

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、1.給定給定a、b兩個(gè)文件,各存放兩個(gè)文件,各存放50億個(gè)億個(gè)url,每個(gè),每個(gè)url各占各占64字節(jié),內(nèi)存限制是字節(jié),內(nèi)存限制是4G,讓?zhuān)屇阏页瞿阏页鯽、b文件共同的文件共同的url?方案1:可以估計(jì)每個(gè)文件安的大小為50G64=320G,遠(yuǎn)遠(yuǎn)大于內(nèi)存限制的4G。所以不可能將其完全加載到內(nèi)存中處理。考慮采取分而治之的方法。s遍歷文件a,對(duì)每個(gè)url求取,然后根據(jù)所取得的值將url分別存儲(chǔ)到1000個(gè)小文件(記為)中。這樣每個(gè)小文件的
2、大約為300M。s遍歷文件b,采取和a相同的方式將url分別存儲(chǔ)到1000各小文件(記為)。這樣處理后,所有可能相同的url都在對(duì)應(yīng)的小文件()中,不對(duì)應(yīng)的小文件不可能有相同的url。然后我們只要求出1000對(duì)小文件中相同的url即可。s求每對(duì)小文件中相同的url時(shí),可以把其中一個(gè)小文件的url存儲(chǔ)到hash_set中。然后遍歷另一個(gè)小文件的每個(gè)url,看其是否在剛才構(gòu)建的hash_set中,如果是,那么就是共同的url,存到文件里面就
3、可以了。方案2:如果允許有一定的錯(cuò)誤率,可以使用Bloomfilter,4G內(nèi)存大概可以表示340億bit。將其中一個(gè)文件中的url使用Bloomfilter映射為這340億bit,然后挨個(gè)讀取另外一個(gè)文件的url,檢查是否與Bloomfilter,如果是,那么該url應(yīng)該是共同的url(注意會(huì)有一定的錯(cuò)誤率)。ps:個(gè)人認(rèn)為方案1中的估計(jì)是不是有問(wèn)題50億就是510的9次方。小于等于52的30次方,即5G,2.有10個(gè)文件,每個(gè)文件個(gè)
4、文件,每個(gè)文件1G,每個(gè)文件的每一行存放的都是用戶的,每個(gè)文件的每一行存放的都是用戶的query,每個(gè)文,每個(gè)文件的件的query都可能重復(fù)。要求你按照都可能重復(fù)。要求你按照query的頻度排序。的頻度排序。方案1:s順序讀取10個(gè)文件,按照hash(query)%10的結(jié)果將query寫(xiě)入到另外10個(gè)文件(記為)中。這樣新生成的文件每個(gè)的大小大約也1G(假設(shè)hash函數(shù)是隨機(jī)的)。s找一臺(tái)內(nèi)存在2G左右的機(jī)器,依次對(duì)用hash_map
5、(queryquery_count)來(lái)統(tǒng)計(jì)每個(gè)query出現(xiàn)的次數(shù)。利用快速堆歸并排序按照出現(xiàn)次數(shù)進(jìn)行排序。將排序好的query和對(duì)應(yīng)的query_cout輸出到文件中。這樣得到了10個(gè)排好序的文件(記為內(nèi)存,還可以接受。然后掃描這2.5億個(gè)整數(shù),查看Bitmap中相對(duì)應(yīng)位,如果是00變01,01變10,10保持不變。所描完事后,查看bitmap,把對(duì)應(yīng)位是01的整數(shù)輸出即可。方案2:也可采用上題類(lèi)似的方法,進(jìn)行劃分小文件的方法。然后在
6、小文件中找出不重復(fù)的整數(shù),并排序。然后再進(jìn)行歸并,注意去除重復(fù)的元素。6.海量數(shù)據(jù)分布在海量數(shù)據(jù)分布在100臺(tái)電腦中,想個(gè)辦法高校統(tǒng)計(jì)出這批數(shù)據(jù)的臺(tái)電腦中,想個(gè)辦法高校統(tǒng)計(jì)出這批數(shù)據(jù)的TOP10。方案1:s在每臺(tái)電腦上求出TOP10,可以采用包含10個(gè)元素的堆完成(TOP10小,用最大堆,TOP10大,用最小堆)。比如求TOP10大,我們首先取前10個(gè)元素調(diào)整成最小堆,如果發(fā)現(xiàn),然后掃描后面的數(shù)據(jù),并與堆頂元素比較,如果比堆頂元素大,那
7、么用該元素替換堆頂,然后再調(diào)整為最小堆。最后堆中的元素就是TOP10大。s求出每臺(tái)電腦上的TOP10后,然后把這100臺(tái)電腦上的TOP10組合起來(lái),共1000個(gè)數(shù)據(jù),再利用上面類(lèi)似的方法求出TOP10就可以了。7.怎么在海量數(shù)據(jù)中找出重復(fù)次數(shù)最多的一個(gè)?怎么在海量數(shù)據(jù)中找出重復(fù)次數(shù)最多的一個(gè)?方案1:先做hash,然后求模映射為小文件,求出每個(gè)小文件中重復(fù)次數(shù)最多的一個(gè),并記錄重復(fù)次數(shù)。然后找出上一步求出的數(shù)據(jù)中重復(fù)次數(shù)最多的一個(gè)就是所
8、求(具體參考前面的題)。8.上千萬(wàn)或上億數(shù)據(jù)(有重復(fù)),統(tǒng)計(jì)其中出現(xiàn)次數(shù)最多的錢(qián)上千萬(wàn)或上億數(shù)據(jù)(有重復(fù)),統(tǒng)計(jì)其中出現(xiàn)次數(shù)最多的錢(qián)N個(gè)數(shù)據(jù)。個(gè)數(shù)據(jù)。方案1:上千萬(wàn)或上億的數(shù)據(jù),現(xiàn)在的機(jī)器的內(nèi)存應(yīng)該能存下。所以考慮采用hash_map搜索二叉樹(shù)紅黑樹(shù)等來(lái)進(jìn)行統(tǒng)計(jì)次數(shù)。然后就是取出前N個(gè)出現(xiàn)次數(shù)最多的數(shù)據(jù)了,可以用第6題提到的堆機(jī)制完成。9.1000萬(wàn)字符串,其中有些是重復(fù)的,需要把重復(fù)的全部去掉,保留沒(méi)有重復(fù)的字符萬(wàn)字符串,其中有些是重
9、復(fù)的,需要把重復(fù)的全部去掉,保留沒(méi)有重復(fù)的字符串。請(qǐng)?jiān)趺丛O(shè)計(jì)和實(shí)現(xiàn)?串。請(qǐng)?jiān)趺丛O(shè)計(jì)和實(shí)現(xiàn)?方案1:這題用trie樹(shù)比較合適,hash_map也應(yīng)該能行。10.一個(gè)文本文件,大約有一萬(wàn)行,每行一個(gè)詞,要求統(tǒng)計(jì)出其中最頻繁出現(xiàn)的前一個(gè)文本文件,大約有一萬(wàn)行,每行一個(gè)詞,要求統(tǒng)計(jì)出其中最頻繁出現(xiàn)的前10個(gè)詞,請(qǐng)給出思想,給出時(shí)間復(fù)雜度分析。詞,請(qǐng)給出思想,給出時(shí)間復(fù)雜度分析。方案1:這題是考慮時(shí)間效率。用trie樹(shù)統(tǒng)計(jì)每個(gè)詞出現(xiàn)的次數(shù),時(shí)間復(fù)
10、雜度是O(nle)(le表示單詞的平準(zhǔn)長(zhǎng)度)。然后是找出出現(xiàn)最頻繁的前10個(gè)詞,可以用堆來(lái)實(shí)現(xiàn),前面的題中已經(jīng)講到了,時(shí)間復(fù)雜度是O(nlg10)。所以總的時(shí)間復(fù)雜度,是O(nle)與O(nlg10)中較大的哪一個(gè)。11.一個(gè)文本文件,找出前一個(gè)文本文件,找出前10個(gè)經(jīng)常出現(xiàn)的詞,但這次文件比較長(zhǎng),說(shuō)是上億行或十億個(gè)經(jīng)常出現(xiàn)的詞,但這次文件比較長(zhǎng),說(shuō)是上億行或十億行,總之無(wú)法一次讀入內(nèi)存,問(wèn)最優(yōu)解。行,總之無(wú)法一次讀入內(nèi)存,問(wèn)最優(yōu)解。方
11、案1:首先根據(jù)用hash并求模,將文件分解為多個(gè)小文件,對(duì)于單個(gè)文件利用上題的方法求出每個(gè)文件件中10個(gè)最常出現(xiàn)的詞。然后再進(jìn)行歸并處理,找出最終的10個(gè)最常出現(xiàn)的詞。12.100w個(gè)數(shù)中找出最大的個(gè)數(shù)中找出最大的100個(gè)數(shù)。個(gè)數(shù)。方案1:在前面的題中,我們已經(jīng)提到了,用一個(gè)含100個(gè)元素的最小堆完成。復(fù)雜度為O(100wlg100)。方案2:采用快速排序的思想,每次分割之后只考慮比軸大的一部分,知道比軸大的一部分在比100多的時(shí)候,采
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 制造物聯(lián)海量實(shí)時(shí)數(shù)據(jù)處理方法研究.pdf
- 基于Hadoop的海量車(chē)載物聯(lián)網(wǎng)數(shù)據(jù)處理方法研究.pdf
- 海量數(shù)據(jù)處理技術(shù)研究與應(yīng)用.pdf
- 基于云計(jì)算的海量球形地形數(shù)據(jù)處理方法的研究.pdf
- 海量銷(xiāo)售數(shù)據(jù)處理平臺(tái)的設(shè)計(jì)與實(shí)現(xiàn).pdf
- 船舶監(jiān)控系統(tǒng)中海量數(shù)據(jù)處理技術(shù)研究.pdf
- 基于Hadoop的海量工程數(shù)據(jù)處理技術(shù)研究.pdf
- 基于海量高維圖像的大數(shù)據(jù)處理框架.pdf
- 基于Hadoop海量數(shù)據(jù)處理關(guān)鍵技術(shù)研究.pdf
- 基于Hadoop的海量數(shù)據(jù)處理模型研究和應(yīng)用.pdf
- 數(shù)據(jù)挖掘中海量數(shù)據(jù)處理算法的研究與實(shí)現(xiàn).pdf
- 基于Hadoop的海量日志數(shù)據(jù)處理研究與應(yīng)用.pdf
- 海量數(shù)據(jù)處理與挖掘關(guān)鍵技術(shù)研究.pdf
- Hadoop平臺(tái)下基于HBase的海量數(shù)據(jù)處理研究.pdf
- 海量日志數(shù)據(jù)處理與查詢優(yōu)化技術(shù)研究.pdf
- 基于Hadoop的海量電能質(zhì)量數(shù)據(jù)處理研究.pdf
- 變形觀測(cè)方法及其數(shù)據(jù)處理
- 基于QoS的電信網(wǎng)絡(luò)海量數(shù)據(jù)處理與研究.pdf
- 誤差理論與數(shù)據(jù)處理總結(jié)
- 智慧高速海量異構(gòu)數(shù)據(jù)處理關(guān)鍵技術(shù)研究.pdf
評(píng)論
0/150
提交評(píng)論