青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

posts - 200, comments - 8, trackbacks - 0, articles - 0

                     程序員編程藝術：第三章續、Top K算法問題的實現


    作者：July，zhouzhenren，yansha。
    致謝：微軟100題實現組，狂想曲創作組。
    時間：2011年05月08日
    微博：http://weibo.com/julyweibo 。
    出處：http://blog.csdn.net/v_JULY_v 。
    wiki：http://tctop.wikispaces.com/。
-----------------------------------------------

 

前奏
    在上一篇文章，程序員面試題狂想曲：第三章、尋找最小的k個數中，后來為了論證類似快速排序中partition的方法在最壞情況下，能在O（N）的時間復雜度內找到最小的k個數，而前前后后updated了10余次。所謂功夫不負苦心人，終于得到了一個想要的結果。

    簡單總結如下（詳情，請參考原文第三章）：
    1、RANDOMIZED-SELECT，以序列中隨機選取一個元素作為主元，可達到線性期望時間O（N）的復雜度。
    2、SELECT，快速選擇算法，以序列中“五分化中項的中項”，或“中位數的中位數”作為主元（樞紐元），則不容置疑的可保證在最壞情況下亦為O（N）的復雜度。

    本章，咱們來闡述尋找最小的k個數的反面，即尋找最大的k個數，但此刻可能就有讀者質疑了，尋找最大的k個數和尋找最小的k個數，原理不是一樣的么?

    是的，的確是一樣，但這個尋找最大的k個數的問題的實用范圍更廣，因為它牽扯到了一個Top K算法問題，以及有關搜索引擎，海量數據處理等廣泛的問題，所以本文特意對這個Top K算法問題，進行闡述以及實現（側重實現，因為那樣看起來，會更令人激動人心），算是第三章的續。ok，有任何問題，歡迎隨時不吝指正。謝謝。

 

說明

      關于尋找最小K個數能做到最壞情況下為O（N）的算法及證明，請參考原第三章，尋找最小的k個數，本文的代碼不保證O（N）的平均時間復雜度，只是根據第三章有辦法可以做到而已（如上面總結的，2、SELECT，快速選擇算法，以序列中“五分化中項的中項”，或“中位數的中位數”作為主元或樞紐元的方法，原第三章已經嚴格論證并得到結果）。

 

第一節、尋找最小的第k個數

     在進入尋找最大的k個數的主題之前，先補充下關于尋找最k小的數的三種簡單實現。由于堆的完整實現，第三章：第五節，堆結構實現，處理海量數據中已經給出，下面主要給出類似快速排序中partition過程的代碼實現：

尋找最小的k個數，實現一（下段代碼經本文評論下多位讀者指出有問題：當a [ i ]=a [ j ]=pivot時，則會產生一個無限循環，在Mark Allen Weiss的數據結構與算法分析C++描述中文版的P209-P210有描述，讀者可參看之。特此說明，因本文代碼存在問題的地方還有幾處，故請待后續統一修正.2012.08.21）：

  1. //copyright@ mark allen weiss && July && yansha  
  2. //July，yansha、updated，2011.05.08.  
  3.   
  4. //本程序，后經飛羽找出錯誤，已經修正。  
  5. //隨機選取樞紐元，尋找最小的第k個數  
  6. #include <iostream>  
  7. #include <stdlib.h>  
  8. using namespace std;  
  9.   
  10. int my_rand(int low, int high)  
  11. {  
  12.     int size = high - low + 1;  
  13.     return  low + rand() % size;   
  14. }  
  15.   
  16. //q_select places the kth smallest element in a[k]  
  17. int q_select(int a[], int k, int left, int right)  
  18. {  
  19.     if(k>right)  
  20.     {  
  21.         cout<<"---------"<<endl;   //為了處理當k大于數組中元素個數的異常情況  
  22.         return false;  
  23.     }  
  24.   
  25.     //真正的三數中值作為樞紐元方法，關鍵代碼就是下述六行  
  26.     int midIndex = (left + right) / 2;  
  27.     if(a[left] < a[midIndex])  
  28.         swap(a[left], a[midIndex]);  
  29.     if(a[right] < a[midIndex])  
  30.         swap(a[right], a[midIndex]);  
  31.     if(a[right] < a[left])  
  32.         swap(a[right], a[left]);  
  33.     swap(a[midIndex], a[right]);  
  34.   
  35.     int pivot = a[right];   //之前是int pivot = right，特此，修正。  
  36.       
  37.     // 申請兩個移動指針并初始化  
  38.     int i = left;   
  39.     int j = right-1;    
  40.       
  41.     // 根據樞紐元素的值對數組進行一次劃分  
  42.     for (;;)   
  43.     {    
  44.         while(a[i] < pivot)  
  45.             i++;  
  46.         while(a[j] > pivot)  
  47.             j--;  
  48.         if (i < j)   
  49.             swap(a[i], a[j]);   
  50.         else     
  51.             break;     
  52.     }  
  53.     swap(a[i], a[right]);   
  54.       
  55.     /* 對三種情況進行處理：(m = i - left + 1) 
  56.     1、如果m=k，即返回的主元即為我們要找的第k小的元素，那么直接返回主元a[i]即可; 
  57.     2、如果m>k，那么接下來要到低區間A[0....m-1]中尋找，丟掉高區間; 
  58.     3、如果m<k，那么接下來要到高區間A[m+1...n-1]中尋找，丟掉低區間。 
  59.     */  
  60.     int m = i - left + 1;  
  61.     if (m == k)  
  62.     {  
  63.         cout<<a[i]<<endl;  
  64.         for(i-=1;i>=0;i--)  
  65.             cout<<a[i]<<endl;  
  66.     }  
  67.     else if(m > k)   
  68.         return q_select(a, k, left, i - 1);    
  69.     else    
  70.         return q_select(a, k - m, i + 1, right);  
  71. }  
  72.   
  73. int main()  
  74. {  
  75.     int i;  
  76.     int a[] = {7, 8, 9, 54, 6, 4, 11, 1, 2, 33};  
  77.     q_select(a, 4, 0, sizeof(a) / sizeof(int) - 1);  
  78.     return 0;  
  79. }  
     尋找最小的第k個數，實現二：

 

  1. //copyright@ July  
  2. //yansha、updated，2011.05.08。  
  3. // 數組中尋找第k小元素，實現二  
  4. #include <iostream>  
  5. using namespace std;  
  6.   
  7. const int numOfArray = 10;  
  8.   
  9. // 這里并非真正隨機  
  10. int my_rand(int low, int high)  
  11. {  
  12.     int size = high - low + 1;  
  13.     return low + rand() % size;   
  14. }  
  15.   
  16. // 以最末元素作為主元對數組進行一次劃分  
  17. int partition(int array[], int left, int right)      
  18. {                              
  19.     int pos = right;  
  20.     for(int index = right - 1; index >= left; index--)  
  21.     {  
  22.         if(array[index] > array[right])  
  23.             swap(array[--pos], array[index]);  
  24.     }  
  25.     swap(array[pos], array[right]);  
  26.     return pos;  
  27. }  
  28.   
  29. // 隨機快排的partition過程   
  30. int random_partition(int array[], int left, int right)          
  31. {  
  32.     // 隨機從范圍left到right中取一個值作為主元  
  33.     int index = my_rand(left, right);                          
  34.     swap(array[right], array[index]);      
  35.       
  36.     // 對數組進行劃分，并返回主元在數組中的位置  
  37.     return partition(array, left, right);                   
  38. }  
  39.   
  40. // 以線性時間返回數組array[left...right]中第k小的元素  
  41. int random_select(int array[], int left, int right, int k)      
  42. {  
  43.     // 處理異常情況  
  44.     if (k < 1 || k > (right - left + 1))  
  45.         return -1;  
  46.       
  47.     // 主元在數組中的位置  
  48.     int pos = random_partition(array, left, right);       
  49.       
  50.     /* 對三種情況進行處理：(m = i - left + 1) 
  51.     1、如果m=k，即返回的主元即為我們要找的第k小的元素，那么直接返回主元array[i]即可; 
  52.     2、如果m>k，那么接下來要到低區間array[left....pos-1]中尋找，丟掉高區間; 
  53.     3、如果m<k，那么接下來要到高區間array[pos+1...right]中尋找，丟掉低區間。 
  54.     */  
  55.     int m = pos - left + 1;  
  56.     if(m == k)  
  57.         return array[pos];                               
  58.     else if (m > k)         
  59.         return random_select(array, left, pos - 1, k);  
  60.     else   
  61.         return random_select(array, pos + 1, right, k - m);  
  62. }  
  63.   
  64. int main()  
  65. {      
  66.     int array[numOfArray] = {7, 8, 9, 54, 6, 4, 2, 1, 12, 33};  
  67.     cout << random_select(array, 0, numOfArray - 1, 4) << endl;  
  68.     return 0;  
  69. }  

 

