关于：一道腾讯面试题:从大量数字中取出top100

一道腾讯面试题:从大量数字中取出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  

用类快速排序吧？