|
|
#include "LinkedList.h"
|
|
|
#include "Utilities.h"
|
|
|
#include <stdio.h>
|
|
|
#include <stdlib.h>
|
|
|
#include <string.h>
|
|
|
#include <time.h>
|
|
|
#include <windows.h>
|
|
|
|
|
|
#define MAXN 600 //设置数组最大长度
|
|
|
|
|
|
/**
|
|
|
* 统计Alg算法对大小从incN，2*incN,3*incN,...,到maxN的数组进行处理的时间
|
|
|
* 对不同大小的数组分别测试numTrials次，记录总的时间
|
|
|
*/
|
|
|
template <class T>
|
|
|
void Alg2(LinkedList<T> &L, int n, int &movenum, int &compnum, int &bytesnum)
|
|
|
{
|
|
|
L.Uniquify(movenum, compnum, bytesnum);
|
|
|
}
|
|
|
|
|
|
template <class T>
|
|
|
void Alg1(LinkedList<T> &L, int n)
|
|
|
{
|
|
|
L.Uniquify();
|
|
|
}
|
|
|
void timeAlg(FILE *fp,
|
|
|
int incN,
|
|
|
int maxN,
|
|
|
int numTrials)
|
|
|
{
|
|
|
void printUsage(); //函数声明
|
|
|
int(*p)[MAXN];
|
|
|
double start_time = 0, end_time = 0;
|
|
|
|
|
|
LARGE_INTEGER startCount;
|
|
|
LARGE_INTEGER endCount;
|
|
|
LARGE_INTEGER freq;
|
|
|
double elapsed;
|
|
|
if (QueryPerformanceFrequency(&freq) == 0) //作用：返回硬件支持的高精度计数器的频率。返回值：非零，硬件支持高精度计数器；零，硬件不支持，读取失败。
|
|
|
{
|
|
|
// 硬件不支持高精度计数器
|
|
|
throw "硬件不支持高精度计数器!";
|
|
|
}
|
|
|
|
|
|
for (int n = incN; n <= maxN; n += incN)
|
|
|
{
|
|
|
srand(time(NULL));
|
|
|
printf("timing n == %d ", n);
|
|
|
//产生numTrials+1个大小为600的二维随机数组p
|
|
|
p = (int(*)[MAXN])malloc((numTrials + 1) * MAXN * sizeof(int));
|
|
|
LinkedList<int> *L = new LinkedList<int>[(numTrials + 1)];
|
|
|
for (int t = 0; t < numTrials + 1; t++)
|
|
|
{
|
|
|
for (int x = 0; x < n; x++)
|
|
|
{
|
|
|
p[t][x] = rand() % (n / 2);
|
|
|
L[t].OrderInsert(p[t][x]);
|
|
|
}
|
|
|
}
|
|
|
|
|
|
//L[numTrials].output(fp); //输出，用于测试函数功能
|
|
|
Alg1(L[numTrials], n); // 对p[numTrials]进行Alg操作不统计运行时间
|
|
|
//L[numTrials].output(fp); //输出，用于测试函数功能
|
|
|
// 开始计时器和效率计数器
|
|
|
int movenum = 0;
|
|
|
int compnum = 0;
|
|
|
int bytesnum = 0;
|
|
|
|
|
|
QueryPerformanceFrequency(&freq);
|
|
|
MemoryMonitor mm;
|
|
|
mm.reset();
|
|
|
QueryPerformanceCounter(&startCount); // 对p[0]..p[numTrials-1]共numTrials个大小为n的一维随机数组进行操作，统计运行总时间
|
|
|
// 统计操作时间和累加基础操作次数和空间字节数
|
|
|
for (int t = 0; t < numTrials; t++)
|
|
|
{
|
|
|
//L[t].output(fp); //输出，用于测试函数功能
|
|
|
Alg2(L[t], n, movenum, compnum, bytesnum);
|
|
|
//L[t].output(fp); //输出，用于测试函数功能
|
|
|
}
|
|
|
// 停止计时器
|
|
|
QueryPerformanceCounter(&endCount);
|
|
|
auto mem2 = __get_working_set_size();
|
|
|
|
|
|
printf(" -Uniquify \n");
|
|
|
|
|
|
// 返回计时器经过时间(单位：毫秒）和基本操作次数、额外空间字节数
|
|
|
elapsed = (double)(endCount.QuadPart - startCount.QuadPart) / freq.QuadPart;
|
|
|
fprintf(fp, "算法对大小为 %d 的数组操作 200 次所耗费的总时间为： %f ms ,元素移动总次数： %d , 元素值比较总次数： %d ,辅助空间总字节数： %d \n", n, elapsed * 1000, movenum, compnum, mm.save());
|
|
|
}
|
|
|
}
|
|
|
|
|
|
// 打印出数组a[]中的所有元素
|
|
|
void printData(int a[], int n)
|
|
|
{
|
|
|
for (int i = 0; i < n - 1; i++)
|
|
|
{
|
|
|
printf("%d ", a[i]);
|
|
|
}
|
|
|
if (n - 1 >= 0)
|
|
|
{
|
|
|
printf("%d", a[n - 1]);
|
|
|
}
|
|
|
}
|
|
|
/** 打印一个正确调用主函数的参数说明 */
|
|
|
void printUsage()
|
|
|
{
|
|
|
printf("Usage:");
|
|
|
printf(" AlgPerf <incr> <max> <runs> <outfile>");
|
|
|
printf(" incr - the initial array size and increment");
|
|
|
printf(" max - the maximum array size");
|
|
|
printf(" runs - the number of runs for each size");
|
|
|
printf(" outfile - is the name of the timing output file");
|
|
|
}
|
