103.【C语言】数据结构之TopK问题详细分析

1.定义

2.实现

一个容易想到的方法

稍微改进的方法

最优的方法

分析方法的可行性

取出无序数组的取出前K个元素有几种可能

1.取的全是非TopK个元素中的

2.取的前K个既有非TopK个元素也有TopK个元素

3.取的前K个q恰为TopK个元素

代码实现

步骤

TestTopK代码

PrintTopK的代码

运行结果

3.手动测试

1.使用Access测试

1.运行代码一次,data.txt做后用

2.打开Access,创建空白桌面数据库

3.将data.txt导入到数据库

4.创建查询

2.修改data.txt后测试

1.运行代码一次,data.txt做后用

2.手动修改data.txt

3.修改main.c

4.执行代码,查看结果

1.定义

TopK即排名位于前K个(按从大到小或从小到大排序)

2.实现

一个容易想到的方法

先将无序数组中所有的元素载入内存,再建大堆

但此方法有缺陷,如果数组元素个数过大,比如N=100亿,设以int类型存储,则粗略计算总大小

100亿--> $4*10^{10}$ byte--> $4*10^{10}/(1024*1024*1024)$ GB--> $1024\approx10^3$ -->

约为40GB

实际上一个进程不可能分配40GB的内存,因此无法存储

稍微改进的方法

将大数组拆分为多个小数组,再对每个小数组建大堆,取出前K个即可

最优的方法

先取出无序数组的取出前K个元素,对它们建小堆(这里非常关键),再遍历剩下的(N-K)个元素,如果某个元素的值比堆顶的值要大,就替代堆顶元素,接着向下调整建小堆,反复执行前述过程,最后这个含有K个元素的小堆就是TopK个

分析方法的可行性

取出无序数组的取出前K个元素有几种可能

1.取的全是非TopK个元素中的

说明TopK个元素全在剩下的(N-K)个元素中,由于小堆中的堆顶元素是堆中最小的,因此TopK个元素一定可以进入小堆中替换原来的元素

最后这个小堆的数据一定是最大的前K个

2.取的前K个既有非TopK个元素也有TopK个元素

分析同上,不再赘述

3.取的前K个q恰为TopK个元素

分析同上,不再赘述

代码实现

步骤

1.生成大量随机数写入(fprintf)文件中

2.将TopK个的结果输出

TestTopK代码

void TestTopK()
{int n = 10000;//设置10000个随机数const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen");return;}srand((unsigned int)time(NULL));//设置种子for (int i = 0; i < n; i++){int x = rand() % 10000;//生成1~9999内的随机数fprintf(fin, "%d\n", x);//以文本模式写入文件}fclose(fin);fin = NULL;PrintTopK(file,10);
}

PrintTopK的代码

1.为前K个元素开辟空间

2.打开文件

3.读取前K个元素,放入文件中

4.遍历剩下的(N-K)个元素,多次向下调整

void PrintTopK(const char* file,int K)
{//为前K个元素开辟空间 int* topk = (int*)malloc(sizeof(int) * K);if (topk == NULL){perror("malloc");return;}//打开文件FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen");return;}//从流中读取前K个元素for (int i = 0; i < K; i++){fscanf(fout, "%d", &topk[i]);}//前K个元素建小堆for (int i = (K - 1 - 1) / 2; i >= 0; i--){AdjustDown(topk, K, i);}//将剩余(N-K)个与堆顶元素比较,满足条件则替换,每换一次则向下调整一次int val = 0;int ret = fscanf(fout, "%d", &val);while (ret != EOF){if (val > topk[0]){topk[0] = val;AdjustDown(topk, K, 0);}ret = fscanf(fout, "%d", &val);}fclose(fout);//打印TopK个for (int i = 0; i < K; i++){printf("%d\n", topk[i]);}
}