方法1：全部排序(适合大記憶體)
先利用快拍全部排序，在提取最大的1000個數。單機+單核+足夠大記憶體複雜度O(nlogn)。
方法2：局部淘汰法
先排序個10000個資料maxs數組，然後之後的資料和最小的相比較，大于最小的說明之前的最小值不是最大的10000個數。此時的時間複雜度為O(n+m^2)，其中m為容器的大小，即10000。在maxs數組插入新的資料之後的排序必須要優化，否則會造成很大的不必要的排序。
方法3：分治法 (适合小記憶體)
将一億個資料分為100分，沒分100萬資料。依次取每組的前10000大的資料，最後通過分治進行merge操作。
方法4：Hash法
沒接觸過
方法5：堆排序(最優)
思想類似于方法2，建構小根堆，剩下的元素和最小的(堆頂)進行比較，如果小于最小的，說明肯定不是最大的10000個數。 為什麼要建構小根堆？ 如果是大根堆的話，與堆頂元素的比較，不管是大于還是小于，都難以取舍，既不能判斷該數是否是10000個最大數之一。
show you the code //快排的代碼見第6題
package a_a_problems;
import Utils.ArrayUtils;
import g_quicksortupdate.QuickSort;
import g_quicksortupdate.QuickSort2;
import g_quicksortupdate.QuickSort33;
import java.util.Arrays;
public class Top10000 {
public static int[] top1000AllSort(int[]arr){
QuickSort33.quickSort(arr);
return Arrays.copyOf(arr, 10000);
}
public static int[] top1000First10000(int[] arr){
int index = 10000;
int[] maxs = Arrays.copyOf(arr, index);
QuickSort33.quickSort(maxs);//利用快排先将10000有序友善查找最小值與之後的數進行比較
for(int i = 10000;i
if(arr[i]>maxs[0]){
maxs[0] = arr[i];
//QuickSort33.quickSort(maxs);//如果用快排将會耗費大量的時間比較原本有序的序列，應該用優化過的插入排序
}
}
return maxs;
}
//方法2的改進，提高性能
public static int[] top1000First10000_2(int[] arr){
int index = 10000;
int[] maxs = Arrays.copyOf(arr, index);
QuickSort33.quickSort(maxs);
for(int i = 10000;i
if(arr[i]>maxs[0]){
maxs[0] = arr[i];
insertSort(maxs);//改進後的插入排序
}
}
return maxs;
}
//傳過來的除了第一個數之外都有序
private static void insertSort(int[] arr){
for(int i = 0;i
if(arr[i]>arr[i+1]){
int temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}else
break;
}
}
public static int[] top10000partition(int[]arr){
return fun(arr,0,arr.length-1);
}
private static int[] fun(int[]arr,int left,int right){
if (left + 1000000 <= right) {//100萬傳回前10000大的數組
QuickSort2.quickSort2(arr,left,right);
int l = right-left;
int[] m = new int[l];
for (int i = 0;i
m[i] = arr[left+i];
}
return m;
}else{
int[] maxs1 = fun(arr,left,left+1000000);
int[] maxs2 = fun(arr,left+1000001,right);
return merge(maxs1, maxs2);
}
}
//取兩個數組的前10000個資料
private static int[] merge(int[] arr1,int[] arr2){
int i = 0,a1 = 0,a2 = 0;
int[] mergemax = new int[10000];
while(i<10000){
if(arr1[a1]>arr2[a2]){
mergemax[i++] = arr1[a1++];
}
else{
mergemax[i++] = arr2[a2++];
}
}
return mergemax;
}
public static int[] top10000minHeap(int[] arr){
int[] maxs = new int[10000];
//建構小根堆，為什麼是小根堆，因為堆頂是最小的，插入的數如果比最小的還小，
// 肯定不是最大的10000之一。如果是大根堆，小于和大于堆頂沒有任何意義
maxs = Arrays.copyOf(arr,10000);
buildHeap(maxs);
//周遊數組進行插堆下濾，小于堆頂直接跳過，大于堆頂則插入
for(int i = 10000;i
if(arr[i]>maxs[0]){
maxs[0] = arr[i];
percDown(maxs,0);//重新建構小頂堆
}
}
//層級周遊堆
return maxs;
}
private static void buildHeap(int[] arr){
int len = arr.length;
for (int i = len/2;i>=0;i--){
percDown(arr,i);
}
}
//hole是需要下濾的元素的index而不是元素本身
private static void percDown(int[]arr,int hole){
int len = arr.length;
int insert = arr[hole];
int child;
for (;hole*2+1
child = hole*2+1;
if(child != len-1&&arr[child+1]
child++;
}
if(arr[child]
arr[hole] = arr[child];
}else
break;
}
arr[hole] = insert;
//此時的hole就是之前的child，如果跳進過循環，則hole==child。
// 如果沒有跳進過循環，則表示hole*2+1 = child會越界
}
public static void main(String[] args) {
int[] arr = ArrayUtils.arrGenerator(100000000, 10000000);
long start = System.nanoTime();
//int[] ints = top1000AllSort(arr);//14998ms
//int[] ints = top1000First10000(arr);//stackOverFlow，記憶體不夠用。因為多次快排進行了不必要的比較。
//int[] ints = top1000First10000_2(arr);//526ms
//int[] ints = top10000partition(arr);//16563ms，分治的效率并沒提高。
int[] ints = top10000minHeap(arr);//105ms 效率最高，輸出的資料并不單調，因為二叉堆同一層的元素大小關系并不确定，如果需要單調。
//可以使用帶下标和層數的層級周遊。
long end = System.nanoTime();
System.out.println(Arrays.toString(ints));
System.out.println(ArrayUtils.isMono(ints));
System.out.println("cost"+(end-start)/1000000+"ms");
}
}
實際運作： 實際上，最優的解決方案應該是最符合實際設計需求的方案，在時間應用中，可能有足夠大的記憶體，那麼直接将資料扔到記憶體中一次性處理即可，也可能機器有多個核，這樣可以采用多線程處理整個資料集。 下面針對不容的應用場景，分析了适合相應應用場景的解決方案。 (1)單機+單核+足夠大記憶體 如果需要查找10億個查詢次(每個占8B)中出現頻率最高的10個，考慮到每個查詢詞占8B，則10億個查詢次所需的記憶體大約是10^9 * 8B=8GB記憶體。如果有這麼大記憶體，直接在記憶體中對查詢次進行排序，順序周遊找出10個出現頻率最大的即可。這種方法簡單快速，使用。然後，也可以先用HashMap求出每個詞出現的頻率，然後求出頻率最大的10個詞。 (2)單機+多核+足夠大記憶體 這時可以直接在記憶體總使用Hash方法将資料劃分成n個partition，每個partition交給一個線程處理，線程的處理邏輯同(1)類似，最後一個線程将結果歸并。 該方法存在一個瓶頸會明顯影響效率，即資料傾斜。每個線程的處理速度可能不同，快的線程需要等待慢的線程，最終的處理速度取決于慢的線程。而針對此問題，解決的方法是，将資料劃分成c×n個partition(c>1)，每個線程處理完目前partition後主動取下一個partition繼續處理，知道所有資料處理完畢，最後由一個線程進行歸并。 (3)單機+單核+受限記憶體 這種情況下，需要将原資料檔案切割成一個一個小檔案，如次啊用hash(x)%M，将原檔案中的資料切割成M小檔案，如果小檔案仍大于記憶體大小，繼續采用Hash的方法對資料檔案進行分割，知道每個小檔案小于記憶體大小，這樣每個檔案可放到記憶體中處理。采用(1)的方法依次處理每個小檔案。 (4)多機+受限記憶體 這種情況，為了合理利用多台機器的資源，可将資料分發到多台機器上，每台機器采用(3)中的政策解決本地的資料。可采用hash+socket方法進行資料分發。
在大規模資料處理環境下，作業效率并不是首要考慮的問題，算法的擴充性和容錯性才是首要考慮的。是以上述方法中堆排序的方法最優。