|
精华帖 (0) :: 良好帖 (9) :: 新手帖 (15) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2010-03-31
用treeset在千万级的测试要21秒，，亿级别的没测出来 ，不愿等了
|
| 返回顶楼 | |
|
发表时间：2010-03-31
MicahChen 写道 fengshihao 写道 fffvvvzz 写道 你把问题想复杂化了，单次循环，top100用红黑树，如果树大小小于100直接插入，否则比较树中最小值，大于则移去最小值，插入新值。
严重同意 呵呵 . 大顶堆 而已 . 哈哈，最大堆正解，头100个节点不断构造就可以了 按照题目来说应该使用大小为100的最小堆。其他多线程、分开合并纯属多余。LZ的方式比较耗内存，性能也不怎么好。 |
| 返回顶楼 | |
|
发表时间：2010-03-31
感觉需要很大的内存吧
|
| 返回顶楼 | |
|
发表时间：2010-03-31
呵呵，先感谢楼主的分享。我个人的意见是：效率快慢首先取决与你数据的存取方式：线性存取（表、栈、队列、串、数组和文件）或是非线性存取(树和图)肯定不一样。其次不同的数据存取方式对不同的排序算法复杂度也不是一样的。我以前上大学好像做过这方面的测试。时间久了忘了，等忙完这个项目一定抽时间再去试下。
|
| 返回顶楼 | |
|
发表时间：2010-03-31
题目没说要排序, 只是说明提取前100个, 那把1亿条数据拆分成n等分, 然后多线程跑每一等分的前100个就行了. 这样的时间复杂度是o(n)<=n, 否则不管用什么样的其它方式其复杂度都应该>n*log_n
|
| 返回顶楼 | |
|
发表时间：2010-03-31
如果这个maxValue 达到2147483648或者数字为long更大，那这个位图数组也很大，不过在最大数不大的情况下，这样算也可以
|
| 返回顶楼 | |
|
发表时间：2010-03-31
SELECT TOP 100 * FROM table1 ORDER BY value DESC;
|
| 返回顶楼 | |
|
发表时间：2010-03-31
不可能吧，我写的那段程序，亿级的数据花销 2.3秒
Spend time:2375 |
| 返回顶楼 | |
|
发表时间：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) |
| 返回顶楼 | |
|
发表时间：2010-03-31
这个错误是在初始化数组的时候产生的，你要加参数-Xms128M -Xmx1024M。排序的时候内存又不会增加多少。
|
| 返回顶楼 | |
