前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >揭秘Top-K问题:算法探索、性能优化与应用场景深度解析

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

作者头像
鸽芷咕
发布2023-12-25 15:18:25
3550
发布2023-12-25 15:18:25
举报
文章被收录于专栏:C++干货基地C++干货基地
在这里插入图片描述
在这里插入图片描述

🎬 鸽芷咕个人主页 🔥 个人专栏: 《linux深造日志》 《高效算法》

⛺️生活的理想,就是为了理想的生活!


文章目录
  • 一、什么是 TOPK 问题?
  • 二、日常生活中的 TOPK 问题
    • 2.1 美团店面排行
    • 2.2 软件排行榜
    • 2.3 富豪榜
  • 三、TOPK 问题的实现代码
    • 3.1 TOK问题的核心思想
    • 3.2 数据文件的创建
    • 3.2 TOK问题的代码测试
  • 📝文章结语:

一、什么是 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个数

📚 代码演示:

代码语言:javascript
复制
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 数据文件的创建

📚 代码演示:

代码语言:javascript
复制
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语句啦! 看到这里了还不给博主扣个: ⛳️ 点赞🍹收藏 ⭐️ 关注 💛 💙 💜 ❤️ 💚💓 💗 💕 💞 💘 💖 拜托拜托这个真的很重要! 你们的点赞就是博主更新最大的动力! 有问题可以评论或者私信呢秒回哦。

在这里插入图片描述
在这里插入图片描述
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2023-12-22,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 文章目录
  • 一、什么是 TOPK 问题?
  • 二、日常生活中的 TOPK 问题
    • 2.1 美团店面排行
      • 2.2 软件排行榜
        • 2.3 富豪榜
        • 三、TOPK 问题的实现代码
          • 3.1 TOK问题的核心思想
            • 3.2 数据文件的创建
              • 3.2 TOK问题的代码测试
              • 📝文章结语:
              相关产品与服务
              腾讯云服务器利旧
              云服务器(Cloud Virtual Machine,CVM)提供安全可靠的弹性计算服务。 您可以实时扩展或缩减计算资源,适应变化的业务需求,并只需按实际使用的资源计费。使用 CVM 可以极大降低您的软硬件采购成本,简化 IT 运维工作。
              领券
              问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档