尋找最小的第k個數，實現三：

  1. //求取無序數組中第K個數，本程序樞紐元的選取有問題，不作推薦。    
  2. //copyright@ 飛羽   
  3. //July、yansha，updated，2011.05.18。     
  4. #include <iostream>    
  5. #include <time.h>   
  6. using namespace std;     
  7.   
  8. int kth_elem(int a[], int low, int high, int k)     
  9. {     
  10.     int pivot = a[low];    
  11.     //這個程序之所以做不到O（N）的最最重要的原因，就在于這個樞紐元的選取。           
  12.     //而這個程序直接選取數組中第一個元素作為樞紐元，是做不到平均時間復雜度為 O（N）的。  
  13.       
  14.     //要 做到，就必須 把上面選取樞紐元的 代碼改掉，要么是隨機選擇數組中某一元素作為樞紐元，能達到線性期望的時間  
  15.     //要么是選取數組中中位數的中位數作為樞紐元，保證最壞情況下，依然為線性O（N）的平均時間復雜度。  
  16.     int low_temp = low;     
  17.     int high_temp = high;     
  18.     while(low < high)     
  19.     {     
  20.         while(low < high && a[high] >= pivot)       
  21.             --high;     
  22.         a[low] = a[high];     
  23.         while(low < high && a[low] < pivot)     
  24.             ++low;     
  25.         a[high] = a[low];     
  26.     }     
  27.     a[low] = pivot;     
  28.       
  29.     //以下就是主要思想中所述的內容     
  30.     if(low == k - 1)      
  31.         return a[low];     
  32.     else if(low > k - 1)      
  33.         return kth_elem(a, low_temp, low - 1, k);     
  34.     else      
  35.         return kth_elem(a, low + 1, high_temp, k);     
  36. }     
  37.   
  38. int main()   //以后盡量不再用隨機產生的數組進行測試，沒多大必要。  
  39. {  
  40.     for (int num = 5000; num < 50000001; num *= 10)  
  41.     {  
  42.         int *array = new int[num];  
  43.           
  44.         int j = num / 10;  
  45.         int acc = 0;  
  46.         for (int k = 1; k <= num; k += j)  
  47.         {  
  48.             // 隨機生成數據  
  49.             srand(unsigned(time(0)));  
  50.             for(int i = 0; i < num; i++)     
  51.                 array[i] = rand() * RAND_MAX + rand();      
  52.             //”如果數組本身就是利用隨機化產生的話，那么選擇其中任何一個元素作為樞軸都可以看作等價于隨機選擇樞軸，  
  53.             //（雖然這不叫隨機選擇樞紐）”，這句話，是完全不成立的，是錯誤的。  
  54.               
  55.             //“因為你總是選擇 隨機數組中第一個元素 作為樞紐元，不是 隨機選擇樞紐元”  
  56.             //相當于把上面這句話中前面的 “隨機” 兩字去掉，就是：  
  57.             //因為 你總是選擇數組中第一個元素作為樞紐元，不是 隨機選擇樞紐元。  
  58.             //所以，這個程序，始終做不到平均時間復雜度為O（N）。  
  59.               
  60.             //隨機數組和給定一個非有序而隨機手動輸入的數組，是一個道理。稍后，還將就程序的運行結果繼續解釋這個問題。  
  61.             //July、updated，2011.05.18。  
  62.               
  63.             // 計算一次查找所需的時鐘周期數  
  64.             clock_t start = clock();  
  65.             int data = kth_elem(array, 0, num - 1, k);  
  66.             clock_t end = clock();  
  67.             acc += (end - start);  
  68.         }  
  69.         cout << "The average time of searching a date in the array size of " << num << " is " << acc / 10 << endl;  
  70.     }  
  71.     return 0;     
  72. }    
   測試：
The average time of searching a date in the array size of 5000 is 0
The average time of searching a date in the array size of 50000 is 1
The average time of searching a date in the array size of 500000 is 12
The average time of searching a date in the array size of 5000000 is 114
The average time of searching a date in the array size of 50000000 is 1159
Press any key to continue

 

通過測試這個程序，我們竟發現這個程序的運行時間是線性的?
或許，你還沒有意識到這個問題，ok，聽我慢慢道來。
我們之前說，要保證這個算法是線性的，就一定要在樞紐元的選取上下足功夫：
1、要么是隨機選取樞紐元作為劃分元素
2、要么是取中位數的中位數作為樞紐元劃分元素
 
現在，這程序直接選取了數組中第一個元素作為樞紐元
竟然，也能做到線性O（N）的復雜度，這不是自相矛盾么?
你覺得這個程序的運行時間是線性O（N），是巧合還是確定會是如此?

哈哈，且看1、@well：根據上面的運行結果不能判斷線性，如果人家是O(n^1.1) 也有可能啊，而且部分數據始終是擬合，還是要數學證明才可靠。2、@July：同時，隨機數組中選取一個元素作為樞紐元！=> 隨機數組中隨機選取一個元素作為樞紐元（如果是隨機選取隨機數組中的一個元素作為主元，那就不同了，跟隨機選取數組中一個元素作為樞紐元一樣了）。3、@飛羽：正是因為數組本身是隨機的，所以選擇第一個元素和隨機選擇其它的數是等價的（由等概率產生保證），這第3點，我與飛羽有分歧，至于誰對誰錯，待時間讓我考證。

關于上面第3點我和飛羽的分歧，在我們進一步討論之后，一致認定（不過，相信，你看到了上面程序更新的注釋之后，你應該有幾分領會了）：

  1. 我們說輸入一個數組的元素，不按其順序輸入：如，1,2,3,4,5,6,7，而是這樣輸入：5,7,6,4,3，1,2，這就叫隨機輸入，而這種情況就相當于上述程序主函數中所產生的隨機數組。然而選取隨機輸入的數組或隨機數組中第一個元素作為主元，我們不能稱之為說是隨機選取樞紐元。
  2. 因為，隨機數產生器產生的數據是隨機的，沒錯，但你要知道，你總是選取隨機數組的第一個元素作為樞紐元，這不叫隨機選取樞紐元。
  3. 所以，上述程序的主函數中隨機產生的數組對這個程序的算法而言，沒有任何意義，就是幫忙產生了一個隨機數組，幫助我們完成了測試，且方便我們測試大數據量而已，就這么簡單。
  4. 且一般來說，我們看一個程序的 時間復雜度，是不考慮 其輸入情況的，即不考慮主函數，正如這個 kth number 的程序所見，你每次都是隨機選取數組中第一個元素作為樞紐元，而并不是隨機選擇樞紐元，所以，做不到平均時間復雜度為O（N）。 

所以：想要保證此快速選擇算法為O（N）的復雜度，只有兩種途徑，那就是保證劃分的樞紐元元素的選取是：
1、隨機的（注，此樞紐元隨機不等同于數組隨機）
2、五分化中項的中項，或中位數的中位數。

所以，雖然咱們對于一切心知肚明，但上面程序的運行結果說明不了任何問題，這也從側面再次佐證了咱們第三章中觀點的正確無誤性。 

