寻找最优的topn算法_topn算法java,javatopn资源-CSDN文库

4星 · 超过85%的资源需积分: 50 75 浏览量 2009-10-25 16:08:26 上传评论 1 收藏 93KB PDF 举报

资源推荐

资源详情

资源评论

寻找最优的 TopN 算法

mail:cuichaox@gmail.com

blog: http://cuichaox.cublog.cn

1 概要

在大量的数据记录中，依据某可排序的记录属性（一般为数字类型），找出最大的前 N 个记录，称为

TopN 问题。这是一个常常遇到的问题，也是一个比较简单的算法问题，却很少能有人能写出最优化的

topn 算法。本文对常见的 TopN 算法，进行分析比较，最后给出最优的 TopN 算法：基于小根堆的筛选

法.

2 问题定义

为了方便。我们把问题具体化：要求使用 C 语言来实现函数，在一个大小为 m 的，无序的整数数组中选

取最大的 n 个整数。即，问题定义为一个函数的实现:

int * topn(int *pdata, int m,int *ptop, int n);

其中，pdata 指向保存大量整数的内存，整数的个数为 m，要求函数把前 n 个最大的整数保存到 ptop 指

向的内存中,显然满足

m

≥

n

≥0

。同时假定

n



m

2

，因为当 n 如果超过半数，可以问题转换为排

除

n

−

m

2

个最小的整数----这种转换减少了问题规模。并且，已经实现选择 n 个最值（最大或最小）

的算法的情况下，排除 n 个最值的算法可以仿照实现。这里不再费时间叙述。

我们虽然假设的数据类型为整数，其他任意的数据类型，只要其数据是可以排序的，都可以根据这里的

算法，写出对应的算法实现。同样，我们虽然假定输入数据的方式为数组，实际输入的方式可以是任意

其他方式（如文件，数据库等）。

3 算法介绍

3.1 算法 1 完整排序法

对 pdata 中的数据，进行内部排序，然后选取前 n 个整数放到 ptop 中。如果使用较高效率的内部排序

算法（如：快速排序，堆排序），复杂度为

m

∗log

2

m

.

使用这种算法，结果数据是从大到小排序的。

3.2 算法 2 基于有序数组的筛选法

保持 ptop 中的结果数组有序，即满足

ptop

[0]≥

ptop

[1]≥...≥

ptop

[

n

−1]

，遍历 pdata 中的数

据，如果发现当前整数大于 ptop[n-1]就把数据插入到合适位置，以保持 ptop 中的仍然有序。算法复

杂度为.

m

∗

n

使用这种算法，结果数据是从大到小排序的。

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余6页未读，立即下载

内容反馈

wu_qiang_

2013-04-23

还不错，基本实现了功能

cuichaox

粉丝: 6
资源: 1

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip