请教一道面试题！

[leisurelylicht]

前几天去腾讯面试 Python 的时候遇到一道面试题，如下

有一个大文件日志，日志内容包含 访问时间 和 访问 IP，问如何统计每分钟访问次数超过 100 次的 IP ？

面试官说手写代码大概是 10 分钟的量。

我觉得可以用桶排序切割大文件为小文件后再读到内存里统计。但不知道对不对。

求解是不是有更好的方法？

根据大家提供的思路搞了个demo

改自@Vegetable的代码

https://gist.github.com/leisurelicht/d7d0005abdf8b743f90bc99ba35ac0d2@

[oblivious]

文件有多大？

文件能放入内存，的确 10 分钟能写完。文件远大于内存，我这里有一个挺傻的思路：按照每分钟建 24*60 文件，每个文件内再排序。（大文件总不能除以 1440 ）还不能丢进内存吧 ：）

[leisurelylicht]

@oblivious 我觉得他特别说过文件特别大，应该就是指不能一次性读入内存。所以我才往外部排序上考虑的。

[leisurelylicht]

@leisurelylicht 我当时就是你这个思路，给他说了，但是面试官没什么反应。我觉得这么做的话涉及到读写文件，10 分钟内也写不完啊。

[di94sh]

我感觉每分钟不是从 1 秒到 60 秒，而是一个窗口，所以需要为这个窗口建缓存，每次读入一秒的数据，然后再过期一秒的数据，之后统计这个窗口内 ip 超过 100 的。

[xinyusir]

感觉用 Node 的话 stream 可以完美解决。。。。

[di94sh]

@xinyusir #5 文件描述符就是基于流的, 每次读一行就行了.

[binux]

日志不都是按照时间排序的吗，一秒一个窗口读一遍就行了啊

[Vegetable]

关键词是一个大文件.
日志默认应该是在时间上连续的,所以无论文件有多大,当前应该只处理 60 秒的数据.不应该有切割文件的操作.
如果是判断自然分钟,就是从 0 开始读取,读取到下一个分钟结算一下当前分钟的数据,给出达标结果,再继续处理下一个分钟的数据.
如果是连续 60 秒的话,这个还挺麻烦的,因为 24 小时的不同窗口从 1440 个一下子变成了 86400 个了,会麻烦不少.

[smdbh]

我想到的一个： 逐行读取日志文件，对于每个 ip，创建一个文件，写入此行。
日志文件应该按时间排序的
所以对于每个 ip 文件，写入的时候就判断与第一行的时间差和之间的行数，比如是否差 100 行且时间差小于 1min
删掉超过 1 分钟的 log，满足条件，则记录此 ip

[owt5008137]

日志文件。一般时间都是顺序的呀。个人想法：
可以按 ip，hashmap，如果精度要求是秒级就一个 60 长度的数组统计下次数。如果不是分钟级别精度就可以那直接统计一分钟的次数就好了。
然后内存够就存内存，不够就落地。
日志内容顺序扫一遍就完了

[lhx2008]

就像 #7 说的，顺序读，然后 Python 这边搞个 dict 做统计应该就可以了，内存只用记录 1 分钟内的所有 IP，过了一分钟就 clear() ，毕竟 10 分钟写不了什么

[oblivious]

如果是日志文件按时间排序好了，又不要求连续 60s，数据量不多那就是一个 python dict 就能搞定的事情呀~

读完这一分钟把 dict 丢掉就好了，hhhh

[qdzzyb]

插眼

[g7rhythm]

“每分钟访问次数超过 N 次” 与 “单分钟访问次数超过 N 次” 的差别在于一个求均值，一个求峰值。
既然是求均值，那么最简单的做法就是逐条记录 IP 的总访问次数，然后除以总时间范围 M 分钟，如果文件过大就用流读取。