updated：

    非常感謝飛羽等人的工作，將上述三個版本綜合到了一起（待進一步測試）：

  1. ///下面的代碼對July博客中的三個版本代碼進行重新改寫。歡迎指出錯誤。  
  2. ///先把它們貼在這里，還要進行隨機化數據測試。待發...  
  3.   
  4. //modified by 飛羽 at 2011.5.11  
  5. /////Top_K_test  
  6.   
  7. //修改了下命名規范，July、updated，2011.05.12。  
  8. #include <iostream>  
  9. #include <stdlib.h>  
  10. using namespace std;  
  11.   
  12. inline int my_rand(int low, int high)  
  13. {  
  14.     int size = high - low + 1;  
  15.     return  low + rand() % size;  
  16. }  
  17.   
  18. int partition(int array[], int left, int right)  
  19. {  
  20.     int pivot = array[right];  
  21.     int pos = left-1;  
  22.     for(int index = left; index < right; index++)  
  23.     {  
  24.         if(array[index] <= pivot)  
  25.             swap(array[++pos], array[index]);  
  26.     }  
  27.     swap(array[++pos], array[right]);  
  28.     return pos;//返回pivot所在位置  
  29. }  
  30.   
  31. bool median_select(int array[], int left, int right, int k)  
  32. {  
  33.     //第k小元素，實際上應該在數組中下標為k-1  
  34.     if (k-1 > right || k-1 < left)     
  35.         return false;  
  36.   
  37.     //真正的三數中值作為樞紐元方法，關鍵代碼就是下述六行  
  38.     int midIndex=(left+right)/2;  
  39.     if(array[left]<array[midIndex])  
  40.         swap(array[left],array[midIndex]);  
  41.     if(array[right]<array[midIndex])  
  42.         swap(array[right],array[midIndex]);  
  43.     if(array[right]<array[left])  
  44.         swap(array[right],array[left]);  
  45.     swap(array[midIndex], array[right]);  
  46.       
  47.     int pos = partition(array, left, right);  
  48.       
  49.     if (pos == k-1)  
  50.         return true;  
  51.     else if (pos > k-1)  
  52.         return median_select(array, left, pos-1, k);  
  53.     else return median_select(array, pos+1, right, k);  
  54. }  
  55.   
  56. bool rand_select(int array[], int left, int right, int k)  
  57. {  
  58.     //第k小元素，實際上應該在數組中下標為k-1  
  59.     if (k-1 > right || k-1 < left)     
  60.         return false;  
  61.   
  62.     //隨機從數組中選取樞紐元元素  
  63.     int Index = my_rand(left, right);  
  64.     swap(array[Index], array[right]);  
  65.       
  66.     int pos = partition(array, left, right);  
  67.       
  68.     if (pos == k-1)  
  69.         return true;  
  70.     else if (pos > k-1)  
  71.         return rand_select(array, left, pos-1, k);  
  72.     else return rand_select(array, pos+1, right, k);  
  73. }  
  74.   
  75. bool kth_select(int array[], int left, int right, int k)  
  76. {  
  77.     //直接取最原始的劃分操作  
  78.     if (k-1 > right || k-1 < left)     
  79.         return false;  
  80.   
  81.     int pos = partition(array, left, right);  
  82.     if(pos == k-1)  
  83.         return true;  
  84.     else if(pos > k-1)  
  85.         return kth_select(array, left, pos-1, k);  
  86.     else return kth_select(array, pos+1, right, k);  
  87. }  
  88.   
  89. int main()  
  90. {  
  91.     int array1[] = {7, 8, 9, 54, 6, 4, 11, 1, 2, 33};   
  92.     int array2[] = {7, 8, 9, 54, 6, 4, 11, 1, 2, 33};   
  93.     int array3[] = {7, 8, 9, 54, 6, 4, 11, 1, 2, 33};   
  94.       
  95.     int numOfArray = sizeof(array1) / sizeof(int);  
  96.     for(int i=0; i<numOfArray; i++)  
  97.         printf("%d/t",array1[i]);  
  98.       
  99.     int K = 9;  
  100.     bool flag1 = median_select(array1, 0, numOfArray-1, K);  
  101.     bool flag2 = rand_select(array2, 0, numOfArray-1, K);  
  102.     bool flag3 = kth_select(array3, 0, numOfArray-1, K);  
  103.     if(!flag1)   
  104.         return 1;  
  105.     for(i=0; i<K; i++)  
  106.         printf("%d/t",array1[i]);  
  107.     printf("/n");  
  108.       
  109.     if(!flag2)   
  110.         return 1;  
  111.     for(i=0; i<K; i++)  
  112.         printf("%d/t",array2[i]);  
  113.     printf("/n");  
  114.       
  115.     if(!flag3)   
  116.         return 1;  
  117.     for(i=0; i<K; i++)  
  118.         printf("%d/t",array3[i]);  
  119.     printf("/n");  
  120.       
  121.     return 0;  
  122. }  

 

    說明：@飛羽：因為預先設定了K，經過分割算法后，數組肯定被劃分為array[0...k-1]和array[k...length-1]，注意到經過Select_K_Version操作后，數組是被不斷地分割的，使得比array[k-1]的元素小的全在左邊，題目要求的是最小的K個元素，當然也就是array[0...k-1]，所以輸出的結果就是前k個最小的數：

7       8       9       54      6       4       11      1       2       33
4       1       2       6       7       8       9       11      33
7       6       4       1       2       8       9       11      33
7       8       9       6       4       11      1       2       33
Press any key to continue

（更多，請參見：此狂想曲系列tctop修訂wiki頁面：http://tctop.wikispaces.com/）


第二節、尋找最大的k個數
把之前第三章的問題，改幾個字，即成為尋找最大的k個數的問題了，如下所述：
查找最大的k個元素
題目描述：輸入n個整數，輸出其中最大的k個。
例如輸入1，2，3，4，5，6，7和8這8個數字，則最大的4個數字為8，7，6和5。

    分析：由于尋找最大的k個數的問題與之前的尋找最小的k個數的問題，本質是一樣的，所以，這里就簡單闡述下思路，ok，考驗你舉一反三能力的時間到了：

    1、排序，快速排序。我們知道，快速排序平均所費時間為n*logn，從小到大排序這n個數，然后再遍歷序列中后k個元素輸出，即可，總的時間復雜度為O（n*logn+k）=O（n*logn）。

    2、排序，選擇排序。用選擇或交換排序，即遍歷n個數，先把最先遍歷到得k個數存入大小為k的數組之中，對這k個數，利用選擇或交換排序，找到k個數中的最小數kmin（kmin設為k個元素的數組中最小元素），用時O（k）（你應該知道，插入或選擇排序查找操作需要O（k）的時間），后再繼續遍歷后n-k個數，x與kmin比較：如果x>kmin，則x代替kmin，并再次重新找出k個元素的數組中最大元素kmin‘（多謝jiyeyuran 提醒修正）；如果x<kmin，則不更新數組。這樣，每次更新或不更新數組的所用的時間為O（k）或O（0），整趟下來，總的時間復雜度平均下來為：n*O（k）=O（n*k）。

    3、維護k個元素的最小堆，原理與上述第2個方案一致，即用容量為k的最小堆存儲最先遍歷到的k個數，并假設它們即是最大的k個數，建堆費時O（k），并調整堆（費時O（logk））后，有k1>k2>...kmin（kmin設為小頂堆中最小元素）。繼續遍歷數列，每次遍歷一個元素x，與堆頂元素比較，若x>kmin，則更新堆（用時logk），否則不更新堆。這樣下來，總費時O（k*logk+（n-k）*logk）=O（n*logk）。此方法得益于在堆中，查找等各項操作時間復雜度均為logk（不然，就如上述思路2所述：直接用數組也可以找出最大的k個元素，用時O（n*k））。

    4、按編程之美第141頁上解法二的所述，類似快速排序的劃分方法，N個數存儲在數組S中，再從數組中隨機選取一個數X，把數組劃分為Sa和Sb倆部分，Sa>=X>=Sb，如果要查找的k個元素小于Sa的元素個數，則返回Sa中較大的k個元素，否則返回Sa中所有的元素+Sb中最大的k-|Sa|個元素。不斷遞歸下去，把問題分解成更小的問題，平均時間復雜度為O（N）（編程之美所述的n*logk的復雜度有誤，應為O（N），特此訂正。其嚴格證明，請參考第三章：程序員面試題狂想曲：第三章、尋找最小的k個數、updated 10次）。
   .........

   其它的方法，在此不再重復了，同時，尋找最小的k個數借助堆的實現，代碼在上一篇文章第三章已有給出，更多，可參考第三章，只要把最大堆改成最小堆，即可。


第三節、Top K 算法問題
3.1、搜索引擎熱門查詢統計

題目描述：
    搜索引擎會通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來，每個查詢串的長度為1-255字節。
    假設目前有一千萬個記錄（這些查詢串的重復度比較高，雖然總數是1千萬，但如果除去重復后，不超過3百萬個。一個查詢串的重復度越高，說明查詢它的用戶越多，也就是越熱門。），請你統計最熱門的10個查詢串，要求使用的內存不能超過1G。

    分析：這個問題在之前的這篇文章十一、從頭到尾徹底解析Hash表算法里，已經有所解答。方法是:

    第一步、先對這批海量數據預處理，在O（N）的時間內用Hash表完成統計（之前寫成了排序，特此訂正。July、2011.04.27）；
    第二步、借助堆這個數據結構，找出Top K，時間復雜度為N‘logK。
        即，借助堆結構，我們可以在log量級的時間內查找和調整/移動。因此，維護一個K(該題目中是10)大小的小根堆（K1>K2>....Kmin，Kmin設為堆頂元素），然后遍歷300萬的Query，分別和根元素Kmin進行對比比較（如上第2節思路3所述，若X>Kmin，則更新并調整堆，否則，不更新），我們最終的時間復雜度是：O（N） + N'*O（logK），（N為1000萬，N’為300萬）。ok，更多，詳情，請參考原文。

    或者：采用trie樹，關鍵字域存該查詢串出現的次數，沒有出現為0。最后用10個元素的最小推來對出現頻率進行排序。

    ok，本章里，咱們來實現這個問題，為了降低實現上的難度，假設這些記錄全部是一些英文單詞，即用戶在搜索框里敲入一個英文單詞，然后查詢搜索結果，最后，要你統計輸入單詞中頻率最大的前K個單詞。ok，復雜問題簡單化了之后，編寫代碼實現也相對輕松多了，畫的簡單示意圖（繪制者，yansha），如下：

