实验时间：2021年10月14日
实验一:频繁元素从数据流中获取出现次数最多的三个元素
要求：空间复杂度为O(k)
简述算法过程：
1.k值越大越稳定；（近似解）
2.水库抽样法
Misra-Gries Algorithm
（1）运算逻辑是：不满就放入，如果满了就消掉一行，每个记录中的项都减一；
（2）Misra-Gries算法输出的数据项并不一定是频繁项，但是频繁项一定在输出结果之中。
（3） 频繁项（频数>=n/k）要出现在最终的结果里
建立一个大小为k（此处给k取值为3）的数组，当下一个数到达时，如果数组里有这个数，则其对应的计数器加1；如果数组里没有这个数，则先判断数组容量是否已满，若未满则添加这个数，并为其分配计数器且赋值为1，若已满则弃掉此数，并且数组里所有数的计数器减一，当计数器等于零时，则从该数组中删除此数。
实验代码：
#include#include #include #include using namespace std; class Env { public: int data[50000]; int pointer_max = 0; int pointer = 0; Env() { // test_0.csv test_1.csv test_2.csv 为第一题的测试用例 ifstream file("E:/siat-projects/VS Code Projects/C++ Project/BigData_2/test_data/test_2.csv", ios::in); if (!file.is_open()) cout << " 文件打开失败！" << endl; string temp; while (getline(file, temp)) { data[pointer_max] = atoi(temp.c_str()); pointer_max++; } file.close(); } int get_data() { if (!done()) return data[pointer++]; else return -1; } bool done() { if (pointer < pointer_max) return false; else return true; } }; // 所有的代码都需要写在 Algo 类内，自行定义其他需要的变量或函数 class Algo { public: Algo() { cout << "algo ok" << endl; } int run(Env env) { //在此写入你的代码 //env.get_data() 会返回当前数据流中的数据 //env.done() 表示数据流是否输出完毕 int data = 0; int d[3] = { 0,0,0 }, num[3] = { 0,0,0 }; int isHave; while (!env.done()) { isHave = 0; data = env.get_data(); for (int i = 0; i < 3; i++) { if (data == d[i]) { num[i]++; isHave = 1; break; } } if (isHave == 0) { for (int i = 0; i < 3; i++) { if (d[i] == 0) { d[i] = data; num[i] = 1; isHave = 1; break; } } } if (isHave == 0) { for (int i = 0; i < 3; i++) { if (num[i] > 0) num[i]--; if (num[i] == 0) d[i] = 0; } } } for (int i = 0; i < 3; i++) cout << d[i] << " " << num[i] << endl; return 0; } }; int main() { Algo algo; Env env; cout << "程序结果：" << endl; time_t start = clock(); int res = algo.run(env); time_t end = clock(); cout << "程序耗时: " << double(end - start) / CLOCKS_PER_SEC << " ms" << endl; cout << "占用内存：" << sizeof(algo) << " byte" << endl; system("pause"); return 0; }
实验结果（含时间、空间、输出结果）：
测试样例test_0.csv:
测试样例test_1.csv:
测试样例test_.2csv:
判断一个极大的数组是否是有序数组
要求：时间复杂度为O(log n)
简述算法过程：
（1.i随机值；二分查找找n;判断大小关系;（近似解）---->多找几次2.水库抽样）
利用rand()伪随机函数选数字，利用二分查找在数组中寻找，出现大、中、小的关系排列错误则无序，多次循环，若均已验证为有序则证明该数组已经是有序数组。
实验代码：
#include#include #include #include using namespace std; class Env { public: int data[40000]; int pointer_max = 0; int pointer = 0; Env() { // test_3.csv test_4.csv test_5.csv 为第二题的测试用例 ifstream file("E:/siat-projects/VS Code Projects/C++ Project/BigData_2/test_data/test_5.csv", ios::in); if (!file.is_open()) cout << " 文件打开失败！" << endl; string temp; while (getline(file, temp)) { data[pointer_max] = atoi(temp.c_str()); pointer_max++; } file.close(); } }; // 所有的代码都需要写在 Algo 类内，自行定义其他需要的变量或函数 class Algo { public: Algo() { cout << "algo ok" << endl; } int run(Env env) { // 在此写入你的代码 // env.data[40000] 为已获取到的数组 int l,r,mid,k; //flag为数组中数据顺序标志，1为递增有序，0为无序 int flag; for (int i = 0; i < 5000; i++) { flag = 1; r = 39999; l = 0; k = rand() % 40000; mid = (l + r) / 2; while (l < r - 1) { if (env.data[mid] > env.data[r] || env.data[l] > env.data[mid]) { cout << k << endl; cout << "该数组为无序数组！" << endl; flag = 0; break; } if (env.data[mid] > k) { r = mid; mid = (l + r) / 2; } else if (env.data[mid] < k) { l = mid; mid = (l + r) / 2; } else break; } if (flag == 0) break; } if(flag == 1) cout << "该数组为有序数组！" << endl; return 0; } }; int main() { Algo algo; Env env; cout << "程序结果：" << endl; time_t start = clock(); int res = algo.run(env); time_t end = clock(); cout << "程序耗时: " << double(end - start) / CLOCKS_PER_SEC << " ms" << endl; cout << "占用内存：" << sizeof(algo) << " byte" << endl; system("pause"); return 0; }
实验结果（含时间、空间、输出结果）：
测试样例test_.3csv:
测试样例test_.4csv:
测试样例test_.5csv:
