|
|
#include "Benchmark.h"
|
|
|
#include "Utilities.h"
|
|
|
#include "YourPartition.h"
|
|
|
#include <algorithm>
|
|
|
#include <cstring>
|
|
|
#include <functional>
|
|
|
#include <new>
|
|
|
void __print_result_line(FILE *fp, int rep, int sz, double ms, int cmp, int mov, int mem)
|
|
|
{
|
|
|
fprintf(fp,
|
|
|
"算法对大小为 %d 的数组划分 %d 次所耗费的总时间为：%.6lf ms, 元素移动总次数： %d, 元素值比较总次数： %d, 辅助空间总字节数： %d\n",
|
|
|
sz, rep, ms, cmp, mov, mem);
|
|
|
fprintf(stdout, "算法对大小为 %d 的数组划分 %d 次所耗费的总时间为：%.6lf ms\n", sz, rep, ms);
|
|
|
}
|
|
|
void benchmark_hw1_4(int mn, int mx, int stp, int rep)
|
|
|
{
|
|
|
using namespace std;
|
|
|
/*
|
|
|
划分：将基准元素定位在正确位置（基准元素在序列的最左端）。需要时调用swap函数
|
|
|
*/
|
|
|
Random rnd;
|
|
|
Timer timer;
|
|
|
FileHandleExitOnFail fp("benchmark_hw1_4.txt", "w");
|
|
|
int *nums = new int[mx * rep];
|
|
|
int *pivots = new int[mx];
|
|
|
int *stat = new int[rep * 3];
|
|
|
Array2DView<int> stat_view(3, stat);
|
|
|
if (!nums) __error_then_exit("Memory alloc failed.");
|
|
|
for (int sz = mn; sz <= mx; sz += stp)
|
|
|
{
|
|
|
generate(nums, nums + sz * rep, [&]() { return rnd.next(0, sz); });
|
|
|
Array2DView<int> nums_view(sz, nums);
|
|
|
memset(stat, 0, sizeof(int) * 3 * rep);
|
|
|
for (int i = 0; i < rep; i++)
|
|
|
pivots[i] = nums_view[i][0];
|
|
|
timer.start();
|
|
|
for (int i = 0; i < rep; i++)
|
|
|
Partition(nums_view[i], sz, stat_view[i][0], stat_view[i][1], stat_view[i][2]);
|
|
|
timer.stop();
|
|
|
int cmp_sum = 0, mov_sum = 0, mem_sum = 0;
|
|
|
for (int i = 0; i < rep; i++)
|
|
|
{
|
|
|
mov_sum += stat_view[i][0];
|
|
|
cmp_sum += stat_view[i][1];
|
|
|
mem_sum += stat_view[i][2];
|
|
|
}
|
|
|
for (int i = 0; i < rep; i++)
|
|
|
{
|
|
|
int pos1 = -1, pos2 = sz;
|
|
|
for (int j = 0; j < sz; j++)
|
|
|
if (nums_view[i][j] < pivots[i])
|
|
|
pos1 = j;
|
|
|
for (int j = 0; j < sz; j++)
|
|
|
if (nums_view[i][j] > pivots[i])
|
|
|
{
|
|
|
pos2 = j;
|
|
|
break;
|
|
|
}
|
|
|
if (pos1 > pos2) __error_then_exit("Wrong answer! Not correctly partitioned.");
|
|
|
}
|
|
|
__print_result_line(fp, 200, sz, timer.diff_in_ms(), cmp_sum, mov_sum, mem_sum);
|
|
|
}
|
|
|
delete[] pivots;
|
|
|
delete[] nums;
|
|
|
}
|
