揭秘Top-K问题:算法探索、性能优化与应用场景深度解析

举报
鸽芷咕 发表于 2023/12/22 22:42:10 2023/12/22
【摘要】 TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大*比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

一、什么是 TOPK 问题?

Top-K 问题是一类常见的算法问题,其中目的是从一组元素中找到排名前K的元素。具体来说,对于给定的一组数据。

  • Top-K 问题要求找到其中最大(或最小)的K个元素。

二、日常生活中的 TOPK 问题

Top-K 问题要求找到其中最大(或最小)的K个元素,这类问题我们的生活中也经常遇到,例如排名问题?

  • 例如找出排名最高的 5 家店铺,这就要根据销量来算了
  • 淘宝效率最高的5个店铺这些都需要用到 TOPK 问题

2.1 美团店面排行

在这里插入图片描述

2.2 软件排行榜

在这里插入图片描述

2.3 富豪榜

在这里插入图片描述

三、TOPK 问题的实现代码

TOPK问题大家第一时间想到的当让当然就是 排序但排序的消耗太大了,我们只需要找到前 100 名但要把整个数据全部排序好。

  • 而我们刚好学了堆这个是数据结构
  • 每次 堆顶要不就是最大或者最小的

而需要前100名的时候就先把,前100 个数据建。然后再和堆顶进行比较进行向下调整,这样整个数据的前100是不就被排出来了。

3.1 TOK问题的核心思想

🔥 前 TOP 个数据建堆,每次拿堆顶和剩下数据进行比较,进行向下调整。

  • 这样我们建的堆就是 最大或最小的前 TOP个数

📚 代码演示:

void PrintTopK(const char* filename, int k)
{
	// 1. 打开数据文件建堆--用a中前k个元素建堆
	FILE* fout = fopen(filename, "r");
	if (fout == NULL)
	{
		perror("fopen fail");
		return;
	}
	//开辟堆空间
	int* minheap = (int*)malloc(sizeof(int) * k);
	if (minheap == NULL)
	{
		perror("malloc fail");
		return;
	}
	//录入数据
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minheap[i]);
	}
	//建堆
	for (int i = (k - 2) / 2; i >= 0; --i)
	{
		adjustdown(minheap, k, i);
	}

	// 2. 将剩余n-k个元素依次与堆顶元素交换,不满则则替换
	int x = 0;
	while (fscanf(fout, "%d", &x) != EOF)
	{
		if (x > minheap[0])
		{
			minheap[0] = x;
			adjustdown(minheap, k, 0);
		}
	}

	free(minheap);
	fclose(fout);
}

🔥 注:这里采用的是文件打开方式有些书上可能给的是一个数组接收原理都是一样的!
在这里插入图片描述

3.2 数据文件的创建

📚 代码演示:

void TestTopk()
{
	// 造数据
	int n = 10000000;
	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) % 10000000;
		fprintf(fin, "%d\n", x);
	}

	fclose(fin);
	//PrintTopK(a, n, 10);
}

3.2 TOK问题的代码测试

这里拿了一千万个数据进行比较可以看到,只需要几秒钟就出来了大家可以去试验一下。

在这里插入图片描述

📝文章结语:

☁️ 把本章的内容全部掌握,铁汁们就可以熟练应用switch语句啦!
看到这里了还不给博主扣个:
⛳️ 点赞🍹收藏 ⭐️ 关注

💛 💙 💜 ❤️ 💚💓 💗 💕 💞 💘 💖
拜托拜托这个真的很重要!
你们的点赞就是博主更新最大的动力!
有问题可以评论或者私信呢秒回哦。
在这里插入图片描述

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。