江苏省建设执业资格中心网站,WordPress的黑色,学网站建设哪里好,南海军事新闻最新消息1.top-k问题
1.1思路分析 TOP-K 问题#xff1a;即求数据结合中前 K 个最大的元素或者最小的元素#xff0c;一般情况下数据量都比较大 。 比如#xff1a;专业前 10 名、世界 500 强、富豪榜、游戏中前 100 的活跃玩家等。 对于 Top-K 问题#xff0c;能想到的最简单直…1.top-k问题
1.1思路分析 TOP-K 问题即求数据结合中前 K 个最大的元素或者最小的元素一般情况下数据量都比较大 。 比如专业前 10 名、世界 500 强、富豪榜、游戏中前 100 的活跃玩家等。 对于 Top-K 问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了 ( 可能 数据都不能一下子全部加载到内存中) 。 在我们之前的解决方法中堆的物理结构都是数组假如我们要在100亿个人中找出前十个有钱的人暂且不论每个人的数据是结构体就把每个人的数据看做一个整数。 100亿个整数有400亿个字节。我们把1000 000 000看做1024^3也就是十亿字节是一个g四百亿字节就是40个g一个简单的找前十有钱人功能就需要运行内存为40个g的电脑空间需求未免也太大了。 我们以共有N个数据找前k个举例 (N远大于k)
思路一 假如电脑运行内存足够大我们建立出了这样一个大堆依据上文C语言数据结构基础笔记——树、二叉树简介-CSDN博客中的讲解用向上遍历的向下调整算法建大堆时间复杂度是O(n),再pop k次由于每次pop都会经历向下调整算法故总复杂度应该为NklogN 思路二 建立一个由k个树构成的小堆保证根部是先存在堆中最小的数据然后遍历数据遇到比根更小的数据就交换并且实行向下调整算法时间复杂度应N-kkNlogkk是将k个数据建堆的消耗N-k是遍历剩下元素的消耗 对比两种思路时间复杂度接近但是思路二的空间复杂度为O(1)思路二的空间复杂度为O(N)
因此思路二是最佳选择。 总结就是找最大的k个用小堆找最小的k个用大堆这样才能挑出最不符合条件的来被替换掉
1.2代码实现
我们以在文件中读取和输入为背景实现将文件中的top_k个数据给输出
首先作为程序员一定是不能去手动给文件中输入一万个随机值作为测试用例的。
我们封装一段函数来创造样本输入到本地的data.txt中去
void CreatFile(void) {const char* filename data.txt;int number 100;FILE* pf fopen(filename, w);//初始化时间种子srand((unsigned int)time(NULL));for (int i 0; i number; i) {fprintf(pf, %d\n, rand());}fclose(pf);
}
先只创造100个即可
创造测试用例也有许多技巧在之后的测试中会有体现 创造好样本后我们在topk函数中建k个数的小堆运用文件读写的方法先写入K个数据再依次遍历并进行交换 void topk(int k,int number) {//建立数组空间HeapDataType* minheap (HeapDataType*)malloc(sizeof(HeapDataType) * k);if (minheap NULL) {perror(malloc fail!);exit(1);}//打开文件将k个数据先放入数组const char* filename data.txt;FILE* pf fopen(filename, r);for (int i 0; i k; i) {fscanf(pf, %d, minheap[i]);}//使用向上遍历的向下调整算法建小堆for (int i (k - 1 - 1) / 2; i 0; i--) {AdjustDown(minheap, k, i);}//此时k个数据的小堆已经建好开始遍历数组for (int i 1; i number-k ; i) {int x 0;fscanf(pf, %d, x);if (x minheap[0]) {Swap(x, minheap[0]);AdjustDown(minheap, k, 0);}}fclose(pf);for (int i 0; i k; i) {printf(%d , minheap[i]);}
}int main() {int k 0;int number 0;printf(请输入k值和数据总量:\n);scanf(%d,%d, k,number);// CreatFile(number);topk(k,number);return 0;
} 我们再将样本调小,k输入5,number输入10
注意输入数据时两个数据之间需要是英文的逗号中文的逗号会被视作两个字符而导致number不能正确读入 由此可见我们成功的完成了任务输出了10个数中最大的五个。
可是有没有可能我们的代码在数据量如此小的时候能跑过当数据达到100万时会挂掉呢
我们将k调到10number调到100万新的问题又出现了我怎么才知道输出的就是最大的10个呢100万个数据没法使用肉眼比较。
测试小技巧
控制用例范围
//将生成随机数的语句调整为
fprintf(pf, %d\n, (rand() i)%1000000);
再在文件中手动设置出最大的几个样本用于检测.随机加入了11111和23456或者123123等 第一次使用creat函数第二次使用topk函数 这样更便于调试 topk问题成功解决。
