关于:一路腾讯面试题:从大量数字中取出top100
关于:一道腾讯面试题:从大量数字中取出top100
一道腾讯面试题:从大量数字中取出top100
http://www.iteye.com/topic/628707
虽然题目并不难,但看到许多的人回复了,当然有回复的水平高的也有低的反正各种回复千奇百怪。
能想到用二叉树或堆来做的算想对思路了,用多线程部分排序的感觉至少思路上就差得远了。
有个兄弟第一时间用TreeSet给出了代码,当然代码很简单,如下:
大数据量肯定要尽量的避免排序的,即使是部分也要避免,即能避免就不要排,所以堆和二叉树是最好的选择,内存开销其实不必担心,1亿个数字也没多少吧!
然后看了下TreeSet的first()方法的实现。
first()方法的实现如下:
很明显,取的是最小值,但是它需要每次去找最小值,那个while的开销就完全不必要了,所以选择最小堆才是最明智的选择,人家只在改变节点后才去修改结构,而且取最小值只用取根节点就OK了,TreeSet里面的remove()方法啊也都是需要先查询的,所以这一比较根本没堆有优势(对于此题)。
改成最小堆后,经测试,最小堆花费1800毫秒左右的时间,TreeSet花费的时间大概3600毫秒,接近2倍的差距。
ps:JVM内存改大点,否则可能申请不到1亿的数组 -Xms128M -Xmx1024M
一道腾讯面试题:从大量数字中取出top100
http://www.iteye.com/topic/628707
虽然题目并不难,但看到许多的人回复了,当然有回复的水平高的也有低的反正各种回复千奇百怪。
能想到用二叉树或堆来做的算想对思路了,用多线程部分排序的感觉至少思路上就差得远了。
有个兄弟第一时间用TreeSet给出了代码,当然代码很简单,如下:
package sunfa; import java.util.Random; import java.util.TreeSet; /** * tx的面试题:1亿个数中取前100个最大的数 * * 利用TreeSet这个有序树,100之前随便放,100后要进行替换的话只需要对比树的第一个节点就可以知道该不该放 * */ public class Demo1_tx { public static void main(String[] args) { top100(); } private static void top100(){ TreeSet<Integer> tree = new TreeSet<Integer>(); int n = 100000000; int[] arr = new int[n]; Random ran = new Random(); long start = System.currentTimeMillis(); for (int i = 0; i < n; i++) { arr[i] = ran.nextInt(n); } System.out.println(System.currentTimeMillis() - start); start = System.currentTimeMillis(); for (int i = 0; i < arr.length; i++) { if (tree.size() < 100) { tree.add(arr[i]); } else if (tree.first() < arr[i]) { tree.remove(tree.first()); tree.add(arr[i]); } } System.out.println(System.currentTimeMillis() - start); System.out.println(tree); } }
大数据量肯定要尽量的避免排序的,即使是部分也要避免,即能避免就不要排,所以堆和二叉树是最好的选择,内存开销其实不必担心,1亿个数字也没多少吧!
然后看了下TreeSet的first()方法的实现。
first()方法的实现如下:
final Entry<K,V> getFirstEntry() { Entry<K,V> p = root; if (p != null) while (p.left != null) p = p.left; return p; }
很明显,取的是最小值,但是它需要每次去找最小值,那个while的开销就完全不必要了,所以选择最小堆才是最明智的选择,人家只在改变节点后才去修改结构,而且取最小值只用取根节点就OK了,TreeSet里面的remove()方法啊也都是需要先查询的,所以这一比较根本没堆有优势(对于此题)。
private static void top100() { // TreeSet<Integer> tree = new TreeSet<Integer>(); PriorityQueue<Integer> heap = new PriorityQueue<Integer>(100); int n = 100000000; int[] arr = new int[n]; Random ran = new Random(); long start = System.currentTimeMillis(); for (int i = 0; i < n; i++) { arr[i] = ran.nextInt(n); } System.out.println(System.currentTimeMillis() - start); start = System.currentTimeMillis(); for (int i = 0; i < arr.length; i++) { if (heap.size() < 100) { heap.add(arr[i]); } else if (heap.peek() < arr[i]) { heap.poll(); heap.add(arr[i]); } } System.out.println(System.currentTimeMillis() - start); System.out.println(heap); }
改成最小堆后,经测试,最小堆花费1800毫秒左右的时间,TreeSet花费的时间大概3600毫秒,接近2倍的差距。
ps:JVM内存改大点,否则可能申请不到1亿的数组 -Xms128M -Xmx1024M
1 楼
rain_liang
2011-10-15
用类快速排序吧?