完整源碼：

  1. //copyright@yansha &&July  
  2. //July、updated，2011.05.08  
  3.   
  4. //題目描述：  
  5. //搜索引擎會通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來，每個查詢串的  
  6. //長度為1-255字節。假設目前有一千萬個記錄（這些查詢串的重復度比較高，雖然總數是1千萬，但如果  
  7. //除去重復后，不超過3百萬個。一個查詢串的重復度越高，說明查詢它的用戶越多，也就是越熱門），  
  8. //請你統計最熱門的10個查詢串，要求使用的內存不能超過1G。  
  9.   
  10. #include <iostream>  
  11. #include <string>  
  12. #include <assert.h>  
  13. using namespace std;  
  14.   
  15. #define HASHLEN 2807303  
  16. #define WORDLEN 30  
  17.   
  18. // 結點指針  
  19. typedef struct node_no_space *ptr_no_space;  
  20. typedef struct node_has_space *ptr_has_space;  
  21. ptr_no_space head[HASHLEN];  
  22.   
  23. struct node_no_space   
  24. {  
  25.     char *word;  
  26.     int count;  
  27.     ptr_no_space next;  
  28. };  
  29.   
  30. struct node_has_space  
  31. {  
  32.     char word[WORDLEN];  
  33.     int count;  
  34.     ptr_has_space next;  
  35. };  
  36.   
  37. // 最簡單hash函數  
  38. int hash_function(char const *p)  
  39. {  
  40.     int value = 0;  
  41.     while (*p != '/0')  
  42.     {  
  43.         value = value * 31 + *p++;  
  44.         if (value > HASHLEN)  
  45.             value = value % HASHLEN;  
  46.     }  
  47.     return value;  
  48. }  
  49.   
  50. // 添加單詞到hash表  
  51. void append_word(char const *str)  
  52. {  
  53.     int index = hash_function(str);  
  54.     ptr_no_space p = head[index];  
  55.     while (p != NULL)  
  56.     {  
  57.         if (strcmp(str, p->word) == 0)  
  58.         {  
  59.             (p->count)++;  
  60.             return;  
  61.         }  
  62.         p = p->next;  
  63.     }  
  64.       
  65.     // 新建一個結點  
  66.     ptr_no_space q = new node_no_space;  
  67.     q->count = 1;  
  68.     q->word = new char [strlen(str)+1];  
  69.     strcpy(q->word, str);  
  70.     q->next = head[index];  
  71.     head[index] = q;  
  72. }  
  73.   
  74.   
  75. // 將單詞處理結果寫入文件  
  76. void write_to_file()  
  77. {  
  78.     FILE *fp = fopen("result.txt", "w");  
  79.     assert(fp);  
  80.       
  81.     int i = 0;  
  82.     while (i < HASHLEN)  
  83.     {  
  84.         for (ptr_no_space p = head[i]; p != NULL; p = p->next)  
  85.             fprintf(fp, "%s  %d/n", p->word, p->count);  
  86.         i++;  
  87.     }  
  88.     fclose(fp);  
  89. }  
  90.   
  91. // 從上往下篩選，保持小根堆  
  92. void sift_down(node_has_space heap[], int i, int len)  
  93. {  
  94.     int min_index = -1;  
  95.     int left = 2 * i;  
  96.     int right = 2 * i + 1;  
  97.       
  98.     if (left <= len && heap[left].count < heap[i].count)  
  99.         min_index = left;  
  100.     else  
  101.         min_index = i;  
  102.       
  103.     if (right <= len && heap[right].count < heap[min_index].count)  
  104.         min_index = right;  
  105.       
  106.     if (min_index != i)  
  107.     {  
  108.         // 交換結點元素  
  109.         swap(heap[i].count, heap[min_index].count);  
  110.           
  111.         char buffer[WORDLEN];  
  112.         strcpy(buffer, heap[i].word);  
  113.         strcpy(heap[i].word, heap[min_index].word);  
  114.         strcpy(heap[min_index].word, buffer);  
  115.           
  116.         sift_down(heap, min_index, len);  
  117.     }  
  118. }  
  119.   
  120. // 建立小根堆  
  121. void build_min_heap(node_has_space heap[], int len)  
  122. {  
  123.     if (heap == NULL)  
  124.         return;  
  125.       
  126.     int index = len / 2;  
  127.     for (int i = index; i >= 1; i--)  
  128.         sift_down(heap, i, len);  
  129. }  
  130.   
  131. // 去除字符串前后符號  
  132. void handle_symbol(char *str, int n)  
  133. {  
  134.     while (str[n] < '0' || (str[n] > '9' && str[n] < 'A') || (str[n] > 'Z' && str[n] < 'a') || str[n] > 'z')  
  135.     {  
  136.         str[n] = '/0';  
  137.         n--;  
  138.     }  
  139.       
  140.     while (str[0] < '0' || (str[0] > '9' && str[0] < 'A') || (str[0] > 'Z' && str[0] < 'a') || str[0] > 'z')  
  141.     {  
  142.         int i = 0;  
  143.         while (i < n)  
  144.         {  
  145.             str[i] = str[i+1];  
  146.             i++;  
  147.         }  
  148.         str[i] = '/0';  
  149.         n--;  
  150.     }  
  151. }  
  152.   
  153. int main()  
  154. {  
  155.     char str[WORDLEN];  
  156.     for (int i = 0; i < HASHLEN; i++)  
  157.         head[i] = NULL;  
  158.       
  159.     // 將字符串用hash函數轉換成一個整數并統計出現頻率  
  160.     FILE *fp_passage = fopen("string.txt", "r");  
  161.     assert(fp_passage);  
  162.     while (fscanf(fp_passage, "%s", str) != EOF)  
  163.     {  
  164.         int n = strlen(str) - 1;  
  165.         if (n > 0)  
  166.             handle_symbol(str, n);  
  167.         append_word(str);  
  168.     }  
  169.     fclose(fp_passage);  
  170.       
  171.     // 將統計結果輸入文件  
  172.     write_to_file();  
  173.       
  174.     int n = 10;  
  175.     ptr_has_space heap = new node_has_space [n+1];  
  176.       
  177.     int c;  
  178.       
  179.     FILE *fp_word = fopen("result.txt", "r");  
  180.     assert(fp_word);  
  181.     for (int j = 1; j <= n; j++)  
  182.     {  
  183.         fscanf(fp_word, "%s %d", &str, &c);  
  184.         heap[j].count = c;  
  185.         strcpy(heap[j].word, str);  
  186.     }  
  187.       
  188.     // 建立小根堆  
  189.     build_min_heap(heap, n);  
  190.       
  191.     // 查找出現頻率最大的10個單詞  
  192.     while (fscanf(fp_word, "%s %d", &str, &c) != EOF)  
  193.     {  
  194.         if (c > heap[1].count)  
  195.         {  
  196.             heap[1].count = c;  
  197.             strcpy(heap[1].word, str);  
  198.             sift_down(heap, 1, n);  
  199.         }  
  200.     }  
  201.     fclose(fp_word);  
  202.       
  203.     // 輸出出現頻率最大的單詞  
  204.     for (int k = 1; k <= n; k++)  
  205.         cout << heap[k].count << " " << heap[k].word << endl;  
  206.       
  207.     return 0;  
  208. }  

 

程序測試：咱們接下來，來對下面的通過用戶輸入單詞后，搜索引擎記錄下來，“大量”單詞記錄進行統計（同時，令K=10，即要你找出10個最熱門查詢的單詞）：

運行結果：根據程序的運行結果，可以看到，搜索引擎記錄下來的查詢次數最多的10個單詞為（注，并未要求這10個數要有序輸出）：in（312次），it（384次），a（432），that（456），MPQ（408），of（504），and（624），is（456），the（1008），to（936）。

    讀者反饋from 楊忠勝：3.1節的代碼第38行 hash_function(char const *p)有誤吧，這樣的話，不能修改p的值（但是函數需要修改指針的值），要想不修改*p指向的內容，應該是const char *p; 此外，您程序中的/t,  /n有誤，C語言是\t,\n。
    感謝這位讀者的來信，日后統一訂正。謝謝。

 

3.2、統計出現次數最多的數據

題目描述：
給你上千萬或上億數據（有重復），統計其中出現次數最多的前N個數據。

    分析：上千萬或上億的數據，現在的機器的內存應該能存下（也許可以，也許不可以）。所以考慮采用hash_map/搜索二叉樹/紅黑樹等來進行統計次數。然后就是取出前N個出現次數最多的數據了。當然，也可以堆實現。

    ok，此題與上題類似，最好的方法是用hash_map統計出現的次數，然后再借用堆找出出現次數最多的N個數據。不過，上一題統計搜索引擎最熱門的查詢已經采用過hash表統計單詞出現的次數，特此，本題咱們改用紅黑樹取代之前的用hash表，來完成最初的統計，然后用堆更新，找出出現次數最多的前N個數據。

    同時，正好個人此前用c && c++ 語言實現過紅黑樹，那么，代碼能借用就借用吧。
