一道腾讯面试题:从大量数字中取出 top 100

最近有同事去腾讯面试,其中一个排序算法题:从1亿个数字中取出最大的100个. 我感觉用位图排序是比较合适的.位图排序的特点是用内存空间换取CPU时间.代码如下:

 

import java.util.Random;

 

public class Top100 {

public static int[] getTop100(int[] inputArray) {

 

int maxValue = Integer.MIN_VALUE;

for (int i = 0; i < inputArray.length; ++i) {

if (maxValue < inputArray[i]) {

maxValue = inputArray[i];

}

}

byte[] bitmap = new byte[maxValue+1];

for (int i = 0; i < inputArray.length; ++i) {

int value=inputArray[i];

bitmap[value] = 1;

}

 

int[] result = new int[100];

int index = 0;

for (int i = maxValue; i >= 0 & index < 100; --i) {

if (bitmap[i] == 1) {

result[index++] = i;

}

}

return result;

}

 

public static void main(String[] args) {

int numberCount = 90000000;

int maxNumber = numberCount;

int inputArray[] = new int[numberCount];

Random random = new Random();

for (int i = 0; i < numberCount; ++i) {

inputArray[i] = Math.abs(random.nextInt(maxNumber));

}

System.out.println("Sort begin...");

long current = System.currentTimeMillis();

int[] result = Top100.getTop100(inputArray);

System.out.println(System.currentTimeMillis() - current);

for (int i = 0; i < result.length; ++i) {

System.out.print(result[i] + ",");

}

}

}

 

我的机子是配置是CPU:Intel(R) Pentium(R) M processor 1.60GHZ,512M内存. 运行结果如下

1千万:1.297秒

2千万: 2.906秒

3千万:4.578秒

4千万:6.203秒

5千万:7.875秒

6千万:9.953秒

7千万:11.407秒

8千万:26.921秒

9千万:31.953秒

 

当运行到1亿数据时,机子几乎就没有反应了,这可能是物理内存已经耗尽,用虚拟内存了.

 

欢迎交流!

评论

19 楼 docong 2010-03-31  

luke_kai 写道

import java.util.Random;
import java.util.Set;
import java.util.TreeSet;

public class TestSF {

public static Set<Integer> getTop100(int[] inputArray) {

TreeSet<Integer> top100 = new TreeSet();
for (int i = 0; i < inputArray.length; i++) {

if (top100.size()<100){
top100.add(inputArray[i]);
}else if ((Integer)top100.first()<inputArray[i]){
Object obj = top100.first();
top100.remove(obj);
top100.add(inputArray[i]);
}

}

return top100;

}

public static void main(String[] args) {

int numberCount = 100000000;

int maxNumber = numberCount;

int inputArray[] = new int[numberCount];

Random random = new Random();

for (int i = 0; i < numberCount; ++i) {

inputArray[i] = Math.abs(random.nextInt(maxNumber));

}

System.out.println("Sort begin...");

long current = System.currentTimeMillis();

Set<Integer> result = TestSF.getTop100(inputArray);

System.out.println("Spend time:"+(System.currentTimeMillis() - current));


}

}

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at TestSF.main(TestSF.java:32)

18 楼 luke_kai 2010-03-31  

不可能吧，我写的那段程序，亿级的数据花销 2.3秒
Spend time:2375

17 楼 flashjay 2010-03-31  

SELECT TOP 100 * FROM table1 ORDER BY value DESC;

16 楼 wjjxf 2010-03-31  

如果这个maxValue 达到2147483648或者数字为long更大，那这个位图数组也很大，不过在最大数不大的情况下，这样算也可以

15 楼 icyiwh 2010-03-31  

  题目没说要排序, 只是说明提取前100个, 那把1亿条数据拆分成n等分, 然后多线程跑每一等分的前100个就行了. 这样的时间复杂度是o(n)<=n, 否则不管用什么样的其它方式其复杂度都应该>n*log_n