然后如果以每一分钟去统计一次，那么就会记录到峰值超过 100 次的 IP，但是总时间内每分钟并没有超过 100 次。
实际上这可能是一个防止数据采集的办法，防范的重点在于不要被采集过多的数据，而不是特别在意峰值高低。

[lolizeppelin]

挺好的题目呀 其实和大访问量的网站怎么过滤高频 IP 一个思路

[lolizeppelin]

以 ip 为 key
pipe 管道去 incr,并计数,超过就是异常 ip

key 身存时间 1 分钟

[Vegetable]

按照分钟统计还是比较简单的,连续 60 秒的比较麻烦,但是逻辑差不多.一般监控也没必要搞那么精确吧

https://gist.github.com/luliangce/22c2ece57d0b22faf51827ebe47e1d6b

[hhhsuan]

思路应该还是比较容易想到的，但我肯定 10 分钟内写不出来，算上 debug 的时间我觉得我要花 1 个小时。

[Pzqqt]

Emmm 不知道这样解是否正确

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from collections import defaultdict, Counter

dic = defaultdict(lambda: set())

# 假设该日志文件为 log.log
with open("log.log", "r", encoding="utf-8") as f:
while True:
l = f.readline().strip()
if not l.strip():
break
# 假设该日志文件每行的格式为:
# HH:MM:SS XXX.XXX.XXX.XXX
try:
time, ip = l.split(" ")
except ValueError:
continue
dic[time.rsplit(":")[0]].add(ip)

for time_min, ips in dic:
for ip, count in Counter(ips):
if count > 100:
print(time_min, ip, count)

[binux]

哎，真是的，这么简单的问题有什么好讨论的

def group_by_second(logs):
start = null
window = defaultdict(int)
for time, ip in logs:
if time - start > 1000:
yield window
start = null
window = {}
if start is null:
start = time
window[ip] += 1

windows = []
ip_cnt = defaultdict(int)
for window in group_by_second(logs):
windows.append(window)
if len(windows) > 60:
for ip, cnt in windows.pop(0):
ip_cnt[ip] -= cnt
for ip, cnt in window:
ip_cnt[ip] += cnt
if ip_cnt[ip] > 100:
print ip

[leisurelylicht]

@Vegetable
@binux
@Pzqqt
@oblivious
@lhx2008
@owt5008137
按这么考虑还真的是 10 分钟量的代码，是我当时考虑的太复杂了

@Vegetable 你的代码缩进乱掉了，虽然我还是看懂了

[makdon]

问题：有一个大文件日志，日志内容包含 访问时间 和 访问 IP，问如何统计每分钟访问次数超过 100 次的 IP ？
keyword：日志、大文件、访问频率

题目并没有说明的内容：
日志时间跨度：这么大个文件是一天日志还是一分钟日志,还是说其它时间跨度
分钟切分粒度：假如在 00 分后半分钟访问 50 次，01 分钟前半分钟访问 51 次，算不算“访问次数超过 100 次”

那就按照最极端的情况来考虑：这个文件是两分钟的日志文件，体积极大，需要任意 60 秒时间段内访问次数不超过 100.

按照这种极端情况考虑的话，前面的“以分钟切片单位，用字典记录用户访问，每分钟清除一遍字典”之类的方法就不适用了，因为使用的内存量是跟用户量成正比的：假如日志中，有极多用户，每个用户只访问一遍，那字典需要的内存比文件本身一半（假定两分钟的日志）还要大，显然会炸内存。

我个人认为，在大文件的前提下，只能按照用户进行切片，而不是时间为单位切片，因为每分钟的数据量在这个场景上没有上限，但是用户的数据上限是 100。而且使用用户 IP 作为切片的 Key，可以上 Hadoop、Spark 等分布式计算框架。（时间作为 key 也可以上分布式，不过可能切片太大，计算量集中到单机）。

当本地操作时，时间 O(n)，内存占用 O(1)，硬盘占用 O(n)；用分布式框架时，时间 O(n)，内存 O(n)，硬盘 O(1)