完整代碼：

  1. //copyright@ zhouzhenren &&July  
  2. //July、updated，2011.05.08.  
  3.   
  4. //題目描述：  
  5. //上千萬或上億數據（有重復），統計其中出現次數最多的前N個數據  
  6.   
  7. //解決方案：  
  8. //1、采用紅黑樹（本程序中有關紅黑樹的實現代碼來源于@July）來進行統計次數。  
  9. //2、然后遍歷整棵樹，同時采用最小堆更新前N個出現次數最多的數據。  
  10.   
  11. //聲明：版權所有，引用必須注明出處。  
  12. #define PARENT(i) (i)/2  
  13. #define LEFT(i)   2*(i)  
  14. #define RIGHT(i)  2*(i)+1  
  15.   
  16. #include <stdio.h>  
  17. #include <stdlib.h>  
  18. #include <string.h>  
  19.   
  20. typedef enum rb_color{ RED, BLACK }RB_COLOR;  
  21. typedef struct rb_node  
  22. {  
  23.     int key;  
  24.     int data;  
  25.     RB_COLOR color;  
  26.     struct rb_node* left;  
  27.     struct rb_node* right;  
  28.     struct rb_node* parent;  
  29. }RB_NODE;  
  30.   
  31. RB_NODE* RB_CreatNode(int key, int data)  
  32. {  
  33.     RB_NODE* node = (RB_NODE*)malloc(sizeof(RB_NODE));  
  34.     if (NULL == node)  
  35.     {  
  36.         printf("malloc error!");  
  37.         exit(-1);  
  38.     }  
  39.       
  40.     node->key = key;  
  41.     node->data = data;  
  42.     node->color = RED;  
  43.     node->left = NULL;  
  44.     node->right = NULL;  
  45.     node->parent = NULL;  
  46.       
  47.     return node;  
  48. }  
  49.   
  50. /**  
  51. * 左旋   
  52. * 
  53. *  node           right  
  54. *  / /    ==>     / /  
  55. * a  right     node  y  
  56. *     / /       / /      
  57. *     b  y     a   b     
  58. */    
  59. RB_NODE* RB_RotateLeft(RB_NODE* node, RB_NODE* root)  
  60. {    
  61.     RB_NODE* right = node->right;    // 指定指針指向 right<--node->right    
  62.       
  63.     if ((node->right = right->left))      
  64.         right->left->parent = node;  // 好比上面的注釋圖，node成為b的父母  
  65.       
  66.     right->left = node;   // node成為right的左孩子   
  67.       
  68.     if ((right->parent = node->parent))    
  69.     {    
  70.         if (node == node->parent->right)    
  71.             node->parent->right = right;  
  72.         else    
  73.             node->parent->left = right;  
  74.     }    
  75.     else    
  76.         root = right;    
  77.       
  78.     node->parent = right;  //right成為node的父母    
  79.       
  80.     return root;    
  81. }    
  82.   
  83. /** 
  84. * 右旋   
  85. * 
  86. *      node            left  
  87. *       / /             / /  
  88. *     left y   ==>     a  node  
  89. *     / /                  / /  
  90. *    a   b                b   y   
  91. */    
  92. RB_NODE* RB_RotateRight(RB_NODE* node, RB_NODE* root)    
  93. {    
  94.     RB_NODE* left = node->left;    
  95.       
  96.     if ((node->left = left->right))    
  97.         left->right->parent = node;    
  98.       
  99.     left->right = node;    
  100.       
  101.     if ((left->parent = node->parent))    
  102.     {    
  103.         if (node == node->parent->right)      
  104.             node->parent->right = left;    
  105.         else    
  106.             node->parent->left = left;    
  107.     }    
  108.     else    
  109.         root = left;    
  110.       
  111.     node->parent = left;    
  112.       
  113.     return root;    
  114. }    
  115.   
  116. /**  
  117. * 紅黑樹的3種插入情況   
  118. * 用z表示當前結點, p[z]表示父母、p[p[z]]表示祖父, y表示叔叔. 
  119. */  
  120. RB_NODE* RB_Insert_Rebalance(RB_NODE* node, RB_NODE* root)    
  121. {    
  122.     RB_NODE *parent, *gparent, *uncle, *tmp;  //父母p[z]、祖父p[p[z]]、叔叔y、臨時結點*tmp    
  123.       
  124.     while ((parent = node->parent) && parent->color == RED)    
  125.     { // parent 為node的父母，且當父母的顏色為紅時    
  126.         gparent = parent->parent;   // gparent為祖父    
  127.           
  128.         if (parent == gparent->left)  // 當祖父的左孩子即為父母時,其實上述幾行語句，無非就是理順孩子、父母、祖父的關系。  
  129.         {  
  130.             uncle = gparent->right; // 定義叔叔的概念，叔叔y就是父母的右孩子。    
  131.             if (uncle && uncle->color == RED) // 情況1：z的叔叔y是紅色的    
  132.             {    
  133.                 uncle->color = BLACK;   // 將叔叔結點y著為黑色    
  134.                 parent->color = BLACK;  // z的父母p[z]也著為黑色。解決z，p[z]都是紅色的問題。    
  135.                 gparent->color = RED;      
  136.                 node = gparent;     // 將祖父當做新增結點z，指針z上移倆層，且著為紅色。    
  137.                 // 上述情況1中，只考慮了z作為父母的右孩子的情況。    
  138.             }    
  139.             else                     // 情況2：z的叔叔y是黑色的，    
  140.             {       
  141.                 if (parent->right == node)  // 且z為右孩子    
  142.                 {    
  143.                     root = RB_RotateLeft(parent, root); // 左旋[結點z，與父母結點]    
  144.                     tmp = parent;    
  145.                     parent = node;    
  146.                     node = tmp;     // parent與node 互換角色    
  147.                 }    
  148.                 // 情況3：z的叔叔y是黑色的，此時z成為了左孩子。    
  149.                 // 注意，1：情況3是由上述情況2變化而來的。    
  150.                 // ......2：z的叔叔總是黑色的，否則就是情況1了。    
  151.                 parent->color = BLACK;   // z的父母p[z]著為黑色    
  152.                 gparent->color = RED;    // 原祖父結點著為紅色    
  153.                 root = RB_RotateRight(gparent, root); // 右旋[結點z，與祖父結點]    
  154.             }    
  155.         }     
  156.           
  157.         else     
  158.         {         
  159.             // 這部分是特別為情況1中，z作為左孩子情況，而寫的。    
  160.             uncle = gparent->left;  // 祖父的左孩子作為叔叔結點。[原理還是與上部分一樣的]    
  161.             if (uncle && uncle->color == RED)  // 情況1：z的叔叔y是紅色的    
  162.             {    
  163.                 uncle->color = BLACK;    
  164.                 parent->color = BLACK;    
  165.                 gparent->color = RED;    
  166.                 node = gparent;           // 同上  
  167.             }    
  168.             else                               // 情況2：z的叔叔y是黑色的，    
  169.             {    
  170.                 if (parent->left == node)  // 且z為左孩子    
  171.                 {    
  172.                     root = RB_RotateRight(parent, root);  // 以結點parent、root右旋    
  173.                     tmp = parent;    
  174.                     parent = node;    
  175.                     node = tmp;       // parent與node 互換角色    
  176.                 }     
  177.                 // 經過情況2的變化，成為了情況3.    
  178.                 parent->color = BLACK;    
  179.                 gparent->color = RED;    
  180.                 root = RB_RotateLeft(gparent, root);   // 以結點gparent和root左旋    
  181.             }    
  182.         }    
  183.     }    
  184.       
  185.     root->color = BLACK; // 根結點，不論怎樣，都得置為黑色。    
  186.     return root;      // 返回根結點。    
  187. }  
  188.   
  189. /**  
  190. * 紅黑樹查找結點   
  191. * rb_search_auxiliary：查找   
  192. * rb_node_t* rb_search：返回找到的結點   
  193. */  
  194. RB_NODE* RB_SearchAuxiliary(int key, RB_NODE* root, RB_NODE** save)    
  195. {    
  196.     RB_NODE* node = root;  
  197.     RB_NODE* parent = NULL;    
  198.     int ret;    
  199.       
  200.     while (node)    
  201.     {    
  202.         parent = node;    
  203.         ret = node->key - key;    
  204.         if (0 < ret)    
  205.             node = node->left;    
  206.         else if (0 > ret)    
  207.             node = node->right;    
  208.         else    
  209.             return node;    
  210.     }    
  211.       
  212.     if (save)    
  213.         *save = parent;    
  214.       
  215.     return NULL;    
  216. }    
  217.   
  218. /**  
  219. * 返回上述rb_search_auxiliary查找結果   
  220. */  
  221. RB_NODE* RB_Search(int key, RB_NODE* root)    
  222. {    
  223.     return RB_SearchAuxiliary(key, root, NULL);    
  224. }    
  225.   
  226. /**  
  227. * 紅黑樹的插入   
  228. */  
  229. RB_NODE* RB_Insert(int key, int data, RB_NODE* root)    
  230. {    
  231.     RB_NODE* parent = NULL;  
  232.     RB_NODE* node = NULL;    
  233.       
  234.     parent = NULL;    
  235.     if ((node = RB_SearchAuxiliary(key, root, &parent)))  // 調用RB_SearchAuxiliary找到插入結點的地方    
  236.     {    
  237.         node->data++; // 節點已經存在data值加1  
  238.         return root;    
  239.     }    
  240.       
  241.     node = RB_CreatNode(key, data);  // 分配結點    
  242.     node->parent = parent;        
  243.       
  244.     if (parent)    
  245.     {    
  246.         if (parent->key > key)    
  247.             parent->left = node;    
  248.         else    
  249.             parent->right = node;    
  250.     }    
  251.     else    
  252.     {    
  253.         root = node;    
  254.     }    
  255.       
  256.     return RB_Insert_Rebalance(node, root);   // 插入結點后，調用RB_Insert_Rebalance修復紅黑樹的性質    
  257. }  
  258.   
  259. typedef struct rb_heap  
  260. {  
  261.     int key;  
  262.     int data;  
  263. }RB_HEAP;  
  264. const int heapSize = 10;  
  265. RB_HEAP heap[heapSize+1];  
  266.   
  267. /**  
  268. * MAX_HEAPIFY函數對堆進行更新，使以i為根的子樹成最大堆 
  269. */  
  270. void MIN_HEAPIFY(RB_HEAP* A, const int& size, int i)  
  271. {  
  272.     int l = LEFT(i);  
  273.     int r = RIGHT(i);  
  274.     int smallest = i;  
  275.       
  276.     if (l <= size && A[l].data < A[i].data)  
  277.         smallest = l;  
  278.     if (r <= size && A[r].data < A[smallest].data)  
  279.         smallest = r;  
  280.       
  281.     if (smallest != i)  
  282.     {  
  283.         RB_HEAP tmp = A[i];  
  284.         A[i] = A[smallest];  
  285.         A[smallest] = tmp;  
  286.         MIN_HEAPIFY(A, size, smallest);  
  287.     }  
  288. }  
  289.   
  290. /**  
  291. * BUILD_MINHEAP函數對數組A中的數據建立最小堆 
  292. */  
  293. void BUILD_MINHEAP(RB_HEAP* A, const int& size)  
  294. {  
  295.     for (int i = size/2; i >= 1; --i)  
  296.         MIN_HEAPIFY(A, size, i);  
  297. }  
  298.   
  299.   
  300. /* 
  301. 3、維護k個元素的最小堆，原理與上述第2個方案一致， 
  302. 即用容量為k的最小堆存儲最先在紅黑樹中遍歷到的k個數，并假設它們即是最大的k個數，建堆費時O（k）， 
  303. 然后調整堆（費時O（logk））后，有k1>k2>...kmin（kmin設為小頂堆中最小元素）。 
  304. 繼續中序遍歷紅黑樹，每次遍歷一個元素x，與堆頂元素比較，若x>kmin，則更新堆（用時logk），否則不更新堆。 
  305. 這樣下來，總費時O（k*logk+（n-k）*logk）=O（n*logk）。 
  306. 此方法得益于在堆中，查找等各項操作時間復雜度均為logk）。 
  307. */  
  308.   
  309. //中序遍歷RBTree  
  310. void InOrderTraverse(RB_NODE* node)    
  311. {  
  312.     if (node == NULL)    
  313.     {    
  314.         return;    
  315.     }    
  316.     else    
  317.     {    
  318.         InOrderTraverse(node->left);    
  319.         if (node->data > heap[1].data) // 當前節點data大于最小堆的最小元素時，更新堆數據  
  320.         {  
  321.             heap[1].data = node->data;  
  322.             heap[1].key = node->key;  
  323.             MIN_HEAPIFY(heap, heapSize, 1);  
  324.         }  
  325.         InOrderTraverse(node->right);    
  326.     }  
  327. }   
  328.   
  329. void RB_Destroy(RB_NODE* node)  
  330. {  
  331.     if (NULL == node)  
  332.     {  
  333.         return;  
  334.     }  
  335.     else  
  336.     {  
  337.         RB_Destroy(node->left);  
  338.         RB_Destroy(node->right);  
  339.         free(node);  
  340.         node = NULL;  
  341.     }  
  342. }  
  343.   
  344. int main()  
  345. {  
  346.     RB_NODE* root = NULL;  
  347.     RB_NODE* node = NULL;    
  348.       
  349.     // 初始化最小堆  
  350.     for (int i = 1; i <= 10; ++i)  
  351.     {  
  352.         heap[i].key = i;  
  353.         heap[i].data = -i;  
  354.     }  
  355.     BUILD_MINHEAP(heap, heapSize);  
  356.       
  357.     FILE* fp = fopen("data.txt", "r");  
  358.     int num;  
  359.     while (!feof(fp))  
  360.     {  
  361.         fscanf(fp, "%d", &num);  
  362.         root = RB_Insert(num, 1, root);  
  363.     }  
  364.     fclose(fp);  
  365.       
  366.     InOrderTraverse(root);   //遞歸遍歷紅黑樹  
  367.     RB_Destroy(root);  
  368.       
  369.     for (i = 1; i <= 10; ++i)  
  370.     {  
  371.         printf("%d/t%d/n", heap[i].key, heap[i].data);  
  372.     }     
  373.     return 0;  
  374. }   

 