14 楼 提烟而过 2010-03-31  

呵呵，先感谢楼主的分享。我个人的意见是：效率快慢首先取决与你数据的存取方式：线性存取（表、栈、队列、串、数组和文件）或是非线性存取(树和图)肯定不一样。其次不同的数据存取方式对不同的排序算法复杂度也不是一样的。我以前上大学好像做过这方面的测试。时间久了忘了，等忙完这个项目一定抽时间再去试下。

13 楼 robin_hood 2010-03-31  

感觉需要很大的内存吧

12 楼 seraphim871211 2010-03-31  

MicahChen 写道

fengshihao 写道

fffvvvzz 写道

你把问题想复杂化了，单次循环，top100用红黑树，如果树大小小于100直接插入，否则比较树中最小值，大于则移去最小值，插入新值。

严重同意  呵呵 . 大顶堆 而已 .

哈哈，最大堆正解，头100个节点不断构造就可以了

按照题目来说应该使用大小为100的最小堆。其他多线程、分开合并纯属多余。LZ的方式比较耗内存，性能也不怎么好。

11 楼 蔡华江 2010-03-31  

用treeset在千万级的测试要21秒，，亿级别的没测出来 ，不愿等了

10 楼 fffvvvzz 2010-03-31  

aoliwen521 写道

fffvvvzz 写道

你把问题想复杂化了，单次循环，top100用红黑树，如果树大小小于100直接插入，否则比较树中最小值，大于则移去最小值，插入新值。

请问，用java实现，也就是一个treeset就可以了吗？

我不太熟悉java，如果treeset是有序树的话，那就没问题

9 楼 luke_kai 2010-03-31  

import java.util.Random;
import java.util.Set;
import java.util.TreeSet;

public class TestSF {

public static Set<Integer> getTop100(int[] inputArray) {

TreeSet<Integer> top100 = new TreeSet();
for (int i = 0; i < inputArray.length; i++) {

if (top100.size()<100){
top100.add(inputArray[i]);
}else if ((Integer)top100.first()<inputArray[i]){
Object obj = top100.first();
top100.remove(obj);
top100.add(inputArray[i]);
}

}

return top100;

}

public static void main(String[] args) {

int numberCount = 100000000;

int maxNumber = numberCount;

int inputArray[] = new int[numberCount];

Random random = new Random();

for (int i = 0; i < numberCount; ++i) {

inputArray[i] = Math.abs(random.nextInt(maxNumber));

}

System.out.println("Sort begin...");

long current = System.currentTimeMillis();

Set<Integer> result = TestSF.getTop100(inputArray);

System.out.println("Spend time:"+(System.currentTimeMillis() - current));


}

}

8 楼 jianghengwei 2010-03-31  

1亿的数据， 我建议用1亿的数据进行分割， 分割成10万*1000次；
10万条数据排序一次，取前最大的100条数据，放到缓存中，总共要进行1001次就可以了。
如果要考虑性能的问题， 我们可以用多线程进行排序。

7 楼 JE帐号 2010-03-31  

1.原理上讲就是一个长度为100的有序结构快速插入的问题.
2.不过放这么大的源数据,是否还有什么特别需要,是否有人知道?比如可以分成10个任务给10个CPU分别求top100,再合并之类的.

6 楼 nishizhutoua 2010-03-31  

1.有负数么?
2.数重复么?

5 楼 aoliwen521 2010-03-31  

fffvvvzz 写道

你把问题想复杂化了，单次循环，top100用红黑树，如果树大小小于100直接插入，否则比较树中最小值，大于则移去最小值，插入新值。

请问，用java实现，也就是一个treeset就可以了吗？

4 楼 MicahChen 2010-03-31  

fengshihao 写道

fffvvvzz 写道

你把问题想复杂化了，单次循环，top100用红黑树，如果树大小小于100直接插入，否则比较树中最小值，大于则移去最小值，插入新值。

