當前位置:編程學習大全網 - 網絡軟體 - 海量數據處理 大量數據中找出最大的前10個數 (Top K 問題)

海量數據處理 大量數據中找出最大的前10個數 (Top K 問題)

在工作中我們常遇到此類問題,從壹個大量甚至海量的數據中取出前幾個大的數。必須在海量的文章中取出點擊量最大的10篇文章。

此類問題其實就是Top K問題。

給定壹個數據(數據量海量 N),想找到前 K 個最大的或最小的元素。

eg:有10億個Long型整數,存儲在壹個文件中,如果找出其中最大的10個?

最容易想到的方法是將數據全部排序,然後在排序後的集合中進行查找,最快的排序算法的時間復雜度壹般為O(nlogn),如快速排序。每個Long類型占8個字節,10億個數就要占用7GB+的存儲空間,對於壹些可用內存小於7GB的計算機而言,很顯然是不能壹次將全部數據讀入內存進行排序的。其實即使內存能夠滿足要求(我機器內存都是8GB),該方法也並不高效,因為題目的目的是尋找出最大的10個數即可,而排序卻是將所有的元素都排序了,做了很多的無用功。

第二種方法采用最小堆。首先讀入前10個數來創建大小為10的最小堆,然後遍歷後續的數字,並於堆頂(最小)數字進行比較。如果比最小的數小,則繼續讀取後續數字;如果比堆頂數字大,則替換堆頂元素並重新調整堆為最小堆。整個過程直至10億個數全部遍歷完為止。然後按照中序遍歷的方式輸出當前堆中的所有10個數字。這個方法使用的內存是可控的,只有10個數字所需的內存即可。

  • 上一篇:莫斯科紅場上的列寧墓經歷了那些改動?
  • 下一篇:推薦壹些PSP用軟件吧
  • copyright 2024編程學習大全網