`
hikelee
  • 浏览: 7701 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
最近访客 更多访客>>
文章分类
社区版块
存档分类
最新评论

一道腾讯面试题:从大量数字中取出 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亿数据时,机子几乎就没有反应了,这可能是物理内存已经耗尽,用虚拟内存了.

 

欢迎交流!

分享到:
评论
99 楼 liuxuejin 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!求怎么算的?
98 楼 liuxuejin 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是如何构建的?
97 楼 jeho0815 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;
}
}
}



}

}
重新写的一个,解决了重复数据的问题。并且时间为两秒多一点点!
96 楼 沙舟狼客 2011-03-16  
这题对于我初学者来说有点难度!!!
95 楼 jeho0815 2011-03-16  
楼主的排序时错误的。。。重复数据竟然没算
94 楼 chenyongxin 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));


}

}

如果有重复数据怎么办?
93 楼 pengmj 2010-12-09  
luke_kai 写道
不可能吧,我写的那段程序,亿级的数据花销 2.3秒
Spend time:2375

数组值都是0,当然是这样咯。
92 楼 sunnyfun 2010-12-07  
题目有漏洞吧,这么大数据量数据源是什么?放内存?不可能吧,迟早会溢出的,一般用外排序,搞个B-tree什么的,翻翻数据结构的书就是了
91 楼 请输入用户名 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
90 楼 fairplay 2010-05-29  
public class findValue {
	
	public static void main(String[] args){
			
		int max = 10000*10000;
		int length=100;
		int ints[] = new int[max];
		Random random = new Random();
		for (int i=0;i<max;i++) {
			ints[i]=Math.abs(random.nextInt(max));
		}
		List<Integer> list = new ArrayList();

		long start = System.currentTimeMillis();
		int size=0;
		int value=0;
		list.add(ints[0]);
		for(int i=1;i<max;i++){
			value=ints[i];
			size=list.size();
			if(value<list.get(size-1)){
				if(size<length){
					list.add(value);
				}
				continue;
			}else if(value>list.get(0)){
				list.add(0,value);
				if(size==length){
					list.remove(size);
				}
				continue;
			}
			
			for(int j=0;j<size;j++){
				if(value>list.get(j)){
                                              //如果不需要排除重复数字,则去掉该判断
					if(j>0&&value!=list.get(j-1)){
						list.add(j,value);
						if(size==length){
						  list.remove(size);
						}
					}
					break;
				}
			 }
		}
		
		System.out.println("time:"+(System.currentTimeMillis()-start));
		
		System.out.println(list);
		TreeSet<Integer> set = new TreeSet();
		set.addAll(list);
		
		System.out.println(set.size()+":"+list.size());
		if(set.size()!=list.size()){
			System.out.println("error");
		}
		int i=0;
		for(Iterator<Integer> it=set.iterator();it.hasNext();){
			value=it.next();
			System.out.println(value+":"+list.get(list.size()-1-i));
			if(value!=list.get(list.size()-1-i)){
				System.out.println("error");
				break;
			}
			i++;
		}
	}
}


E2160 3G
time:2453
89 楼 qyhdt 2010-05-29  
路过一次看看而已
88 楼 lzj0470 2010-05-28  
int max = 100000000;
BitSet bset = new BitSet(max);
Random random = new Random(); 
for(int i=0;i<max;i++){
bset.set(Math.abs(random.nextInt(max)));
}
System.out.println("加载完毕!");
long lo = System.currentTimeMillis();
int[] top100 = new int[100];
int location = 0;
for(int i=max;i>=0;i--){
boolean bool = bset.get(i);
if(location==100){
break;
}
if(bool){
top100[location] = i;
location++;
}
}
System.out.println("花费:"+(System.currentTimeMillis()-lo));
for(int i=0;i<100;i++){
System.out.println(top100[i]);
}
这样才对。
87 楼 lzj0470 2010-05-28  
int max = 100000000;
BitSet bset = new BitSet(max);
Random random = new Random(); 
for(int i=0;i<max;i++){
bset.set(Math.abs(random.nextInt(max)));
}
System.out.println("加载完毕!");
long lo = System.currentTimeMillis();
int[] top100 = new int[100];
int location = 0;
for(int i=0;i<max;i++){
boolean bool = bset.get(i);
if(location==100){
break;
}
if(bool){
top100[location] = i;
location++;
}
}
System.out.println("花费:"+(System.currentTimeMillis()-lo));
for(int i=0;i<100;i++){
System.out.println(top100[i]);
}
花费:0
86 楼 Curapica 2010-04-10  
编程之美上的一道题目
85 楼 millton 2010-04-07  
TreeSet<Integer> set = new TreeSet<Integer>();
List<Integer> lst = new ArrayList<Integer>();
int numberCount = 1000000000;
int maxNumber = numberCount;
Random random = new Random();
for (int i = 0; i < numberCount; i++) {
int randomInt = random.nextInt(maxNumber);
Integer inte = new Integer(randomInt);
if (set.contains(inte))
{
lst.add(inte);
}
if (set.size() < 100)
{
set.add(inte);
}
else
{
if (set.first().intValue() < randomInt)
{
set.remove(set.first());
set.add(randomInt);
}
}
}

Iterator iterator = set.iterator();
while(iterator.hasNext()) {
lst.add((Integer)iterator.next());
}

Collections.sort(lst);
for (int i = 0; i < 100; i++)
{
System.out.println(i + ":" + lst.get(lst.size() - i - 1));
}

这段代码貌似十几秒就可以了,每1KW用时不到2S。
84 楼 colorless 2010-04-07  
应该用MapReduce的方式来更好吧
83 楼 willamsccd 2010-04-07  
楼上的代码有问题
82 楼 ansjsun 2010-04-02  
import java.util.Arrays;
import java.util.Random;

public class Top100 {
private static Node head = null;
private static Node end = null;
private static Node tempNode = null;
private static Node node = null;

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

int result[] = new int[100];
int k = 100;
if (inputArray.length < 100) {
k = inputArray.length;
}
for (int i = 0; i < 100; ++i) {
result[i] = inputArray[i];
}

Arrays.sort(result);

for (int i = k - 1; i >= 0; i--) {
node = new Node(result[i], tempNode);
if (i == k - 1) {
head = node;
} else {
tempNode.right = node;
}
if (i == 0) {
end = node;
}else{
tempNode = node;
}
}
tempNode = end ;


for (int i = 100; i < inputArray.length; i++) {
int tempValue = inputArray[i];
if (tempValue <= end.value) {
continue;
}else{
tempNode = end;
setValue(inputArray[i]) ;
}
}

for (int i = 0; i < 100; i++) {
if (i == 0) {
node = head;
} else {
node = node.right;
}
result[i] = node.value;
}

return result;

}

private static void setValue(int tempValue) {
if (tempNode.value < tempValue) {
tempNode = tempNode.left;
//最大的
if(tempNode==null){
node = new Node(head,tempValue );
head.left = node ;
head = node ;
removeEnd() ;
}else{
setValue(tempValue);
}
} else if (tempNode.value != tempValue) {
node = new Node(tempValue, tempNode);
//要替代end
if(tempNode.right==end){
end.left.right = node ;
end = node ;
}else{
try {
tempNode.right.left = node;
} catch (Exception e) {
// TODO Auto-generated catch block
System.err.println(tempNode.right) ;
e.printStackTrace() ;
System.exit(0) ;
}
tempNode.right = node;
removeEnd() ;
}
}
}

private static void removeEnd(){
end = end.left ;
end.right = null ;
}

public static void main(String[] args) {

int numberCount = 1000000;

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 + "ms");

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

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

}

}

}

class Node {
protected int value;
protected Node left;
protected Node right;

public Node(int value) {
this.value = value;
}

public Node(int value, Node left) {
this.value = value;
this.left = left;
}

public Node(Node right, int value) {
this.right = right;
this.value = value;
}
}
81 楼 chunquedong 2010-04-02  
构造100大的数组A,循环放其他的数字。
数组A越来越接近最后要的100个大数,所以后面的插进来的数字小于数组最小值的概略最大,大于数组最大值的概略最小。这样倒着往上比较,插入到合适的位置,然后删除最小值。

纯属理论分析。也许最小顶堆最靠谱!
------------------------------------------
说一下楼主的方法,实际上是基数排序的变种,所需空间取决于给定数字中的最大值,如果遇见一个long型的大数字估计就死了。还有楼主没有统计重复数字。
80 楼 pclfs1983 2010-04-02  
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at Top100.main(Top100.java:62)

楼主的程序好像没有经过测试的

相关推荐

Global site tag (gtag.js) - Google Analytics