如果每個數(shù)據(jù)元素只出現(xiàn)一次,而且只出現(xiàn)在某一臺機器中,那么可以采取以下步驟統(tǒng)計出現(xiàn)次數(shù)TOP10的數(shù)據(jù)元素:
堆排序:在每臺電腦上求出TOP10,可以采用包含10個元素的堆完成(TOP10小,用最大堆,TOP10大,用最小堆,比如求TOP10大,我們首先取前10個元素調整成最小堆,如果發(fā)現(xiàn),然后掃描后面的數(shù)據(jù),并與堆頂元素比較,如果比堆頂元素大,那么用該元素替換堆頂,然后再調整為最小堆。最后堆中的元素就是TOP10大)。
求出每臺電腦上的TOP10后,然后把這100臺電腦上的TOP10組合起來,共1000個數(shù)據(jù),再利用上面類似的方法求出TOP10就可以了。 但如果同一個元素重復出現(xiàn)在不同的電腦中呢,如下例子所述, 這個時候,你可以有兩種方法:
1. 遍歷一遍所有數(shù)據(jù),重新hash取摸,如此使得同一個元素只出現(xiàn)在單獨的一臺電腦中,然后采用上面所說的方法,統(tǒng)計每臺電腦中各個元素的出現(xiàn)次數(shù)找出TOP10,繼而組合100臺電腦上的TOP10,找出最終的TOP10。
2. 或者,暴力求解: 直接統(tǒng)計統(tǒng)計每臺電腦中各個元素的出現(xiàn)次數(shù),然后把同一個元素在不同機器中的出現(xiàn)次數(shù)相加,最終從所有數(shù)據(jù)中找出TOP10。