有10個(gè)文件,每個(gè)文件1G,每個(gè)文件的每一行存放的都是用戶的query,每個(gè)文件的query都可能重復(fù)。要求你按照query的頻度排序?
方案1:
hash映射: 順序讀取10個(gè)文件,按照hash(query)%10的結(jié)果將query寫入到另外10個(gè)文件(記為a0,a1,..a9)中。這樣新生成的文件每個(gè)的大小大約也1G(假設(shè)hash函數(shù)是隨機(jī)的)。
hash_map統(tǒng)計(jì): 找一臺內(nèi)存在2G左右的機(jī)器,依次對用hash_map(query, query_count)來統(tǒng)計(jì)每個(gè)query出現(xiàn)的次數(shù)。注: hash_map(query,query_count)是用來統(tǒng)計(jì)每個(gè)query的出現(xiàn)次數(shù),不是存儲他們的值,出現(xiàn)一次,則count+1。
堆/快速/歸并排序: 利用快速/堆/歸并排序按照出現(xiàn)次數(shù)進(jìn)行排序,將排序好的query和對應(yīng)的query_cout輸出到文件中,這樣得到了10個(gè)排好序的文件(記為)。最后,對這10個(gè)文件進(jìn)行歸并排序(內(nèi)排序與外排序相結(jié)合)。
方案2:
一般query的總量是有限的,只是重復(fù)的次數(shù)比較多而已,可能對于所有的query,一次性就可以加入到內(nèi)存了。這樣,我們就可以采用trie樹/hash_map等直接來統(tǒng)計(jì)每個(gè)query出現(xiàn)的次數(shù),然后按出現(xiàn)次數(shù)做快速/堆/歸并排序就可以了。
方案3:
與方案1類似,但在做完hash,分成多個(gè)文件后,可以交給多個(gè)文件來處理,采用分布式的架構(gòu)來處理(比如MapReduce),最后再進(jìn)行合并。 ¶ 給定a、b兩個(gè)文件,各存放50億個(gè)u