程序測試：咱們來對下面這個小文件進行測試：

運行結果：如下圖所示，

 

問題補遺：

    ok，由于在遍歷紅黑樹采用的是遞歸方式比較耗內存，下面給出一個非遞歸遍歷的程序（下述代碼若要運行，需貼到上述程序之后，因為其它的代碼未變，只是在遍歷紅黑樹的時候，采取非遞歸遍歷而已，同時，主函數的編寫也要稍微修改下）：

  1. //copyright@ zhouzhenren  
  2. //July、updated，2011.05.08.  
  3. #define STACK_SIZE 1000  
  4. typedef struct  
  5. {                                              // 棧的結點定義  
  6.     RB_NODE** top;  
  7.     RB_NODE** base;  
  8. }*PStack, Stack;  
  9.   
  10. bool InitStack(PStack& st)                       // 初始化棧  
  11. {  
  12.     st->base = (RB_NODE**)malloc(sizeof(RB_NODE*) * STACK_SIZE);  
  13.     if (!st->base)  
  14.     {  
  15.         printf("InitStack error!");  
  16.         exit(1);  
  17.     }  
  18.     st->top = st->base;  
  19.     return true;  
  20. }  
  21.   
  22. bool Push(PStack& st, RB_NODE*& e)                    // 入棧  
  23. {  
  24.     if (st->top - st->base >= STACK_SIZE)  
  25.         return false;  
  26.     *st->top = e;  
  27.     st->top++;  
  28.     return true;  
  29. }  
  30.   
  31. bool Pop(PStack& st, RB_NODE*& e)                     // 出棧  
  32. {  
  33.     if (st->top == st->base)  
  34.     {  
  35.         e = NULL;  
  36.         return false;  
  37.     }  
  38.     e = *--st->top;  
  39.     return true;  
  40. }  
  41.   
  42. bool StackEmpty(PStack& st)                     // 棧是否為空  
  43. {  
  44.     if (st->base == st->top)  
  45.         return true;  
  46.     else  
  47.         return false;  
  48. }  
  49.   
  50. bool InOrderTraverse_Stack(RB_NODE*& T)                 // 中序遍歷  
  51. {  
  52.     PStack S = (PStack)malloc(sizeof(Stack));  
  53.     RB_NODE* P = T;  
  54.     InitStack(S);  
  55.     while (P != NULL || !StackEmpty(S))  
  56.     {  
  57.         if (P != NULL)  
  58.         {  
  59.             Push(S, P);  
  60.             P = P->left;  
  61.         }  
  62.         else  
  63.         {  
  64.             Pop(S, P);  
  65.             if (P->data > heap[1].data) // 當前節點data大于最小堆的最小元素時，更新堆數據  
  66.             {  
  67.                 heap[1].data = P->data;  
  68.                 heap[1].key = P->key;  
  69.                 MIN_HEAPIFY(heap, heapSize, 1);  
  70.             }  
  71.             P = P->right;  
  72.         }  
  73.     }  
  74.     free(S->base);  
  75.     S->base = NULL;  
  76.     free(S);  
  77.     S = NULL;  
  78.       
  79.     return true;  
  80. }  
  81.   
  82. bool PostOrderTraverse_Stack(RB_NODE*& T)               //后序遍歷  
  83. {  
  84.     PStack S = (PStack)malloc(sizeof(Stack));  
  85.     RB_NODE* P = T;  
  86.     RB_NODE* Pre = NULL;  
  87.     InitStack(S);  
  88.     while (P != NULL || !StackEmpty(S))  
  89.     {  
  90.         if (P != NULL) // 非空直接入棧  
  91.         {  
  92.             Push(S, P);  
  93.             P = P->left;  
  94.         }  
  95.         else  
  96.         {  
  97.             Pop(S, P); // 彈出棧頂元素賦值給P  
  98.             if (P->right == NULL || P->right == Pre) // P的右子樹空或是右子樹是剛訪問過的  
  99.             { // 節點，則釋放當前節點內存  
  100.                 free(P);  
  101.                 Pre = P;  
  102.                 P = NULL;  
  103.             }  
  104.             else // 反之，當前節點重新入棧，接著判斷右子樹  
  105.             {  
  106.                 Push(S, P);  
  107.                 P = P->right;  
  108.             }  
  109.         }  
  110.     }  
  111.     free(S->base);  
  112.     S->base = NULL;  
  113.     free(S);  
  114.     S = NULL;  
  115.       
  116.     return true;  
  117. }  
  118.   
  119. //主函數稍微修改如下：  
  120. int main()  
  121. {  
  122.     RB_NODE* root = NULL;  
  123.     RB_NODE* node = NULL;    
  124.       
  125.     // 初始化最小堆  
  126.     for (int i = 1; i <= 10; ++i)  
  127.     {  
  128.         heap[i].key = i;  
  129.         heap[i].data = -i;  
  130.     }  
  131.     BUILD_MINHEAP(heap, heapSize);  
  132.       
  133.     FILE* fp = fopen("data.txt", "r");  
  134.     int num;  
  135.     while (!feof(fp))  
  136.     {  
  137.         fscanf(fp, "%d", &num);  
  138.         root = RB_Insert(num, 1, root);  
  139.     }  
  140.     fclose(fp);  
  141.       
  142.       //若上面的程序后面加上了上述的非遞歸遍歷紅黑樹的代碼，那么以下幾行代碼，就得修改如下：  
  143.     //InOrderTraverse(root); //此句去掉（遞歸遍歷樹）  
  144.     InOrderTraverse_Stack(root); // 非遞歸遍歷樹  
  145.       
  146.     //RB_Destroy(root); //此句去掉（通過遞歸釋放內存）  
  147.     PostOrderTraverse_Stack(root); // 非遞歸釋放內存  
  148.       
  149.     for (i = 1; i <= 10; ++i)  
  150.     {  
  151.         printf("%d/t%d/n", heap[i].key, heap[i].data);  
  152.     }     
  153.     return 0;  
  154. }   

 