严重同意  呵呵 . 大顶堆 而已 .

哈哈，最大堆正解，头100个节点不断构造就可以了

3 楼 J-catTeam 2010-03-31  

<div class="quote_title">hikelee 写道</div>
<div class="quote_div">
<p> </p>
<p>最近有同事去腾讯面试,其中一个排序算法题:从1亿个数字中取出最大的100个. 我感觉用位图排序是比较合适的.位图排序的特点是用内存空间换取CPU时间.代码如下:</p>
<p> </p>
<p>import java.util.Random;</p>
<p> </p>
<p>public class Top100 {</p>
<p>public static int[] getTop100(int[] inputArray) {</p>
<p> </p>
<p>int maxValue = Integer.MIN_VALUE;</p>
<p>for (int i = 0; i &lt; inputArray.length; ++i) {</p>
<p>if (maxValue &lt; inputArray[i]) {</p>
<p>maxValue = inputArray[i];</p>
<p>}</p>
<p>}</p>
<p>byte[] bitmap = new byte[maxValue+1];</p>
<p>for (int i = 0; i &lt; inputArray.length; ++i) {</p>
<p>int value=inputArray[i];</p>
<p>bitmap[value] = 1;</p>
<p>}</p>
<p> </p>
<p>int[] result = new int[100];</p>
<p>int index = 0;</p>
<p>for (int i = maxValue; i &gt;= 0 &amp; index &lt; 100; --i) {</p>
<p>if (bitmap[i] == 1) {</p>
<p>result[index++] = i;</p>
<p>}</p>
<p>}</p>
<p>return result;</p>
<p>}</p>
<p> </p>
<p>public static void main(String[] args) {</p>
<p>int numberCount = 90000000;</p>
<p>int maxNumber = numberCount;</p>
<p>int inputArray[] = new int[numberCount];</p>
<p>Random random = new Random();</p>
<p>for (int i = 0; i &lt; numberCount; ++i) {</p>
<p>inputArray[i] = Math.abs(random.nextInt(maxNumber));</p>
<p>}</p>
<p>System.out.println("Sort begin...");</p>
<p>long current = System.currentTimeMillis();</p>
<p>int[] result = Top100.getTop100(inputArray);</p>
<p>System.out.println(System.currentTimeMillis() - current);</p>
<p>for (int i = 0; i &lt; result.length; ++i) {</p>
<p>System.out.print(result[i] + ",");</p>
<p>}</p>
<p>}</p>
<p>}</p>
<p> </p>
<p>我的机子是配置是CPU:Intel(R) Pentium(R) M processor 1.60GHZ,512M内存. 运行结果如下</p>
<p>1千万:1.297秒</p>
<p>2千万:<span style="white-space: pre;"> </span>2.906秒</p>
<p>3千万:4.578秒</p>
<p>4千万:6.203秒</p>
<p>5千万:7.875秒</p>
<p>6千万:9.953秒</p>
<p>7千万:11.407秒</p>
<p>8千万:26.921秒</p>
<p>9千万:31.953秒</p>
<p> </p>
<p>当运行到1亿数据时,机子几乎就没有反应了,这可能是物理内存已经耗尽,用虚拟内存了.</p>
<p> </p>
<p>欢迎交流!</p>
<p> </p>
<p> </p>
<p>100*100000000</p>
</div>
<p> </p>

2 楼 fengshihao 2010-03-31  

fffvvvzz 写道

你把问题想复杂化了，单次循环，top100用红黑树，如果树大小小于100直接插入，否则比较树中最小值，大于则移去最小值，插入新值。

严重同意  呵呵 . 大顶堆 而已 .

1 楼 fffvvvzz 2010-03-31  

你把问题想复杂化了，单次循环，top100用红黑树，如果树大小小于100直接插入，否则比较树中最小值，大于则移去最小值，插入新值。