个人blog原文地址:
http://www.gemoji.me/java_top_n/
距离上次写博客有一个月了, 反省下。今天先写篇简单点的,算是热热身吧。
写在前面
我想几乎每个找过工作的程序员都曾经在面试的时候遇到过如何求topN的问题,而且多数都能不假思索的回答:求topN大用小顶堆,求topN小用大顶堆(觉得反了的同学请去面壁。。。),但是应该也有一部分同学和我之前一样,一直只是把它作为一道面试题而已。
思路
说来不怕丢人,我真的是最近才遇到需要求top N大的场景,囧。。。当时的第一反应是要自己实现一个固定大小的二叉堆,因为印象中常用的Java工具类里并没有现成的实现,但是从头开始实现一个基础工具类是件挺麻烦的事情,别的不说,单是测试就得耗费不少功夫,网上虽然有很多现有实现,但是都不见得那么靠谱。于是想了一个折中的办法就是,对现有的成熟的Java工具类做封装,以达到想要的功能。
代码实现
JDK里有一个现成的工具类叫PriorityQueue,顾名思义,实现的是优先队列的功能,它能够保证每次插入新元素后,队列首位始终是优先级最高的元素,这正是我们想要的,但是它并没有对队列的容量做限制,因此只要对这一点做些许改造,就能达到我们期望的效果。代码如下:
//固定容量的优先队列,模拟大顶堆,用于解决求topN小的问题
public static class FixSizedPriorityQueue>{
private PriorityQueue queue;
private int maxSize; //堆的最大容量
public FixSizedPriorityQueue(int maxSize){
if(maxSize <= 0) throw new IllegalArgumentException();
this.maxSize = maxSize;
this.queue = new PriorityQueue(maxSize, new Comparator() {
@Override
public int compare(E o1, E o2) {
return o2.compareTo(o1);
}
});
}
public void add(E e){
if(queue.size() < maxSize){ //未达到最大容量,直接添加
queue.add(e);
}else{ //队列已满
E peek = queue.peek();
if(e.compareTo(peek) < 0){ //将新元素与当前堆顶元素比较,保留较小的元素
queue.poll();
queue.add(e);
}
}
}
public List sortedList(){
List list = new ArrayList(queue);
Collections.sort(list); //PriorityQueue本身的遍历是无序的,最终需要对队列中的元素进行排序
return list;
}
}
注意一下构造PriorityQueue时用到的Comparator,这里面有个比较tricky的地方,因为代码本身是想实现一个大顶堆来解决求topN小的问题,而PriorityQueue的优先级定义是元素越小优先级越高,这与我们的期望相反,因此我们需要自定义PriorityQueue的Comparator,反转元素大小的定义,这样就能保证队列首位的元素是当前队列中最大的。而在比较新元素和队列首位元素的大小时,则是按照正常的元素大小定义做比较。
结尾
在需要快速实现需求的时候,我们可能没有足够的时间把代码写得很完美,如何写最少的代码实现想要的功能,也是我们日常工作中需要考虑的问题。
PS:文中若有纰漏之处,敬请拍砖。
分享到:
相关推荐
在大量的数据记录中,...TopN问题。这是一个常常遇到的问题,也是一个比较简单的算法问题,却很少能有人能写出最优化的 topn算法。本文对常见的TopN算法,进行分析比较,最后给出最优的TopN算法:基于小根堆的筛选 法.
可以用于对任意数据类型进行topN排序,同时保持数据原来的序号或位置,在信息检索上非常使用,代码简单高效,使用简单。
Spark中实现MapReduce的TopN算法,分为唯一键TopN算法,非唯一键TopN算法和Group内的TopN算法
已知有若干个文件(多个),文件中包含若干个正整数,每行一个,示例如下: 45 3 78 456 70 1 999 。。。 编写MR程序分别求解所有文件中最大的三个值(TOP 3)
详细介绍tableau topN的实现方法,对于TOP N以外的值汇总为“其它”项。
东北大学 软件学院 java期末作业 分布式TOPK算法 基本实现功能
TOPN.pbix DAX中很实用的表函数:TOPN,返回表的前N行,是非重复的行哦
hive不直接支持分组取TopN的操作,需要自定义udf函数打成jar包添加到hive运行环境中
通过跟踪TOP N小区的信令跟踪,发现其中大部分CS业务都是未插SIM卡的紧急呼叫业务,这个结果可以证明和解释以下几个问题: 1. KPI中的统计结果,紧急呼叫占很大比例,接近80%; 2. 为什么以前NodeB同事到这些地区路...
淘宝开放平台JAVA版SDK top4java
自己编写的代码,可以修改代码,csdn找不到相关资料,可以试着模仿
top N 算法,我只是转载,感谢原作者,求实严谨的态度,学习 http://blog.chinaunix.net/uid/20528042.html
获取当前jvm占用CPU的线程, 分析性能问题利器。
网路优化资料,主要是关于topn小区处理的相关基础知识
大数据实验报告Spark编程实现TopN和InvertedIndex程序.doc
本文通过举例的方式来教你如何在Oracle中实现SELECT TOP N的方法。
一个简单的程序,用于计算无法直接加载到内存(1GB)的大文件(100GB)中最常出现的url的topn。 用法 生成测试数据 make data 使用1GB网址进行测试 make test 使用100GB网址运行 make run 算法 根据hash(url)将...
spark实现分组求和
一种缓解推荐偏好的协同过滤TopN算法.docx一种缓解推荐偏好的协同过滤TopN算法.docx一种缓解推荐偏好的协同过滤TopN算法.docx一种缓解推荐偏好的协同过滤TopN算法.docx一种缓解推荐偏好的协同过滤TopN算法.docx一种...
hive中分组取topN、row_number、rank和dense_rank使用介绍