如何在100亿个数据中找出最大的前10个数
首先我们知道100亿个数char类型需要越40G的空间,如果我们通过排序来看,我们不难发现需要大量的时间。
所以我们这里提供了一种思路:
1.我们可以建立一个堆存放10个数字,做小堆.
之后遍历10亿个数,把每个数与堆顶比较。大于堆顶就代替堆顶,进堆。然后调整。遍历结束后,堆里面的就是最大的10个数。
这道题是找N个数中最大的K个数,我们这个算法可以把效率提高到K+(N-K)*logK
如果我们直接用堆排序,我们的速度就是N*logN所以我们的这种新方法效率明显高于堆排序
这里我们来实验一下,先造10亿个数,然后找最大的前10个
代码示例:
void CreateNDate()
{
int n = 100000;
srand(time(0));
const char* file = "data.txt";
FILE* fin = fopen(file, "w");
if (fin == NULL)
{
perror("fopen error");
return;
}
for (int i = 0; i < n; ++i)
{
int x = (rand()+i) % 1000000;
fprintf(fin, "%d\n", x);
}
fclose(fin);
}
void topk()
{
printf("请输入k:>");
int k = 0;
scanf("%d", &k);
const char* file = "data.txt";
FILE* fout = fopen(file, "r");
if (fout == NULL)
{
perror("fopen error");
return;
}
int val = 0;
int* minheap = (int*)malloc(sizeof(int) * k);
if (minheap == NULL)
{
perror("malloc error");
return;
}
for (int i = 0; i < k; i++)
{
fscanf(fout, "%d", &minheap[i]);
}
// 建k个数据的小堆
for (int i = (k - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(minheap, k, i);
}
int x = 0;
while (fscanf(fout, "%d", &x) != EOF)
{
// 读取剩余数据,比堆顶的值大,就替换他进堆
if (x > minheap[0])
{
minheap[0] = x;
AdjustDown(minheap, k, 0);
}
}
for (int i = 0; i < k; i++)
{
printf("%d ", minheap[i]);
}
fclose(fout);
}
int main()
{
CreateNDate();
topk();
return 0;
}