|
精华帖 (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！求怎么算的？ |
| 返回顶楼 | |
