请教一道面试题!

2019-05-19 13:51:29 +08:00
 leisurelylicht

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

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

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

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

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

4828 次点击
所在节点    Python
35 条回复
oblivious
2019-05-19 14:43:53 +08:00
文件有多大?

文件能放入内存,的确 10 分钟能写完。文件远大于内存,我这里有一个挺傻的思路:按照每分钟建 24*60 文件,每个文件内再排序。(大文件总不能除以 1440 )还不能丢进内存吧 :)
leisurelylicht
2019-05-19 14:58:40 +08:00
@oblivious 我觉得他特别说过文件特别大,应该就是指不能一次性读入内存。所以我才往外部排序上考虑的。
leisurelylicht
2019-05-19 15:00:13 +08:00
@leisurelylicht 我当时就是你这个思路,给他说了,但是面试官没什么反应。我觉得这么做的话涉及到读写文件,10 分钟内也写不完啊。
di94sh
2019-05-19 15:33:11 +08:00
我感觉每分钟不是从 1 秒到 60 秒,而是一个窗口,所以需要为这个窗口建缓存,每次读入一秒的数据,然后再过期一秒的数据,之后统计这个窗口内 ip 超过 100 的。
xinyusir
2019-05-19 15:36:53 +08:00
感觉用 Node 的话 stream 可以完美解决。。。。
di94sh
2019-05-19 15:45:13 +08:00
@xinyusir #5 文件描述符就是基于流的, 每次读一行就行了.
binux
2019-05-19 15:55:37 +08:00
日志不都是按照时间排序的吗,一秒一个窗口读一遍就行了啊
Vegetable
2019-05-19 15:57:21 +08:00
关键词是一个大文件.
日志默认应该是在时间上连续的,所以无论文件有多大,当前应该只处理 60 秒的数据.不应该有切割文件的操作.
如果是判断自然分钟,就是从 0 开始读取,读取到下一个分钟结算一下当前分钟的数据,给出达标结果,再继续处理下一个分钟的数据.
如果是连续 60 秒的话,这个还挺麻烦的,因为 24 小时的不同窗口从 1440 个一下子变成了 86400 个了,会麻烦不少.
smdbh
2019-05-19 16:01:46 +08:00
我想到的一个: 逐行读取日志文件,对于每个 ip,创建一个文件,写入此行。
日志文件应该按时间排序的
所以对于每个 ip 文件,写入的时候就判断与第一行的时间差和之间的行数,比如是否差 100 行且时间差小于 1min
删掉超过 1 分钟的 log,满足条件,则记录此 ip
owt5008137
2019-05-19 16:05:54 +08:00
日志文件。一般时间都是顺序的呀。个人想法:
可以按 ip,hashmap,如果精度要求是秒级就一个 60 长度的数组统计下次数。如果不是分钟级别精度就可以那直接统计一分钟的次数就好了。
然后内存够就存内存,不够就落地。
日志内容顺序扫一遍就完了
lhx2008
2019-05-19 16:08:04 +08:00
就像 #7 说的,顺序读,然后 Python 这边搞个 dict 做统计应该就可以了,内存只用记录 1 分钟内的所有 IP,过了一分钟就 clear() ,毕竟 10 分钟写不了什么
oblivious
2019-05-19 16:08:35 +08:00
如果是日志文件按时间排序好了,又不要求连续 60s,数据量不多那就是一个 python dict 就能搞定的事情呀~

读完这一分钟把 dict 丢掉就好了,hhhh
qdzzyb
2019-05-19 16:13:39 +08:00
插眼
g7rhythm
2019-05-19 16:15:15 +08:00
“每分钟访问次数超过 N 次” 与 “单分钟访问次数超过 N 次” 的差别在于一个求均值,一个求峰值。
既然是求均值,那么最简单的做法就是逐条记录 IP 的总访问次数,然后除以总时间范围 M 分钟,如果文件过大就用流读取。

然后如果以每一分钟去统计一次,那么就会记录到峰值超过 100 次的 IP,但是总时间内每分钟并没有超过 100 次。
实际上这可能是一个防止数据采集的办法,防范的重点在于不要被采集过多的数据,而不是特别在意峰值高低。
lolizeppelin
2019-05-19 16:18:54 +08:00
挺好的题目呀 其实和大访问量的网站怎么过滤高频 IP 一个思路
lolizeppelin
2019-05-19 16:23:05 +08:00
以 ip 为 key
pipe 管道去 incr,并计数,超过就是异常 ip

key 身存时间 1 分钟
Vegetable
2019-05-19 16:37:00 +08:00
按照分钟统计还是比较简单的,连续 60 秒的比较麻烦,但是逻辑差不多.一般监控也没必要搞那么精确吧

https://gist.github.com/luliangce/22c2ece57d0b22faf51827ebe47e1d6b
hhhsuan
2019-05-19 16:41:22 +08:00
思路应该还是比较容易想到的,但我肯定 10 分钟内写不出来,算上 debug 的时间我觉得我要花 1 个小时。
Pzqqt
2019-05-19 16:52:44 +08:00
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
2019-05-19 17:10:01 +08:00
哎,真是的,这么简单的问题有什么好讨论的

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

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/565534

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX