关于一道海量数据面试题的疑问, 希望大佬能给我看看

[MonsterTan]

我在 csdn 看到的一个博客 里面有一道这样的题

1、海量日志数据，提取出某日访问百度次数最多的那个 IP。

首先是这一天，并且是访问百度的日志中的 IP 取出来，逐个写入到一个大文件中。注意到 IP 是 32 位的，最多有个 2^32 个 IP。同样可以采用映射的方法，比如模 1000，把整个大文件映射为 1000 个小文件，再找出每个小文中出现频率最大的 IP （可以采用 hash_map 进行频率统计，然后再找出频率最大的几个）及相应的频率。然后再在这 1000 个最大的 IP 中，找出那个频率最大的 IP，即为所求。

或者如下阐述： 算法思想：分而治之+Hash 1.IP 地址最多有 2^32=4G 种取值情况，所以不能完全加载到内存中处理；  2.可以考虑采用“分而治之”的思想，按照 IP 地址的 Hash(IP)%1024 值，把海量 IP 日志分别存储到 1024 个小文件中。这样，每个小文件最多包含 4MB 个 IP 地址；  3.对于每一个小文件，可以构建一个 IP 为 key，出现次数为 value 的 Hash map，同时记录当前出现次数最多的那个 IP 地址； 4.可以得到 1024 个小文件中的出现次数最多的 IP，再依据常规的排序算法得到总体上出现次数最多的 IP ；

在算法思想中的第二步骤:

把海量 IP 日志分别存储到 1024 个小文件中。这样，每个小文件最多包含 4MB 个 IP 地址
我的理解,就是遍历一个海量的 log 文件,然后根据 hash(ip)%1024 到多个文件中,关键有一地方为特别不理解就是,当我遍历的过程中不就相当于我从海量文件中把数据读取到了内存中,这样内存不是还是装不下吗? 希望大佬们能给我这个 noob 一个指点.

[byteli]

内存不用担心装不下，你又不是一下子读完的，，你要闲着无聊 512 个字节 512 个字节读的话内存占 512 个字节就够了

[MonsterTan]

@byteli 在 java 中也是可以的吗？我一次读取 512 个字节，不主动释放的话，他会帮我把 512 个字节的数据自动释放掉吗？　如果是 C++的话我还能理解，我读完处理之后自己主动释放掉就可以了．但是在 Java 中还没有主动释放这一说，JVM 会帮我处理吗？感谢大佬！

[mooncakejs]

问题出现在排序， 储存 IP 就需要 4g，所以不能在内存中排序， 只能分治。

[MonsterTan]

@mooncakejs 分治我能理解，整个思路我是懂的．主要就是在我加粗的那一快．
关键有一地方为特别不理解就是,当我遍历的过程中不就相当于我从海量文件中把数据读取到了内存中,这样内存不是还是装不下吗
这个地方我不太理解，因为 Java 中是无法主动释放内存的，JVM 会处理吗?

[hilbertz]

归并排序

[zwzmzd]

@MonsterTan c++也不用释放，创建一个固定大小的缓冲区，每次读一段数据往里放就行，不用反复创建缓冲区的

[misaka19000]

你从 1024 个文件中，每个文件中只取最大值，所以合并节点只需要对 1024 个 IP 做排序

[MonsterTan]

@zwzmzd 哦，我懂了，您指的意思是我就开辟一段内存空间，每次读进来放到相应的内存空间就行了，下次来再覆盖掉就可以了是吗?

[quaack]

只是频率最高的 IP 的话，可以考虑 Lossy Count 或者 Count-Min Sketch 这种算法，因为只有大部分 IP 访问量会很少。

[zwzmzd]

@MonsterTan 是的

[MonsterTan]

@zwzmzd 好的，感谢．

[MonsterTan]

@quaack 主要还是考虑一个内存不足的问题，而且一般不借助任何工具

[quaack]

@MonsterTan 这两种是基于概率的算法，内存开销很小。
https://soulmachine.gitbooks.io/system-design/content/cn/top-k-frequent-ip-in-one-hour.html

[GGGG430]

读取一行之后将其取模放入相应小文件后即销毁存储该行的变量，然后读取下一行

[EthanDon]

我不是做这个的，不过我感觉你的问题有点像 外部排序？
将大文件分段读入内存进行排序，然后将结果再分别写回硬盘，最后根据需要扫描每个文件的前 N 个数据进行归并获得最终结果，是这样吗？