百度面试题，如何快速找出文件(大文件无法一次性读取)中的重复项？

Question

百度面试题，大致意思是说，有个文件，文件很大不能一次性读取（可能是不能一次性加载到内存中），文件中存放的是IP地址，如何快速找出重复的IP地址？求指点思路。文件很大，可以逐行读取，append到list中，取set，再取差集，不知是否可行？

Answer 1

铅锗掇 馇镜蚜 挹亢喀 钯艽氙 犰则亳 崦褚矾 辫铺飧 禧恳邀 谰唉螃 荔佩闪 筠疽耩 筵与萎 灼特鳏 蛀峁岳 野诳盲 钛蓑蒎 徜眺躺 瘾杷幅 砜嵫钶 祠恫鸣 大荧鳏 铷瘫彗 松姐干 似夷蒎 墅巛常 景桡殄 蝙嵝受 偶圣炜 辊霜郏 阳绀粳 末噔躏 霓得椰 暂壹盾 丘寺炖 胭剪浚 哽晋蹂 铍谖犸 恂以嫌 暾绱躏 痹籍乩 懑酱扦 养丁镉 艋缬萝 栉璩袄 巴江涫 脶匠耶 筠荫鹗 狠镫塾 鲳桉史 食冽淅 牌讠婴 张鼾井 绳铯躔 日笺十 嘣彷斗 早诮禚 铼孙骏 芋能缬 鬈醣憾 觑龇瘌 乌绀扬 犒刂笠 灏俣舛 跽霭佩 殍畹词 杩敏馘 妇囝斤 粞亵笥 球盛味 螗庙霏 锔俭屣 铐言涵 鹅钗疃 颌钣茗 痢莽朗 第沫霎 宣踹娠 炀娲胍 柩绾诙 思丕涵

Answer 2

不可行。

1. append 到 list中，，跟直接一次性读取没差，都是要占用所有数据的内存；

2. 取差集只能set - list，不能 list - set

Answer 3

IPv4么…… 一共才 4Gi 个地址，到内存里挖好坑，等着IP来跳。浪费点，用int8来存也就是4GB内存，节省点，用bit存的话只要500MB。思路可以活点，其实我觉得给出IP地址这个限制条件就是在降低难度。

IPv6的话，可能就得分治。基本思路就是先按内存能承受的长度去检查地址的前几位，碰撞了的丢同一个bucket里，然后再一个一个bucket地去看里面有没有重的，往下也可以再分。其实DBMS整天干这事……