updated：

 后來，我們狂想曲創作組中的3又用hash+堆實現了上題，很明顯比采用上面的紅黑樹，整個實現簡潔了不少，其完整源碼如下：

完整源碼：

  1. //Author: zhouzhenren  
  2. //Description: 上千萬或上億數據（有重復），統計其中出現次數最多的錢N個數據  
  3.   
  4. //Algorithm： 采用hash_map來進行統計次數+堆（找出Top K）。  
  5. //July，2011.05.12。紀念汶川地震三周年，默哀三秒。  
  6.   
  7. #define PARENT(i) (i)/2  
  8. #define LEFT(i)   2*(i)  
  9. #define RIGHT(i)  2*(i)+1  
  10.   
  11. #define HASHTABLESIZE 2807303  
  12. #define HEAPSIZE 10  
  13. #define A 0.6180339887  
  14. #define M 16384     //m=2^14  
  15.   
  16. #include <stdio.h>  
  17. #include <stdlib.h>  
  18.   
  19. typedef struct hash_node  
  20. {  
  21.     int data;  
  22.     int count;  
  23.     struct hash_node* next;  
  24. }HASH_NODE;  
  25. HASH_NODE* hash_table[HASHTABLESIZE];  
  26.   
  27. HASH_NODE* creat_node(int& data)  
  28. {  
  29.     HASH_NODE* node = (HASH_NODE*)malloc(sizeof(HASH_NODE));  
  30.       
  31.     if (NULL == node)  
  32.     {  
  33.         printf("malloc node failed!/n");  
  34.         exit(EXIT_FAILURE);  
  35.     }  
  36.       
  37.     node->data = data;  
  38.     node->count = 1;  
  39.     node->next = NULL;  
  40.     return node;  
  41. }  
  42.   
  43. /**  
  44. * hash函數采用乘法散列法 
  45. * h(k)=int(m*(A*k mod 1)) 
  46. */  
  47. int hash_function(int& key)    
  48. {    
  49.     double result = A * key;  
  50.     return (int)(M * (result - (int)result));    
  51. }  
  52.   
  53. void insert(int& data)  
  54. {  
  55.     int index = hash_function(data);  
  56.     HASH_NODE* pnode = hash_table[index];  
  57.     while (NULL != pnode)  
  58.     {   // 以存在data，則count++  
  59.         if (pnode->data == data)  
  60.         {  
  61.             pnode->count += 1;  
  62.             return;  
  63.         }  
  64.         pnode = pnode->next;  
  65.     }  
  66.       
  67.     // 建立一個新的節點，在表頭插入  
  68.     pnode = creat_node(data);  
  69.     pnode->next = hash_table[index];  
  70.     hash_table[index] = pnode;  
  71. }  
  72.   
  73. /**  
  74. * destroy_node釋放創建節點產生的所有內存 
  75. */  
  76. void destroy_node()  
  77. {  
  78.     HASH_NODE* p = NULL;  
  79.     HASH_NODE* tmp = NULL;  
  80.     for (int i = 0; i < HASHTABLESIZE; ++i)  
  81.     {  
  82.         p = hash_table[i];  
  83.         while (NULL != p)  
  84.         {  
  85.             tmp = p;  
  86.             p = p->next;  
  87.             free(tmp);  
  88.             tmp = NULL;  
  89.         }  
  90.     }  
  91. }  
  92.   
  93. typedef struct min_heap  
  94. {  
  95.     int count;  
  96.     int data;  
  97. }MIN_HEAP;  
  98. MIN_HEAP heap[HEAPSIZE + 1];  
  99.   
  100. /**  
  101. * min_heapify函數對堆進行更新，使以i為跟的子樹成最大堆 
  102. */  
  103. void min_heapify(MIN_HEAP* H, const int& size, int i)  
  104. {  
  105.     int l = LEFT(i);  
  106.     int r = RIGHT(i);  
  107.     int smallest = i;  
  108.       
  109.     if (l <= size && H[l].count < H[i].count)  
  110.         smallest = l;  
  111.     if (r <= size && H[r].count < H[smallest].count)  
  112.         smallest = r;  
  113.       
  114.     if (smallest != i)  
  115.     {  
  116.         MIN_HEAP tmp = H[i];  
  117.         H[i] = H[smallest];  
  118.         H[smallest] = tmp;  
  119.         min_heapify(H, size, smallest);  
  120.     }  
  121. }  
  122.   
  123. /**  
  124. * build_min_heap函數對數組A中的數據建立最小堆 
  125. */  
  126. void build_min_heap(MIN_HEAP* H, const int& size)  
  127. {  
  128.     for (int i = size/2; i >= 1; --i)  
  129.         min_heapify(H, size, i);  
  130. }  
  131.   
  132. /**  
  133. * traverse_hashtale函數遍歷整個hashtable，更新最小堆 
  134. */  
  135. void traverse_hashtale()  
  136. {  
  137.     HASH_NODE* p = NULL;  
  138.     for (int i = 0; i < HASHTABLESIZE; ++i)  
  139.     {  
  140.         p = hash_table[i];  
  141.         while (NULL != p)  
  142.         {   // 如果當前節點的數量大于最小堆的最小值，則更新堆  
  143.             if (p->count > heap[1].count)  
  144.             {  
  145.                 heap[1].count = p->count;  
  146.                 heap[1].data = p->data;  
  147.                 min_heapify(heap, HEAPSIZE, 1);  
  148.             }  
  149.             p = p->next;  
  150.         }  
  151.     }  
  152. }  
  153.   
  154. int main()  
  155. {  
  156.     // 初始化最小堆  
  157.     for (int i = 1; i <= 10; ++i)  
  158.     {  
  159.         heap[i].count = -i;  
  160.         heap[i].data = i;  
  161.     }  
  162.     build_min_heap(heap, HEAPSIZE);  
  163.       
  164.     FILE* fp = fopen("data.txt", "r");  
  165.     int num;  
  166.     while (!feof(fp))  
  167.     {  
  168.         fscanf(fp, "%d", &num);  
  169.         insert(num);  
  170.     }  
  171.     fclose(fp);  
  172.       
  173.     traverse_hashtale();  
  174.       
  175.     for (i = 1; i <= 10; ++i)  
  176.     {  
  177.         printf("%d/t%d/n", heap[i].data, heap[i].count);  
  178.     }  
  179.       
  180.     return 0;  
  181. }   

 

程序測試：對65047kb的數據量文件，進行測試統計（不過，因其數據量實在太大，半天沒打開）：

運行結果：如下，

 

 