在加个极端条件：这个大文件是 1 个用户在 2 分钟内疯狂访问生成的几十 G 的日志。检查可知，就算是这种情况，按照用户切片，最多只需要记录 100 次访问记录。

最后，我是云编程玩家，以下是伪代码：


def map2file(log):
with open(log['ip]) as file:
if file.first_line != 'Hit':
file.append(log)
check(file)


def check(file):
while last_line.time - first_line.time > 60:
delete(first_line)
if file.num_of_line >= 100:
delete_all_lines()
file.append("Hit")




if __name__ == '__main__':
with open('file') as logs:
for log in logs:
map2file(log)

result = []
for file in working_dir:
result.append(file.name)




(其实就是把那个字典记录在文件系统里面
(是不是觉得我扯了这么多花里胡哨的，10 行代码 9 行 error
(总感觉我哪里搞错了但是没找出来，有错误请把我往死里锤（反正不可能真的顺着网线砍我（

[makdon]

@makdon #22
果然把我的缩进都删掉了。。。
主函数写错了，应该是
if __name__ == '__main__':
with open('file') as logs:
for log in logs:
map2file(log)

result = new_file
for file in working_dir:
if file 点 first_line == 'Hit':
result 点 append(file 点 name)


附 gist：
htt 他 ps:/不 /gist 点 gi 让 thub 点 co 我 m/Mak 插 Don/4aa9 外 138b9f 链 3a5c89c745b6f4b9a5ea82.js

[makdon]

没有考虑的极端情况：
日历不是按时间排序的（不按时间排序就不是日志了吧。。。
因为服务器时间同步导致的日志时间抖动：例如在 00：00：05 的时候，服务器收到校准时钟信号，把自己时间调到 00：00：00，那出来的日志就是：
00：00：03：blablabla
00：00：04：blablabla
00：00：05：blablabla
00：00：00：blablabla
00：00：01：blablabla

[zgl263885]

滑动窗口算法，窗口宽度为一分钟，统计窗口内 ip 访问次数超过 100 次的 ip。

[MissThee]

虽然不会 puthon,但是感觉用一门语言实现读取文件，计数，1 分钟执行一次的循环任务，应该不会很难吧😅

[Oz2011]

每条记录在文件里本身应该是排序的，一条一条读出来，
ip 为 key, value 是一个时间的有序 list

同时有另外一个 map, ip 为 key, value 是这个 ip 最早的访问时间 （也可以想办法把两个放到同一个 map 里面）

每读一个时间，
if (读出时间 - 60s >= 起始时间)，如果 list size > 100 输出，不然这个 ip 就能删掉了。
else 时间插入对应 ip 的 list

[Oz2011]

这个外部排序分割文件没关系啊，顺序处理就行了

[zgq3337]

用 Dict，以 IP 为 key，时间加入列表，每次对应 key 有变化，就对当前索引前 100 次作时间差计算，超过 1 分钟标记

[Pythoner666666]

python 不是有迭代器么，每次只读一行到内存中，这样就可以解决了吧

[crazypig14]

实际写代码虽然顺序处理为了并发还是得文件切割，切割处小心一点，得有 100 秒的重合

[luckymerlin]

不是 sorted 的先 sort，然后 sliding window + hashmap

[lanshee]

with open('filepath') as f:
for line in f:
# 假定起始时间为 00:00:00

[lanshee]

@lanshee 完犊子.我还没写完.

[lanshee]

time_start = None
with open('filepath') as f:
for line in f:
# 1. 找到起始时间格式化字符串通过时间转换转成 int
# 2. 记录时间差为一分钟的结束时间
# 3. 判断是否在这一分钟内
# 4. 如果在,从该行日志中找到 ip
# 5. 利用 redis 为 ip 记录访问次数
# 6. 判断该次数是否超过 100,如果超过,就记录

ps: 求大神指点.