使用 java 實作從保存了100億個整數的檔案里(每行為一個整數)，找出前100個最小的數。
uj5u.com熱心網友回復：
100億，假設一行只1個數字（也就是1位元組），也需要10*1000*1000*1000 約為 10G記憶體，所以全部讀如記憶體來排序估計夠嗆所以只能用外排序，最后多路歸并，找到前100個最小即可。
也就是先讀入大檔案的一部分資料，排好序，輸出到外部臨時小檔案，最后一起讀入這些臨時小檔案，一次從排好序的小檔案中取最小資料，被取出的最小資料的檔案指標繼續往后移，沒被取出資料的檔案指標保持在原來的位置，直到找出100個。最后再洗掉臨時檔案。
uj5u.com熱心網友回復：
分治法嗎uj5u.com熱心網友回復：
1.根據機器記憶體情況設定一次處理資料的存盤空間大小2.選取前100個資料作為初始的最小資料
3.對這100個資料按照從小到大進行排列
4.從一次性比較資料從選取資料，依次跟100個默認資料從后向前比較，當選取資料滿足比當前比較資料小，比位置靠前一位的比較資料大，則插入資料，將后面資料依次順延，舍掉最后一個資料
5.剩下的都是時間和電量的問題，左后得到100個最小的資料
uj5u.com熱心網友回復：
如果排序為主要的關注點，歸并排序是主要演算法uj5u.com熱心網友回復：
看錯了，你這只是尋找100個最小，所以不用排序，只需遍歷檔案找到前100個最小即可。弄個int[100] min的陣列，每讀取一個資料就跟min陣列的元素比較，如果比min的元素小就把讀出的資料插入陣列
比如前3個最小數不同的數
int array[] = {5, 8, 6, 7, 9, 4, 1, 3, 2, 0}; //找最小前3不同的數
int min[] = {0, 0, 0}; //
int i=0, j=0;
for (int k=0; k<array.length; k++) {
for (i=2; i>=0&&min[i]>array[k]; i--); //比較array[k]和min陣列
if (i<0) { //如果都比min陣列小，則插入第一個位置，陣列剩下元素往后挪
for (j=2; j>0; j--) min[j]=min[j-1];
min[0] = array[k];
} else if (i!=2&&min[i]!=array[k]) { //如果比某個位置小，并且在陣列中不存在，則插入該位置，該位置后面的元素往后挪
for (j=2; j>i+1; j--) min[j]=min[j-1];
min[i+1] = a;
}
}
for (i=0; i<3; i++)
printf("%d ", min[i]);基于這樣的演算法遍歷一邊檔案即可，只是檔案太大，可以考慮分割檔案或者用多執行緒讀檔案
給你寫個簡單的例子，你可以參考一下
public class Sample {
public static void main(String[] args) {
try {
String file = "D:/test.txt";
int threadCount = Runtime.getRuntime().availableProcessors(); //獲得可用的cpu，作為多執行緒的基數
int[][] buf = new int[threadCount][100]; //每個執行緒找出最小100個數（為了防止排他鎖降低性能，每個執行緒的資料域不干涉）
for (int i=0; i<threadCount; i++) {
Arrays.fill(buf[i], Integer.MAX_VALUE); //初始化每個執行緒的資料域
}
CountDownLatch countDown = new CountDownLatch(threadCount); //用于主程式等待執行緒，執行緒結束就會減1
//createTestFile(file, 10000);//生成測驗檔案
class minThread extends Thread { //執行緒類，多執行緒讀檔案
int id = 0; //用于分配資料域
long start = 0; //讀檔案開始
long end = 0; //讀檔案結束
public minThread(int id, long start, long end) {
this.id = id;
this.start = start;
this.end = end;
}
public void run() {
RandomAccessFile raf = null;
try {
raf = new RandomAccessFile(file, "r");
raf.seek(start); //移動到檔案讀取區域
while (start < end) { //從開始到結束位置依次讀取
String s = raf.readLine(); //一行一行讀入
if (s==null) break;
start += s.getBytes().length + 1;
if (s.isEmpty()) continue;
int n = Integer.valueOf(s), i=0; //找前100個數不同的最小數
for (i=99; i>=0 && buf[id][i]>n; i--);
if (i<0) {
for (int j=99; j>0; j--) buf[id][j]=buf[id][j-1];
buf[id][0] = n;
} else if (i!=99 && buf[id][i]!=n) {
for (int j=99; j>i+1; j--) buf[id][j]=buf[id][j-1];
buf[id][i+1] = n;
}
}
countDown.countDown(); //執行緒結束減1
} catch (Throwable e) {
e.printStackTrace();
} finally {
if (raf!=null) {
try {
raf.close();
} catch (Throwable ee) {
ee.printStackTrace();
}
}
}
}
}
RandomAccessFile raf = new RandomAccessFile(file, "r");
long totalLength = raf.length(); //檔案總長度
long offset = totalLength / threadCount;
long start = 0, end = 0;
for (int i=0, j=0; i<threadCount-1; i++) {
raf.seek(start+offset); //劃分檔案讀取區域
end = 0;
while ((j=raf.read()) != -1 && j!='\n') {
end++;
}
end += (start + offset + 1);
new minThread(i, start, end).start(); //分配讀取區域給執行緒
start = end + 1;
}
end = totalLength;
new minThread(threadCount-1, start, end).start();
raf.close();
countDown.await(); //等待執行緒結束
int[] min = new int[100]; //最終結果
int[] cur = new int[threadCount], idx = new int[threadCount];
Arrays.fill(cur, 0);
for (int i=0; i<100; i++) { //從每個執行緒的結果取前100個最小數
int tmp = buf[0][cur[0]]; //取其中一個數
Arrays.fill(idx, 0);
idx[0] = 1;//idx為1的表示被選中的資料，選中當前取的數
for (int j=1; j<threadCount; j++) { //分別比較每個陣列的結果
if (tmp>buf[j][cur[j]]) { //如果某個執行緒的結果更小，則重新記錄選中的數
tmp = buf[j][cur[j]];
Arrays.fill(idx, 0);
idx[j] = 1;
} else if (tmp == buf[j][cur[j]]) { //為了去掉重復資料，相等的也表示選中
idx[j] = 1;
}
}
min[i] = tmp; //保存最小的數
for (int j=0; j<threadCount; j++) { //每個執行緒的結果陣列的下標往后移，表示從該執行緒的結果的下一個數開始選
if (idx[j] != 0) cur[j]++;
}
}
System.out.println(Arrays.toString(min)); //列印結果
} catch (Throwable e) {
e.printStackTrace();
}
}
}
uj5u.com熱心網友回復：
受教了轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/141105.html
標籤：Java相關
上一篇：求助大佬