鍍金池/ 問答/數(shù)據(jù)分析&挖掘  Python/ 百度面試題，如何快速找出文件(大文件無法一次性讀取)中的重復(fù)項(xiàng)？

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

百度面試題，大致意思是說，有個(gè)文件，文件很大不能一次性讀?。赡苁遣荒芤淮涡约虞d到內(nèi)存中），文件中存放的是IP地址，如何快速找出重復(fù)的IP地址？求指點(diǎn)思路。

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

回答
編輯回答
怪痞

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

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

2017年3月8日 06:17
編輯回答
離魂曲

不可行。

  1. append 到 list中，，跟直接一次性讀取沒差，都是要占用所有數(shù)據(jù)的內(nèi)存；
  2. 取差集只能set - list，不能 list - set
2018年7月1日 14:06
編輯回答
故林

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

2017年9月8日 09:52
編輯回答
陪她鬧

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

2018年8月20日 12:30