前言
之前在網(wǎng)上看過一個(gè)很有意思的問題膏执？
在單機(jī)且內(nèi)存不能放下全部足量的數(shù)據(jù)的情況下磨总，如何在1T的文件中喘批，找到重復(fù)的兩行皮壁？
看完這個(gè)問題椭更，不妨我們來思考一下如何實(shí)現(xiàn)...
一.解決方案
首先實(shí)現(xiàn)這個(gè)問題我們的第一想到的最笨的解決方案就是對(duì)每一行都與文件中后面所有的行進(jìn)行比較，這種方式的時(shí)間復(fù)雜度很高為O(n^2)...
那么有沒有更好的解決方案呢...
這個(gè)時(shí)候我們還有一種思路就是將數(shù)據(jù)放到HashSet中蛾魄，運(yùn)用Hash表不能加入重復(fù)的Key的特征來實(shí)現(xiàn)需求虑瀑，可是我們題目的條件是內(nèi)存不能放下全部足量的數(shù)據(jù)..因此這個(gè)方案不可行。
但是我們可以借鑒哈希表的思想滴须，哈希表是將數(shù)據(jù)根據(jù)HashCode經(jīng)過算法算出對(duì)應(yīng)的Hash值缴川，然后根據(jù)Hash值找到數(shù)組下標(biāo)，然后將數(shù)據(jù)存放到對(duì)應(yīng)下標(biāo)的位置描馅，然后如果有哈希沖突把夸，一般采用拉鏈法來解決..看到這里我們是否也能運(yùn)用哈希表的原理來實(shí)現(xiàn)上述需求呢？下面我們來推演一下..
首先我們可以讀取文件的每一行铭污，然后根據(jù)每一行來模仿哈希表算出它的HashCode恋日。拿到了HashCode，我們應(yīng)該干啥呢嘹狞？
哈希表中的數(shù)組岂膳，它主要是用來存儲(chǔ)相同HashCode值的地方，那我們可以類似的將相同HashCode的行存儲(chǔ)到相同的一個(gè)文件中磅网，于是我們可以根據(jù)HashCode對(duì)1000取模谈截，也就是將文件根據(jù)HashCode值分為1000份，那么每份的大小大約就是1GB的大小，這下內(nèi)存可以放的下了吧簸喂，然后我們就可以利用我們之前想到的HashSet毙死，來判斷是不是重復(fù)行了。
上述的這種思想其實(shí)就是一種分治的思想喻鳄，將文件根據(jù)某個(gè)規(guī)則切分成多分扼倘，對(duì)每一份進(jìn)行處理，最終完成需求除呵。
二.思考
1.這個(gè)過程的實(shí)現(xiàn)復(fù)雜度是多少呢再菊？
首先對(duì)每一行進(jìn)行遍歷，時(shí)間復(fù)雜度為O(n)颜曾，然后根據(jù)每個(gè)拆分后的小文件纠拔，運(yùn)用HashSet來判斷重復(fù)行，1000個(gè)小文件泛豪，每個(gè)小文件處理的最壞情況绿语，復(fù)雜度為O(n)，所有總的時(shí)間復(fù)雜度為O(n+1000*n)=O(n)候址，這種方式比上述的最笨的方式O(n^2)來說吕粹，是不是快的多呢...
2.磁盤IO會(huì)耗費(fèi)多少時(shí)間
然后我們可以算一下這個(gè)過程會(huì)磁盤IO會(huì)耗費(fèi)多少時(shí)間，首先I/O操作從文件中讀取1TB的數(shù)據(jù)按照1分鐘1GB的傳輸速度岗仑，差不多要100分鐘匹耕，然后對(duì)每個(gè)小文件進(jìn)行查重，最壞情況下差不多要100分鐘荠雕。因此這個(gè)過程對(duì)應(yīng)于單價(jià)來說稳其，耗時(shí)3個(gè)小時(shí)20分鐘。
后續(xù)如果有更好的解決方案炸卑，我會(huì)隨時(shí)更新這篇文章既鞠，歡迎大家關(guān)注！
