前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >100G的ip文件找出最多的100个ip

100G的ip文件找出最多的100个ip

作者头像
平凡的学生族
发布2019-06-15 14:58:17
3.5K1
发布2019-06-15 14:58:17
举报
文章被收录于专栏:后端技术

参考

问题

100G大小的ip文件,每行都是一条IP访问记录。计算器中重复最多的IP,即访问最多的100个IP。

单文件直接处理可行吗?

首先,鉴于现在64位os的机器内存最多也就64G,我们不可能把整个100G的文件读入内存再计算。 我们得先分析一下数据源: ip这个东西,先假设是ipv4吧。

假如你的电脑有64G内存,我们是可以这样做的:

  1. 为这个100G的文件开启一个流。
  2. 每个ip在处理时都转化为一个int型变量。
  3. 在内存里维护一个hashmap<int, long>,每个key都对应不同的ip(int型),一个key对应的value就是这个ip的出现次数(long型)(注意,在这里,我们已经默认了一个ip出现的最大次数不超过long的最大值)。
  4. 用这个流顺序读取文件,每读入一行记录,其ip对应的value数+1。

分割文件处理(2个)

可是,如果你的电脑只有32G内存呢?你没法放下所有不同的ip,因为ip加上其计数,占用空间有42G以上。为了方便计算,我们先假设所有ip是2^32个,且处理这些ip所维持的hashmap总共占48G吧。

其实把所有ip分为两组,ip%2==0和ip%2==1。 这样,维持每组ip对应的hashmap最多需要48G/2=24G。根据这个规则,我们可以把原文件拆分成两个小文件,再分别分析。具体做法如下:

  1. 开始工作前,我们准备两个空文件: "0.txt"和"1.txt"。再开启100G文件的输入流,进行读取。
  2. 每读取一行数据,将ip转为int型变量,再余2
    1. 如果余2结果为0,则将该行数据写入"0.txt"
    2. 如果余2结果为1,则将该行数据写入"1.txt"
  3. 最后,所有ip记录被分散到两个小文件中。

对于这两个文件,其特征如下:

  1. 同一个ip的所有记录都在一个文件内
  2. 每个文件所覆盖的ip最多有2^32 / 2 = 2^31个,处理这些ip所维持的hashmap占48G / 2 = 24G

所以,我们只需对每个txt分别处理一遍,得到每个文件的前100名ip,写到另一个文件里。(处理每个文件最多需要24G内存,而我们有32G内存。) 处理完两个文件后,这个文件会保存100*2=200条记录,再排序找出其频次最多的100个即可。

假如内存更少呢?

  • 假如我们只有更少内存,比如16G,怎么办?分成4个文件即可,处理每个文件最多需要12G内存。
  • 如果只有8G内存,那就再分,分成8个文件。
  • 如果是4G、2G、1G...那就以此类推,分成16个、32个、64个文件。只要分多几份,总会够用的。也正是这样,你会看到很多人的答案说,分成1024份,因为这样你的内存总会够用了。

其它讨论

  • 上文讨论的都是ipv4,如果是ipv6,虽然我没计算过,但分成1024份的时候,应该肯定够用了。
  • 不过,依然要注意一个前提,即我们上面的讨论,都假设了每个ip最多出现的次数不超过long型最大值如果超过的话,就得用更大的容量的变量来保存。不管怎样,你必须事先保证一个ip的最多出现次数,不超过其变量的类型的最大值

纠正其它文章

最后,要在此纠正其它文章的一个观点。其它文章认为,"将100G的文件按照余100的结果,分成100份,每个文件就是1G左右,所以1G的内存够用"。这个理由是错误的,原因有二:

  1. 100G在分割后,不一定刚好都是1G左右。有可能有的文件有十几G,而别的文件比较小。就算分割再多次,也有可能很多ip记录都集中在一个文件里,导致该文件大小超过了内存。
  2. 我们读取文章时,并不是要把整个文件放入内存;而是读取流,一行一行地读取并处理。所以我们要计算的,是维持所有不同的ip可能最多需要的容量大小,而不是文件本身的大小。

所以,我们是无法确定分割后,一个文件的大小的。除非基于一个前提:ip的分布是较为均匀的,分割后的文件大小差别不大。否则,不管分割几次,一个文件都可能非常大。 那么,用本文的做法,即使一个文件较大,也可以处理,但这个做法得基于另一个前提:一个ip的出现次数不超过其变量保存类型的最大值。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019.06.11 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 参考
  • 问题
  • 单文件直接处理可行吗?
  • 分割文件处理(2个)
  • 假如内存更少呢?
  • 其它讨论
  • 纠正其它文章
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档