|
精华帖 (0) :: 良好帖 (9) :: 新手帖 (15) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2010-04-01
建议还是不要使用多线程，我用1000个线程和2个线程相比，这两个时间简直就不再一个数量级上，花费在线程上的开销占了绝大多数的时间
|
| 返回顶楼 | |
|
发表时间：2010-04-01
SB腾讯的那帮人喜欢装 B,喜欢出些整人的问题.
|
| 返回顶楼 | |
|
发表时间：2010-04-02
最后修改：2010-04-02
taojingrui 写道 这样的考题，我遇过多次了。其实这类题，考官考的东西并不完全是算法。完全追求算法，就陷进去了。考题考的是两方面，一是考虑内存，纯粹用排序算法是不可能的，光int[] nums = new int[100000000];这一句就可能导致内存不够。（增加内存根本不是考官希望的，这么个小程序就要增加内存？）二是考虑在内存许可的情况下，尽量提高速度。
方法1 基本上，这道题如果不考虑数据录入，调用两次循环，上亿的数字中找top100，用不到1秒应该就够了。 提示： 1.考虑用位（bit）数组，1亿bit需要多少内存？100000000/1024/1024/8<12M，就是10亿数字，也不到120M 2.一个bit的数组大小为1亿，bit[i]=0,表示i数据不存在，bit[i]＝1，表示i数据存在。（循环1次1亿数据，不用比较数据大小） 3.最后找到bit数组中，bit[i]＝1且top100 i（循环1次） 方法2 建立一张数据库表，把上亿数据录入数据库，有索引的情况下，在上亿数据中找top100，也是很快的（不考虑数据录入数据库的时间） int[] nums = new int[100000000]; 内存溢出拉？ java int占32位 相当于4个字节 1亿个int占4亿个字节.... 4亿个字节 差不多相当于380M 能溢出？1G的内存就够用 第一种方法 看不懂 使用TreeSet感觉是最好解决方法拉(参考skzr.org的代码) 如果觉得内存会不够用的话 数据放到文件里面读取好拉 内存永远不会溢出 |
| 返回顶楼 | |
|
发表时间：2010-04-02
最后修改：2010-04-02
传个iterator进去吧。用数组构造就得100秒以上
这个算法是排重的。 如果不想排重就复杂了
public Iterator<Integer> naverEnd(){
return new Iterator<Integer>() {
int i =0;
private Random r = new Random();
public void remove() {}
public Integer next() {
i++;
if(i%10==0){
Math.abs(r.nextInt(200));
}
return Math.abs(r.nextInt(100));
}
public boolean hasNext() {
return i<1000000000;
}
};
}
public Set<Integer> getMax100(Iterator<Integer> it){
TreeSet<Integer> set = new TreeSet<Integer>();
int temp = 0;
while(it.hasNext()){
temp = it.next();
if(set.contains(temp)){
continue;
}else if(set.size()<RETURN_SIZE){
set.add(temp);
}else if(set.first()< temp){
set.remove(set.first());
set.add(temp);
}else{
/* do nothing */
}
}
return set;
}
|
| 返回顶楼 | |
|
发表时间：2010-04-02
joeycn 写道 请问这真的是道对亿级数据的排序题吗？
取一百个最大值而已的话，就没那么复杂了吧 先对头一百个数排序， 然后一个个比较，在最大值最小值之外的数直接抛弃，中间值参与二分查找法定位并替换 最后得到的就是要的东西了 应该是这个思路! |
| 返回顶楼 | |
|
发表时间：2010-04-02
做一个链表结构..左右链接.....等下给你代码
|
| 返回顶楼 | |
|
发表时间：2010-04-02
1亿个数据，单独用一种数据结构恐怕吃不消，我认为可以这样处理，让1个线程从文件或DB中读一定批量的数据，分配到N个队列，而每个队列有一个相应的线程进行排序，取前100，而每个线程处理好排序后把前N*100个交给另一个独立线程再去处理前100个的排序，有点归并排序的意味
|
| 返回顶楼 | |
|
发表时间：2010-04-02
Jameslyy 写道 joeycn 写道 请问这真的是道对亿级数据的排序题吗？
取一百个最大值而已的话，就没那么复杂了吧 先对头一百个数排序， 然后一个个比较，在最大值最小值之外的数直接抛弃，中间值参与二分查找法定位并替换 最后得到的就是要的东西了 应该是这个思路! ------------------------------------------ 有那么复杂吗？还扯什么多线程，引用这位的思路正解.昨晚上回家试了下，1亿数据502ms,奔腾T2330 CPU 1.6G,Linux JDK1.6. |
| 返回顶楼 | |
|
发表时间：2010-04-02
楼主这样做是不对的 ，数据量一大的话，直接内存溢出
|
| 返回顶楼 | |
|
发表时间：2010-04-02
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at Top100.main(Top100.java:62) 楼主的程序好像没有经过测试的 |
| 返回顶楼 | |
