|
|
#include "Benchmark.h"
|
|
|
#include "LinkedList.h"
|
|
|
#include "Utilities.h"
|
|
|
#include <algorithm>
|
|
|
#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_hw3_2(int mn, int mx, int stp, int rep)
|
|
|
{
|
|
|
using namespace std;
|
|
|
/*
|
|
|
Merge( )函数实现将两个有序单链表La和lb归并到当前操作对象*this表中，
|
|
|
要求La、Lb、*this三个单链表的每个结点被访问一次，且仅被访问一次。
|
|
|
*/
|
|
|
using TNode = LinkNode<int>;
|
|
|
using TList = LinkedList<int>;
|
|
|
using TPNode = TNode *;
|
|
|
using TPList = TList *;
|
|
|
Random rnd;
|
|
|
Timer timer;
|
|
|
FileHandleExitOnFail fp("benchmark_hw3_2.txt", "w");
|
|
|
int *nums = new int[2ll * mx * rep];
|
|
|
if (!nums) __error_then_exit("Memory alloc failed.");
|
|
|
TPList lists = (TPList)malloc(sizeof(TList) * 3 * rep);
|
|
|
for (int sz = mn; sz <= mx; sz += stp)
|
|
|
{
|
|
|
generate(nums, nums + 2 * sz * rep, [&]() { return rnd.next(0, sz); });
|
|
|
Array2DView<int> nums_view(2 * sz, nums);
|
|
|
for (int i = 0; i < rep; i++)
|
|
|
{
|
|
|
sort(nums_view[i], nums_view[i] + sz);
|
|
|
sort(nums_view[i] + sz, nums_view[i + 1]);
|
|
|
}
|
|
|
Array2DView<TList> lists_view(3, lists);
|
|
|
for (int i = 0; i < rep; i++)
|
|
|
{
|
|
|
new (&lists_view[i][0]) TList();
|
|
|
new (&lists_view[i][1]) TList();
|
|
|
new (&lists_view[i][2]) TList();
|
|
|
TPNode last = nullptr;
|
|
|
for (int k = sz - 1; k >= 0; k--)
|
|
|
{
|
|
|
TPNode nxt = new LinkNode<int>(nums_view[i][k], last);
|
|
|
last = nxt;
|
|
|
}
|
|
|
lists_view[i][1].getHead()->link = last;
|
|
|
last = nullptr;
|
|
|
for (int k = sz + sz - 1; k >= sz; k--)
|
|
|
{
|
|
|
TPNode nxt = new LinkNode<int>(nums_view[i][k], last);
|
|
|
last = nxt;
|
|
|
}
|
|
|
lists_view[i][2].getHead()->link = last;
|
|
|
}
|
|
|
timer.start();
|
|
|
auto mem1 = __get_working_set_size();
|
|
|
for (int i = 0; i < rep; i++)
|
|
|
lists_view[i][0].Merge(lists_view[i][1], lists_view[i][2]);
|
|
|
auto mem2 = __get_working_set_size();
|
|
|
auto diff = mem2 - mem1;
|
|
|
timer.stop();
|
|
|
for (int i = 0; i < rep; i++)
|
|
|
sort(nums_view[i], nums_view[i + 1]);
|
|
|
for (int i = 0; i < rep; i++)
|
|
|
{
|
|
|
TPNode h = lists_view[i][0].getHead()->link;
|
|
|
for (int j = 0; j < sz + sz; j++, h = h->link)
|
|
|
if (!h || h->data != nums_view[i][j])
|
|
|
__error_then_exit("Wrong answer! Not correctly merged.");
|
|
|
}
|
|
|
int cmp_sum = 0, mov_sum = 0, mem_sum = 0;
|
|
|
for (int i = 0; i < rep; i++)
|
|
|
{
|
|
|
cmp_sum += lists_view[i][0].counter.get_cmp();
|
|
|
mov_sum += lists_view[i][0].counter.get_mov();
|
|
|
mem_sum += lists_view[i][0].counter.get_mem();
|
|
|
}
|
|
|
for (int i = 0; i < rep; i++)
|
|
|
{
|
|
|
lists_view[i][0].~LinkedList();
|
|
|
lists_view[i][1].~LinkedList();
|
|
|
lists_view[i][2].~LinkedList();
|
|
|
}
|
|
|
__print_result_line(fp, rep, sz, timer.diff_in_ms(), cmp_sum, mov_sum, diff);
|
|
|
}
|
|
|
free(lists);
|
|
|
delete[] nums;
|
|
|
}
|
