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

brioche
  • 36

百度面试题,大致意思是说,有个文件,文件很大不能一次性读取(可能是不能一次性加载到内存中),文件中存放的是IP地址,如何快速找出重复的IP地址?求指点思路。

文件很大,可以逐行读取,append到list中,取set,再取差集,不知是否可行?

回复
阅读 4k
5 个回答

不可行。

  1. append 到 list中,,跟直接一次性读取没差,都是要占用所有数据的内存;
  2. 取差集只能set - list,不能 list - set

条件不充分阿。如果有1000万条记录地址,只有几个重复,目前想到的可以先排序,然后map-reduce。如果有1000万条记录,其中900万是重复的,用hashTable就解决了。

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

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

首先把ip转成int(网上一堆算法请百度)
然后做一个大的数组
比如192.168.3.4转换后为3232236292
对应的数组为 int array[3232236292-1]做计数即可
再简化一下,由于数组要预先分配,这里用map就行

先生成一个包含所有ip的map 如map<ip,1>,也就1000万条。(这个可以优化下)然后一条一条从文件读,读之后从 map里面取v=map.get(ip) 如果 v=1,map.put(ip,0),如果 v=0 说明已经有重复的了,console.log(ip)

宣传栏