使用benchmark比较分治法与归纳法求解最大子数组问题的性能

#include <benchmark/benchmark.h>

#include <algorithm>
#include <deque>
#include <functional>
#include <iostream>
#include <random>
#include <string>
#include <vector>

using namespace std;

static const int _num = 5000;
static const int _lrange = -1000;
static const int _rrange = 1000;
static const int _iter = 20;




int max_across_subarray(vector<int> _array, size_t left, size_t mid,
												size_t right) {
	int lmax = -10000, rmax = -10000, lsum = 0, rsum = 0;
	for (auto lIter = _array.begin() + mid; lIter >= _array.begin() + left;
			 lIter--) {
		lsum += *lIter;
		lmax = max(lsum, lmax);
	}
	for (auto rIter = _array.begin() + mid + 1; rIter <= _array.begin() + right;
			 rIter++) {
		rsum += *rIter;
		rmax = max(rsum, rmax);
	}
	return lmax + rmax;
}

int max_subarray(vector<int> _array, size_t left, size_t right) {
	if (left == right) return _array.at(left);
	size_t mid = (left + right) / 2;
	int lmax = max_subarray(_array, left, mid);
	int rmax = max_subarray(_array, mid + 1, right);
	int mmax = max_across_subarray(_array, left, mid, right);
	return max(max(lmax, rmax), mmax);
}

int max_across_subarray_induction(vector<int> _array, size_t right) {
	int lmax = -10000, lsum = 0;
	for (auto lIter = _array.begin() + right; lIter >= _array.begin(); lIter--) {
		lsum += *lIter;
		lmax = max(lsum, lmax);
	}
	return lmax;
}

int max_subarray_induction(vector<int> _array, size_t right) {
	if (right == 0) return _array.front();
	int former_max = max_subarray_induction(_array, right - 1);
	int left_max = max_across_subarray_induction(_array, right);
	return max(former_max, left_max);
}


static void BM_demo_1(benchmark::State& state) {
	for (auto _ : state) {
		state.PauseTiming();
		vector<int> a;
		random_device rd;
		mt19937 gen(rd());
		uniform_int_distribution<int> dist(_lrange, _rrange);
		for (int i = 0; i < _num; ++i) {
			a.push_back(dist(gen));
		}
		state.ResumeTiming();
		max_subarray(a, 0, a.size() - 1);
	}
}
BENCHMARK(BM_demo_1)->Iterations(_iter);

static void BM_demo_2(benchmark::State& state) {
	for (auto _ : state) {
		state.PauseTiming();
		vector<int> a;
		random_device rd;
		mt19937 gen(rd());
		uniform_int_distribution<int> dist(_lrange, _rrange);
		for (int i = 0; i < _num; ++i) {
			a.push_back(dist(gen));
		}
		state.ResumeTiming();
		max_across_subarray_induction(a, a.size() - 1);
	}
}
BENCHMARK(BM_demo_2)->Iterations(_iter);

BENCHMARK_MAIN();