course_data_structures/Data Structure Class 1/hw2/Benchmark.cpp

#include "Benchmark.h"
#include "SeqList.h"
#include "Utilities.h"
#include <algorithm>
#include <cstdio>
#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_hw2_1(int mn, int mx, int stp, int rep)
{
    /*
    在SeqList.h中编写OrderInsert()函数。
    OrderInsert()函数实现在有序顺序表中
    按数据元素非递减的顺序插入一个数据元素item，
    使得L中的数据元素按值非递减有序序列。
    */
    using TList = SeqList<int>;
    using TPList = TList *;
    Random rnd;
    Timer timer;
    int *nums = new int[1ll * mx * rep];
    if (!nums) __error_then_exit("Memory alloc failed.");
    FileHandleExitOnFail fp("benchmark_hw2_1.txt", "w");
    for (int sz = mn; sz <= mx; sz += stp)
    {
        int idx = sz * rep;
        while (--idx >= 0) nums[idx] = rnd.next();
        TPList lists = (TPList)malloc(sizeof(TList) * rep);
        for (int i = 0; i < rep; i++) new (lists + i) TList(sz);
        timer.start();
        for (int i = 0; i < rep; i++)
        {
            auto list = lists + i;
            for (int j = 0; j < sz; j++)
                list->OrderInsert(nums[++idx]);
        }
        timer.stop();
        for (int i = 0; i < rep; i++)
        {
            auto list = lists + i;
            for (int j = 1, x, y; j < sz; j++)
            {
                list->getData(j, x);
                list->getData(j + 1, y);
                if (x > y) __error_then_exit("Wrong answer! Not a ordered list.");
            }
        }
        int cmp_sum = 0, mov_sum = 0, mem_sum = 0;
        for (int i = 0; i < rep; i++)
        {
            cmp_sum += lists[i].counter.get_cmp();
            mov_sum += lists[i].counter.get_mov();
            mem_sum += lists[i].counter.get_mem();
        }
        for (int i = 0; i < rep; i++) lists[i].~SeqList();
        free(lists);
        __print_result_line(fp, rep, sz, timer.diff_in_ms(), cmp_sum, mov_sum, mem_sum);
    }
    delete[] nums;
}
void benchmark_hw2_3(int mn, int mx, int stp, int rep)
{
    /*
    在SeqList.h中编写MoreRemove（T &x）函数。
    顺序表中可能有重复的x值。
    MoreRemove（T &x）函数实现在有序顺序表中删除所有值为x的元素。
    尽可能算法高效，考虑减少元素移动的次数。
    */
    using TList = SeqList<int>;
    using TPList = TList *;
    using TView = Array2DView<int>;
    Random rnd;
    Timer timer;
    int *nums = new int[1ll * mx * rep];
    if (!nums) __error_then_exit("Memory alloc failed.");
    FileHandleExitOnFail fp("benchmark_hw2_3.txt", "w");
    for (int sz = mn; sz <= mx; sz += stp)
    {
        int idx = sz * rep;
        int vmin = 0, vmax = log2(sz) + 1;
        while (--idx >= 0) nums[idx] = rnd.next(vmin, vmax);
        TView nums_view(sz, nums);
        int *rm = new int[rep];
        for (int i = 0; i < rep; i++)
            rm[i] = *nums_view[i], std::sort(nums_view[i], nums_view[i + 1]);
        TPList lists = (TPList)malloc(sizeof(TList) * rep);
        for (int i = 0; i < rep; i++) new (lists + i) TList(sz);
        for (int i = 0; i < rep; i++)
        {
            for (int j = 0; j < sz; j++)
                lists[i].Insert(j, nums_view[i][j]);
            lists[i].counter.reset();
        }
        timer.start();
        for (int i = 0; i < rep; i++)
            lists[i].MoreRemove(rm[i]);
        timer.stop();
        int cmp_sum = 0, mov_sum = 0, mem_sum = 0;
        for (int i = 0; i < rep; i++)
        {
            cmp_sum += lists[i].counter.get_cmp();
            mov_sum += lists[i].counter.get_mov();
            mem_sum += lists[i].counter.get_mem();
        }
        for (int i = 0; i < rep; i++)
        {
            TPList list = lists + i;
            int len = remove(nums_view[i], nums_view[i + 1], rm[i]) - nums_view[i];
            if (list->Length() != len)
                __error_then_exit("Wrong answer! Not removing correctly.");
            for (int j = 1, x; j <= list->Length(); j++)
            {
                list->getData(j, x);
                if (x != nums_view[i][j - 1])
                    __error_then_exit("Wrong answer! Not removing correctly.");
            }
        }
        for (int i = 0; i < rep; i++) lists[i].~SeqList();
        free(lists);
        __print_result_line(fp, rep, sz, timer.diff_in_ms(), cmp_sum, mov_sum, mem_sum);
    }
    delete[] nums;
}