上千萬or億數據(有重復),統計其中出現次數最多的前N個數據,分兩種情況:可壹次讀入內存,不可壹次讀入。
可用思路:trie樹+堆,數據庫索引,劃分子集分別統計,hash,分布式計算,近似統計,外排序
所謂的是否能壹次讀入內存,實際上應該指去除重復後的數據量。如果去重後數據可以放入 內存,我們可以為數據建立字典,比如通過 map,hashmap,trie,然後直接進行統計即可。當然在更新每條數據的出現次數的時候,我們可以利用壹個堆來維護出現次數最多的前N個數據,當然這樣導致維護次數增加,不如完全統計後在求前N大效率高。
如果數據無法放入內存。壹方面我們可以考慮上面的字典方法能否被改進以適應這種情形,可以做的改變就是將字典存放到硬盤上,而不是內存,這可以參考數據庫的存儲方法。
當然還有更好的方法,就是可以采用分布式計算,基本上就是map-reduce過程,首先可以根據數據值或者把數據hash(md5)後的值,將數據按照範圍劃分到不同的機子,最好可以讓數據劃分後可以壹次讀入內存,這樣不同的機子負責處理各種的數值範圍,實際上就是map。得到結果後,各個機子只需拿出各自的出現次數最多的前N個數據,然後匯總,選出所有的數據中出現次數最多的前N個數據,這實際上就是reduce過程。
實際上可能想直接將數據均分到不同的機子上進行處理,這樣是無法得到正確的解的。因為壹個數據可能被均分到不同的機子上,而另壹個則可能完全聚集到壹個機子上,同時還可能存在具有相同數目的數據。比如我們要找出現次數最多的前100個,我們將1000萬的數據分布到10臺機器上,找到每臺出現次數最多的前 100個,歸並之後這樣不能保證找到真正的第100個,因為比如出現次數最多的第100個可能有1萬個,但是它被分到了10臺機子,這樣在每臺上只有1千個,假設這些機子排名在1000個之前的那些都是單獨分布在壹臺機子上的,比如有1001個,這樣本來具有1萬個的這個就會被淘汰,即使我們讓每臺機子選出出現次數最多的1000個再歸並,仍然會出錯,因為可能存在大量個數為1001個的發生聚集。因此不能將數據隨便均分到不同機子上,而是要根據hash 後的值將它們映射到不同的機子上處理,讓不同的機器處理壹個數值範圍。
而外排序的方法會消耗大量的IO,效率不會很高。而上面的分布式方法,也可以用於單機版本,也就是將總的數據根據值的範圍,劃分成多個不同的子文件,然後逐個處理。處理完畢之後再對這些單詞的及其出現頻率進行壹個歸並。實際上就可以利用壹個外排序的歸並過程。
另外還可以考慮近似計算,也就是我們可以通過結合自然語言屬性,只將那些真正實際中出現最多的那些詞作為壹個字典,使得這個規模可以放入內存。