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

方案：

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

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

解决思路：

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

9 循环到文件读完为止

实现：

[java] view plain copy

public class Main {
public static void main(String[] args) {
int[] target = {12,4,3,56,11,122,131,312,2,3321,3,4,13,1,231,3,4,5,6,5,34,3};
int[] ary = new int[5];
int j=0;
MinHeap heap = new MinHeap();
for (int i = 0; i < target.length; i++) {
if(j<5){
ary[j]=target[i];
j++;
continue;
}
if(j==5){
heap.builtMinHeap(ary);
}
if(ary[0]
ary[0]=target[i];
heap.minHeapify(ary,0);
}
}
for (int i = 0; i < ary.length; i++) {
System.out.println(ary[i]);
}
}
}
class MinHeap {
@SuppressWarnings("unused")
private int parent(int i) {
if (i == 0)
return -1;
return i / 2;
}
private int left(int i) {
if (i == 0)
return 1;
return 2 * i;
}
private int right(int i) {
if (i == 0)
return 2;
return 2 * i + 1;
}
public void minHeapify(int[] ary, int i) {
int l = left(i);
int r = right(i);
int min = i;
if (l < ary.length) {
if (ary[l] < ary[i]) {
min = l;
}
}
if (r < ary.length) {
if (ary[r] < ary[min]) {
min = r;
}
}
if (min != i) {
int temp = ary[i];
ary[i] = ary[min];
ary[min] = temp;
minHeapify(ary, min);
}
}
public void builtMinHeap(int[] a) {
for (int i = (a.length - 1) / 2; i >= 0; i--) {
minHeapify(a, i);
}
}
}

用TreeSet实现：

[java] view plain copy

import java.util.Random;
import java.util.Set;
import java.util.TreeSet;
public class TestSF {
public static Set getTop100(int[] inputArray) {
TreeSet top100 = new TreeSet();
for (int i = 0; i < inputArray.length; i++) {
if (top100.size()<100){
top100.add(inputArray[i]);
}else if ((Integer)top100.first()
Object obj = top100.first();
top100.remove(obj);
top100.add(inputArray[i]);
}
}
return top100;
}
public static void main(String[] args) {
int numberCount = 30000000;
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 result = TestSF.getTop100(inputArray);
System.out.println("Spend time:"+(System.currentTimeMillis() - current));
}
}

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

ITPub博客

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

ITPub博客

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

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