第四節、海量數據處理問題一般總結

      關于海量數據處理的問題，一般有Bloom filter，Hashing，bit-map，堆，trie樹等方法來處理。更詳細的介紹，請查看此文：十道海量數據處理面試題與十個方法大總結。

 

 

余音

      反饋：此文發布后，走進搜索引擎的作者&&深入搜索引擎-海量信息的壓縮、索引和查詢的譯者，梁斌老師，對此文提了點意見，如下：1、首先TopK問題，肯定需要有并發的，否則串行搞肯定慢，IO和計算重疊度不高。其次在IO上需要一些技巧，當然可能只是驗證算法，在實踐中IO的提升會非常明顯。最后上文的代碼可讀性雖好，但機器的感覺可能就會差，這樣會影響性能。2、同時，TopK可以看成從地球上選拔k個跑的最快的，參加奧林匹克比賽，各個國家自行選拔，各個大洲選拔，層層選拔，最后找出最快的10個。發揮多機多核的優勢。

      預告：程序員面試題狂想曲、第四章，本月月底之前發布（盡最大努力）。

 

修訂

     程序員面試題狂想曲-tctop（the crazy thingking of programers）的修訂wiki（http://tctop.wikispaces.com/）已于今天建立，我們急切的想得到讀者的反饋，意見，建議，以及更好的思路，算法，和代碼優化的建議。所以，

  • 如果你發現了狂想曲系列中的任何一題，任何一章（http://t.cn/hgVPmH）中的錯誤，問題，與漏洞，歡迎告知給我們，我們將感激不盡，同時，免費贈送本blog內的全部博文集錦的CHM文件1期；
  • 如果你能對狂想曲系列的創作提供任何建設性意見，或指導，歡迎反饋給我們，并真誠邀請您加入到狂想曲的wiki修訂工作中；
  • 如果你是編程高手，對狂想曲的任何一章有自己更好的思路，或算法，歡迎加入狂想曲的創作組，以為千千萬萬的讀者創造更多的價值，更好的服務。

 Ps：狂想曲tctop的wiki修訂地址為：http://tctop.wikispaces.com/。歡迎圍觀，更歡迎您加入到狂想曲的創作或wiki修訂中。

聯系July
•email，zhoulei0907@yahoo.cn
•blog，http://blog.csdn.net/v_JULY_v 。
•weibo，http://weibo.com/julyweibo 。

作者按：有任何問題，或建議，歡迎以上述聯系方式call me，真誠的謝謝各位。
      July、狂想曲創作組，二零一一年五月十日。

 

 

版權所有，本人對本blog內所有任何內容享有版權及著作權。實要轉載，請以鏈接形式注明出處。
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

    • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            
亚洲视频免费看|
欧美日韩中字|
一本高清dvd不卡在线观看|
亚洲欧洲精品成人久久奇米网|
最近中文字幕日韩精品|
在线亚洲观看|
久久久噜噜噜久久|
国产视频精品xxxx|
国产精品成人一区|
国内精品免费在线观看|
日韩视频不卡|
国产精品美女久久久久av超清|
欧美不卡激情三级在线观看|
国产精品视频一二三|
亚洲精选91|
久久久国产亚洲精品|
欧美吻胸吃奶大尺度电影|
国产精品私房写真福利视频|
亚洲国产精品久久久久秋霞蜜臀
|
你懂的国产精品|
欧美精品性视频|
欧美在线播放一区二区|
欧美大成色www永久网站婷|
欧美精品videossex性护士|
国产偷国产偷精品高清尤物|
亚洲精品孕妇|
欧美一区二区三区免费在线看|
亚洲精品久久7777|
美女网站久久|
玉米视频成人免费看|
久久久亚洲精品一区二区三区|
亚洲精品一二|
久久综合色播五月|
国产一区视频在线看|
亚洲欧美日韩国产成人精品影院
|
欧美91视频|
亚洲综合精品自拍|
欧美日韩一区免费|
一本色道久久综合精品竹菊|
亚洲成色www8888|
99国内精品久久|
欧美成人午夜|
麻豆精品网站|
亚洲激情国产|
亚洲高清一二三区|
欧美黄色小视频|
国产一区二区三区日韩|
日韩视频免费在线|
99国产精品一区|
欧美精品高清视频|
日韩写真视频在线观看|
在线中文字幕一区|
欧美日韩国产精品一卡|
亚洲综合成人婷婷小说|
亚洲欧美精品suv|
国产一区999|
久久视频在线视频|
久久av一区二区三区漫画|
亚洲国产精品日韩|
欧美片第一页|
亚洲欧美在线免费|
欧美在线影院在线视频|
国语自产精品视频在线看8查询8
|
久久精品国产96久久久香蕉|
最新热久久免费视频|
欧美精品一区在线播放|
在线亚洲欧美|
99精品国产一区二区青青牛奶|
毛片av中文字幕一区二区|
亚洲欧洲在线一区|
亚洲图片欧美午夜|
日韩一级视频免费观看在线|
小黄鸭精品密入口导航|
亚洲精品一区二区三区av|
亚洲欧美中文日韩在线|
亚洲精品乱码|
久久精品国产精品亚洲综合|
在线视频精品一区|
麻豆精品精品国产自在97香蕉|
午夜精品视频在线观看一区二区|
美女精品视频一区|
久久精品最新地址|
欧美网站在线观看|
亚洲国产影院|
在线国产日韩|
久久九九国产精品怡红院|
亚洲欧美在线免费|
欧美激情小视频|
老司机久久99久久精品播放免费
|
亚洲一区网站|
亚洲精品视频免费在线观看|
久久精品二区亚洲w码|
亚洲一级在线|
欧美黄在线观看|
欧美成人有码|
在线免费观看日本欧美|
久久精品国产综合精品|
久久精品国产欧美激情|
国产视频一区在线观看|
久久国产精彩视频|
久久精品国产亚洲a|
国产精品视频区|
在线一区观看|
亚洲欧美日韩精品久久亚洲区|
欧美成人国产va精品日本一级|
欧美不卡视频一区|
在线欧美视频|
久久伊人免费视频|
牛人盗摄一区二区三区视频|
狠狠干狠狠久久|
午夜欧美视频|
美女脱光内衣内裤视频久久网站|
亚洲大胆人体视频|
老色批av在线精品|
久久九九免费|
欧美精品一区二区蜜臀亚洲|
日韩系列在线|
欧美在线视频观看|
极品av少妇一区二区|
久久女同互慰一区二区三区|
亚洲国产精品尤物yw在线观看|
91久久嫩草影院一区二区|
欧美乱妇高清无乱码|
亚洲在线视频网站|
国产毛片一区二区|
久久经典综合|
久久久天天操|
在线免费一区三区|
久久久无码精品亚洲日韩按摩|
免费成人性网站|
亚洲神马久久|
国产亚洲激情视频在线|
裸体丰满少妇做受久久99精品|
亚洲精品国久久99热|
久久久99爱|
亚洲精品午夜精品|
国产精品天美传媒入口|
亚洲永久在线|
欧美高清视频在线观看|
亚洲人成网站777色婷婷|
欧美日韩小视频|
欧美在线在线|
亚洲精品一二三|
久久精品99国产精品日本
|
巨乳诱惑日韩免费av|
亚洲精品中文字幕女同|
国产视频久久久久|
欧美欧美午夜aⅴ在线观看|
亚洲影音先锋|
亚洲欧洲视频在线|
欧美主播一区二区三区|
日韩午夜电影|
在线成人av|
国产人成精品一区二区三|
欧美精品在线观看一区二区|
午夜精品在线观看|
亚洲日本中文字幕|
欧美国产日韩一区二区在线观看|
亚洲欧美久久久|
99视频在线观看一区三区|
国产一区二区三区av电影
|
欧美极品一区|
久久国产日韩|
99精品热视频|
91久久精品国产|
亚洲国产高潮在线观看|
久久只精品国产|
欧美一区二区三区男人的天堂|
在线视频你懂得一区|
亚洲区欧美区|
亚洲精品123区|
…久久精品99久久香蕉国产|
国产一区二区三区不卡在线观看|
国产精品vip|
国产精品福利影院|
国产精品v亚洲精品v日韩精品
|
欧美一级欧美一级在线播放|
亚洲精品日韩久久|
亚洲福利专区|
国产在线麻豆精品观看|
国产精品久久久久三级|
欧美视频中文字幕|
欧美亚州一区二区三区|
欧美日韩不卡|
欧美激情综合五月色丁香小说|
欧美激情精品久久久|
毛片一区二区|
久久婷婷综合激情|
久久久精品999|
亚洲专区一区二区三区|
欧美日韩在线播放|
国产精品成人久久久久|
麻豆成人小视频|
蜜桃久久精品一区二区|
欧美国产日韩一区|
农夫在线精品视频免费观看|
久久久久久成人|
久久se精品一区精品二区|
亚洲男女毛片无遮挡|
一区二区欧美精品|