精华帖 (0) :: 良好帖 (9) :: 新手帖 (15) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2010-12-06
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)); } } 速度果然很快 1千万数据 Sort begin... Spend time:266 不过再多的话我电脑就抛异常了,想来是内存不够了。。 java.lang.OutOfMemoryError: Java heap space |
|
返回顶楼 | |
发表时间:2010-12-07
题目有漏洞吧,这么大数据量数据源是什么?放内存?不可能吧,迟早会溢出的,一般用外排序,搞个B-tree什么的,翻翻数据结构的书就是了
|
|
返回顶楼 | |
发表时间:2010-12-09
luke_kai 写道 不可能吧,我写的那段程序,亿级的数据花销 2.3秒
Spend time:2375 数组值都是0,当然是这样咯。 |
|
返回顶楼 | |
发表时间:2010-12-09
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)); } } 如果有重复数据怎么办? |
|
返回顶楼 | |
发表时间:2011-03-16
楼主的排序时错误的。。。重复数据竟然没算
|
|
返回顶楼 | |
发表时间:2011-03-16
这题对于我初学者来说有点难度!!!
|
|
返回顶楼 | |
发表时间:2011-03-16
import java.util.ArrayList;
import java.util.List; import java.util.Random; public class GetTop100 { private static List<Integer> result = new ArrayList<Integer>(); /** * @param args */ public static void main(String[] args) { int count = 100000000; //要处理的数据量 int maxNumber = count; int inputArray[] = new int[count]; Random random = new Random(); for (int i = 0; i < count; ++i) { inputArray[i] = Math.abs(random.nextInt(maxNumber)); //随机生成的数组 } System.out.println("Sort begin..."); long current = System.currentTimeMillis(); getTop100(inputArray); System.out.println(System.currentTimeMillis() - current + " result:"+result.size()); for (int i = 0; i < result.size(); ++i) { System.out.print(result.get(i) + ","); } } private static void getTop100(int[] inputArray) { //得到前100的数据 for(int i = 0 ; i < inputArray.length ; i ++){ if(i < 100){ add(inputArray[i]);//前100个位自动插入 }else if(inputArray[i] > result.get(0)){ insert(inputArray[i]);//后面的为先删除再插入 } } } private static void insert(int value) { result.remove(0);//删除第一个 int index = result.size();//以下同添加 if(value > result.get(index-1)){ result.add(value); }else{ for(int i = 0 ; i < index ; i++){ if(value <= result.get(i)) { result.add(i, value); return; } } } } private static void add(int value) { int index = result.size(); if(result.size() == 0){ result.add(value); //当为第一个时直接添加 }else if(value > result.get(index-1)){ result.add(value); //当为最后一个,就是最大的时候,也直接添加 }else{ //在lsit中间,则要遍历查找要出入的地方 for(int i = 0 ; i < index ; i++){ if(value <= result.get(i)) { result.add(i, value); return; } } } } } 重新写的一个,解决了重复数据的问题。并且时间为两秒多一点点! |
|
返回顶楼 | |
发表时间:2011-03-17
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,也是很快的(不考虑数据录入数据库的时间) 我想问问,你的bit数组在java是如何构建的? |
|
返回顶楼 | |
发表时间:2011-03-17
paohui01 写道 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的代码) 如果觉得内存会不够用的话 数据放到文件里面读取好拉 内存永远不会溢出 4亿个字节只有380M!求怎么算的? |
|
返回顶楼 | |