百度面試題，如何快速找出文件(大文件無(wú)法一次性讀取)中的重復(fù)項(xiàng)？

百度面試題，大致意思是說(shuō)，有個(gè)文件，文件很大不能一次性讀取（可能是不能一次性加載到內(nèi)存中），文件中存放的是IP地址，如何快速找出重復(fù)的IP地址？求指點(diǎn)思路。

文件很大，可以逐行讀取，append到list中，取set，再取差集，不知是否可行？

回答

編輯回答

怪痞

IPv4么…… 一共才 4Gi 個(gè)地址，到內(nèi)存里挖好坑，等著IP來(lái)跳。浪費(fèi)點(diǎn)，用int8來(lái)存也就是4GB內(nèi)存，節(jié)省點(diǎn)，用bit存的話只要500MB。思路可以活點(diǎn)，其實(shí)我覺(jué)得給出IP地址這個(gè)限制條件就是在降低難度。

IPv6的話，可能就得分治?；舅悸肪褪窍劝磧?nèi)存能承受的長(zhǎng)度去檢查地址的前幾位，碰撞了的丟同一個(gè)bucket里，然后再一個(gè)一個(gè)bucket地去看里面有沒(méi)有重的，往下也可以再分。其實(shí)DBMS整天干這事……

2017年3月8日 06:17

編輯回答

離魂曲

不可行。

append 到 list中，，跟直接一次性讀取沒(méi)差，都是要占用所有數(shù)據(jù)的內(nèi)存；
取差集只能set - list，不能 list - set

2018年7月1日 14:06

編輯回答

故林

條件不充分阿。如果有1000萬(wàn)條記錄地址，只有幾個(gè)重復(fù)，目前想到的可以先排序，然后map-reduce。如果有1000萬(wàn)條記錄，其中900萬(wàn)是重復(fù)的，用hashTable就解決了。

2017年9月8日 09:52

編輯回答

陪她鬧

首先把ip轉(zhuǎn)成int(網(wǎng)上一堆算法請(qǐng)百度)
然后做一個(gè)大的數(shù)組
比如192.168.3.4轉(zhuǎn)換后為3232236292
對(duì)應(yīng)的數(shù)組為 int array[3232236292-1]做計(jì)數(shù)即可
再簡(jiǎn)化一下，由于數(shù)組要預(yù)先分配，這里用map就行

2018年8月20日 12:30