1樓：好奇的投資者
看不慣採用二分查詢的各位，怒答。
我想對採用二分查詢的各位同學拋兩個問題。
一、在二分資料的時候，如何確保」壞資料」在同乙個分塊呢，萬一你分的兩個分塊恰好都有部分錯誤資料呢？如下圖
二、在解決第乙個問題的前提下，如果採用二分查詢，會出現重複計算hash值的情況，此時複雜度肯定大於N。
比如每次二分一次，部分hash可能會重複計算。如下圖陰影部分會被計算多次。
採用類似於rsync滾動查詢演算法或者採用默克爾樹的演算法( @戴斯孟 的回答也提到此處)都比較好解決這兩個問題。
這兩種方式當然都是比較hash值，準確來講是資訊摘要，而不是傳整個檔案-_-||
找到位置後，比如分塊為2MB，然後開始替換。這樣網路傳輸也不會占用太多的時間。
在檔案較大的情況下，如果檔案錯誤不止一處，而且經常容易出錯，此時符合要求的應該是默克爾樹。
默克爾樹在位元幣，BT協議上也有應用。在錯誤不止一處的情況下，建議採用默克爾樹的方式。
注:以上的hash都是指代資訊摘要演算法！可根據自己的情況來選擇資訊摘要演算法，如sha256，sha1，md5等等。
2樓：成雋
資料庫中有類似問題：
超大隨機資料集，要命中一些位置不確定的資料，全表還是索引。
現實答案依賴兩個因素：
1）結果物理分布特點
2）結果在總資料佔比。
傳統尋道cost>>讀取，且結合塊大小/單條資料大小。
經驗上10%以上資料用索引就可能得不償失。
有答案提的分層hash，本質就是分層索引。
Hash還是其他演算法帶來的效益只是層數差別，沒必要糾結。
如果只用定位資料位置，不用讀出。
那不論現實還是理論，比較索引樹都優於全讀。
但構成索引樹成本就已經超過全讀成本。
現實中的系統都會把這個成本攤在每次的寫操作。
計算機所有瓶頸都在傳輸不在計算頻率，演算法能帶來最小的核內/核外傳輸才是優劣關鍵。
題目特意提中美伺服器，那麼網路已是潛在題設，傳輸就應該盡量避免。
通過塊指紋來確定檔案一致性在IBM儲存產品系中有硬體實現，專利坑也已被佔。
現實中就是這麼幹的。
3樓：
這道題尼瑪在前幾天校園招聘時我就被問到了碉作為法盲的我答用二分查詢加 hash 居然和排名第一(目前)給出的思想差不多不過我不知道這居然是乙個知名演算法
4樓：
題裡說了是大檔案，有多大？不確定，算hash值所用的時間也確定不了啦。
So：二分或直接分段都不怎麼靠譜。
基本思路還是分段，這裡考慮到國際網的延時比較大，匹配一下算hash的時間和網路延時。
探測網路的延時
根據時間選擇合適的分段大小（本地記憶體、硬碟考慮進來後算hash的時間）
然後分段hash對比mark有問題的段
對已經mark的段二分、算hash、合併傳送比對重複上一步，二分到很小的段後直接段比對
只是思路
5樓：zhxw
大檔案假設是1T。
1、校驗和是否可信？
也就是錯幾位的校驗和是否可能相同？
如果不可信的話就直接傳過去，靠飛機或高速網路，再一位一位的比。
這裡是假設可信的情況。
2、平衡校驗時間和傳輸時間。
這裡問題是，是否是一定是二分？
比如檔案分成8M份，每部分128K，對份計算校驗和，假如校驗和長是4B，需要傳輸32MB校驗和，返回對比結果，總資料傳輸量33MB。
判斷每個錯誤位，如果錯誤比較少，比如只有少於1k個部分（大小128k）錯誤，直接傳全部資料（<128M）對比。這種情況我覺得可能是最常見的，費時也比較小。
如果錯誤比較多，把錯誤的位細分，再傳。
似乎可以設計乙個協議。。。。
6樓：徐磊
可以考慮Merkle Tree，這個樹本質上和Hash Tree類似的，而且是二叉樹方便做二分查詢。具體的理論可以查下維基百科，手機回答不方便貼圖了。
兩邊的伺服器各自根據這個大檔案開始構造這個樹，然後傳輸這個樹到一邊進行比較，找出有差異的葉子節點，單獨傳輸這些葉子節點就可以了。
解決方法比較容易理解，關鍵是如何切分檔案塊，保證比較的正確
7樓：堯羽行
非程式設計師也來湊熱鬧。
時間複雜度如果用二分不就是log(n)麼。如果還要快，只能建立索引就是程式設計師說的雜湊表。但是，找到錯誤或者說不一樣的地方不一定是雜湊表。
類似於大家來找茬，直接把兩個檔案進行or運算，減去兩個檔案。從一堆零裡面找一就可以利用稀疏矩陣的演算法了。
8樓：
逼我來吐槽。既然中美兩個伺服器檔案內容一致，那是怎麼知道其中乙個檔案的幾位元組的錯誤是故障引起而不是人為改動？如果伺服器的檔案內容已經不一致，那就和題設中兩個伺服器的內容一致矛盾了，請問那這兩個檔案平時是怎麼保持一致的？
就拋開這些不談，就假設兩個伺服器的檔案內容不一樣了，而且在一樣的時候算過乙個正確內容的hash值，那麼這時候就已經可以知道是哪台伺服器的內容出問題了，如題所述，是美國的伺服器錯了，我要吐槽的是，這時候美帝有哪個神人就能知道此檔案僅有幾個位元組出錯，是誰給了你這樣的信心？這個數量級是怎麼得出來的？！！
企業級的磁碟陣列上壞幾塊硬碟是常見的，有各種軟硬虛實的raid以及眾多備盤來提供保障，只要不同時壞超過一定數目的硬碟，資料就很安全，而錯幾個位元組這種奇葩事情，在百T級的磁碟陣列上，反正我是真心沒見過。然後正常伺服器本地硬碟一般標配最少都是raid1，你們懂的，即便如此，伺服器的本地硬碟通常也被定時備份到陣列裡了，有的保守的地方甚至還會定期自動備份到磁帶裡。有些資料重要的地方甚至會用另乙個或幾個更大的磁碟陣列來備份小一點的磁碟陣列做雙保險。
發生這樣的事情，解決方案當然是資料回滾！實際當中，如果兩個大檔案常年遠端同步，那這個檔案一定是有增量同步日誌的，也一定會定期備份的，它所在的fs也會定期做快照和增量快照的，用日誌和這些備份資料可以在本地構建出最近一次同步後的檔案，沒必要也不會去通過網路去反覆比較兩個大檔案。
吐槽完了，二分Hash吧，但是最壞情況需要估計到整個檔案滿目瘡痍的可能性，有可能到最後還不如把整個檔案重新傳一遍。
9樓：謝然
如圖，先分塊hash，然後再對每行及每列的hash們再做一次hash
假設壞點的位置為圖中的位置，那麼打圈的兩個hash一定不相同，於是可以反推出壞點所在的塊
再對壞點所在的塊接著做這種運算，可以進一步縮小範圍……
10樓：
時間複雜度和普通的對比一樣，就是O(n)。但是具體實現上並不是逐個位元組地比較。
這裡瓶頸是傳輸，要讓傳送的檔案盡量的少。所以，可以分塊做hash，比對hash值，如果相同，那麼對應的塊就沒有錯誤，否則繼續往下細分這個塊(對這個塊可以繼續遞迴採用這種分塊hash的思路，直到足夠小)。
可以參考linux下rsync的實現，rsync是保持兩個檔案同步，這個問題可以看做是rsync的簡化版本。
左耳朵耗子曾經發過乙個博文，介紹得比較清楚，http://coolshell.cn/articles/7425.html
11樓：陳碩
時間複雜度肯定是O(N)，不可能再低了。
演算法用rsync。
如果要實際執行時間短，那麼需要具體知道檔案大小、伺服器之間的頻寬、網路延遲。
一道面試題，這是什麼演算法啊？
朱涵俊 答案應該是2 1 0 0 0 1 0 0 0 6 首先0不可能出現0次。其次第二排加起來不可能超過10，因為總共就10個數字。還有第一排數字跟第二排數字相乘之和不超過10，比如2出現4次，那麼第二排有4個2，根據上面一條，第二排數字相加不大於10。假設0出現x次，x在1至9之間，x出現y次，...
一道bat面試題 快速替換10億條標題中的5萬個敏感詞，有哪些解決思路？
汪周洋 這個題目其實這些一億條標題，五萬個敏感詞都是唬人的，就是想考你，給你乙個敏感詞表，然後從乙個文字中找出是否有敏感詞，至於替換是順手的事情，標題數量多也是要乙個個做。核心就是根據敏感詞表建乙個樹可以快速的判斷字串是否有敏感詞。這一般是bat這種公司過濾敏感詞的乙個功能，這其實考不了啥的，沒做過...
虛構一道面試題 有1 10億數字的亂序陣列，其中少了若干個數（不超過100個），怎麼找到這些少的數呢？
可以對原來的數進行快排或者堆排，從大到小排一遍然後從大到小依次減過來，如果有相減結果不是1的就是說明這裡丟了乙個數字 這裡可以多執行緒計算 不過乙個10億個元素的陣列，佔記憶體也不小呢 柳翔天 先實現高精度計算。將每個數相加，與1 10億的總和相減，得到缺失數之和將每個數的平方相加，與1 10億的平...