ITPub博客

首页 > 大数据 > Hadoop > java一道面试题(大数据量 内存限制)

java一道面试题(大数据量 内存限制)

Hadoop 作者:pig78 时间:2013-07-05 18:06:15 0 删除 编辑


3000w数据的表,取某项字段前50项数据 ,内存2g

 

方案:

一个数据文件,有3000W行,每行有一个id号,文件内容无任何排序。
现在让你把id前 TOP 位取出来, TOP = 50.

要求:你的程序最多能吃2G的内存,其他不限,要求考虑io/cup最优。

解决思路:

1 建一个top_array, 长度为50.
2 再建一个buffer, 长度为2^20 (1G) 
3 循环开始
  读取文件到buffer,直到buffer满为止
  将Buffer的前50位读到top_array
  将top_array排序,按照id升序
  循环开始
     接着读取buffer的下一位
       如果比最后一个还大,next;
        否则,插入到top_array相应位置,并删除最后一个。
    循环到Buffer全部读完为止

循环到文件读完为止

 

实现:

  1. public class Main  
  2.     public static void main(String[] args)  
  3.         int[] target {12,4,3,56,11,122,131,312,2,3321,3,4,13,1,231,3,4,5,6,5,34,3};  
  4.         int[] ary new int[5];  
  5.         int j=0 
  6.         MinHeap heap new MinHeap();  
  7.         for (int 0target.length; i++)  
  8.             if(j<5){  
  9.                 ary[j]=target[i];  
  10.                 j++;  
  11.                 continue 
  12.              
  13.             if(j==5){  
  14.                 heap.builtMinHeap(ary);  
  15.              
  16.             if(ary[0] 
  17.                 ary[0]=target[i];  
  18.                 heap.minHeapify(ary,0);  
  19.              
  20.          
  21.         for (int 0ary.length; i++)  
  22.             System.out.println(ary[i]);  
  23.          
  24.      
  25.  
  26. class MinHeap  
  27.     @SuppressWarnings("unused" 
  28.     private int parent(int i)  
  29.         if (i == 0 
  30.             return -1 
  31.         return 2 
  32.      
  33.     private int left(int i)  
  34.         if (i == 0 
  35.             return 1 
  36.         return 2 i;  
  37.      
  38.     private int right(int i)  
  39.         if (i == 0 
  40.             return 2 
  41.         return 2 1 
  42.      
  43.     public void minHeapify(int[] ary, int i)  
  44.         int left(i);  
  45.         int right(i);  
  46.         int min i;  
  47.         if (l ary.length)  
  48.             if (ary[l] ary[i])  
  49.                 min l;  
  50.              
  51.          
  52.         if (r ary.length)  
  53.             if (ary[r] ary[min])  
  54.                 min r;  
  55.              
  56.          
  57.         if (min != i)  
  58.             int temp ary[i];  
  59.             ary[i] ary[min];  
  60.             ary[min] temp;  
  61.             minHeapify(ary, min);  
  62.          
  63.      
  64.     public void builtMinHeap(int[] a)  
  65.         for (int (a.length 12>= 0i--)  
  66.             minHeapify(a, i);  
  67.          
  68.      
  69.  
 

 

用TreeSet实现:

 

  1. import java.util.Random;   
  2. import java.util.Set;   
  3. import java.util.TreeSet;   
  4. public class TestSF   
  5. public static Set getTop100(int[] inputArray)   
  6. TreeSet top100 new TreeSet();   
  7. for (int 0inputArray.length; i++)   
  8. if (top100.size()<100){   
  9. top100.add(inputArray[i]);   
  10. }else if ((Integer)top100.first()  
  11. Object obj top100.first();   
  12. top100.remove(obj);   
  13. top100.add(inputArray[i]);   
  14.   
  15.   
  16. return top100;   
  17.   
  18. public static void main(String[] args)   
  19. int numberCount 30000000  
  20. int maxNumber numberCount;   
  21. int inputArray[] new int[numberCount];   
  22. Random random new Random();   
  23. for (int 0numberCount; ++i)   
  24. inputArray[i] Math.abs(random.nextInt(maxNumber));   
  25.   
  26. System.out.println("Sort begin...");   
  27. long current System.currentTimeMillis();   
  28. Set result TestSF.getTop100(inputArray);   
  29. System.out.println("Spend time:"+(System.currentTimeMillis() current));   
  30.   
  31.   
  32.  

http://blog.csdn.net/mudalu626/article/details/6409805

<!-- 正文结束 -->

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/21794229/viewspace-1120446/,如需转载,请注明出处,否则将追究法律责任。

上一篇: 没有了~
下一篇: 没有了~
请登录后发表评论 登录
全部评论

注册时间:2009-06-01