请教一道面试题!

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

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

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

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

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

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

4828 次点击
所在节点    Python
35 条回复
leisurelylicht
2019-05-19 17:40:18 +08:00
@Vegetable
@binux
@Pzqqt
@oblivious
@lhx2008
@owt5008137
按这么考虑还真的是 10 分钟量的代码,是我当时考虑的太复杂了

@Vegetable 你的代码缩进乱掉了,虽然我还是看懂了
makdon
2019-05-19 20:11:09 +08:00
问题:有一个大文件日志,日志内容包含 访问时间 和 访问 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
2019-05-19 20:17:47 +08:00
@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
2019-05-19 20:26:28 +08:00
没有考虑的极端情况:
日历不是按时间排序的(不按时间排序就不是日志了吧。。。
因为服务器时间同步导致的日志时间抖动:例如在 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
2019-05-19 20:47:02 +08:00
滑动窗口算法,窗口宽度为一分钟,统计窗口内 ip 访问次数超过 100 次的 ip。
MissThee
2019-05-19 20:47:17 +08:00
虽然不会 puthon,但是感觉用一门语言实现读取文件,计数,1 分钟执行一次的循环任务,应该不会很难吧😅
Oz2011
2019-05-19 22:09:43 +08:00
每条记录在文件里本身应该是排序的,一条一条读出来,
ip 为 key, value 是一个时间的有序 list

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

每读一个时间,
if (读出时间 - 60s >= 起始时间),如果 list size > 100 输出,不然这个 ip 就能删掉了。
else 时间插入对应 ip 的 list
Oz2011
2019-05-19 22:10:35 +08:00
这个外部排序分割文件没关系啊,顺序处理就行了
zgq3337
2019-05-20 08:36:58 +08:00
用 Dict,以 IP 为 key,时间加入列表,每次对应 key 有变化,就对当前索引前 100 次作时间差计算,超过 1 分钟标记
Pythoner666666
2019-05-20 09:06:26 +08:00
python 不是有迭代器么,每次只读一行到内存中,这样就可以解决了吧
crazypig14
2019-05-20 13:30:17 +08:00
实际写代码虽然顺序处理为了并发还是得文件切割,切割处小心一点,得有 100 秒的重合
luckymerlin
2019-05-20 14:11:35 +08:00
不是 sorted 的先 sort,然后 sliding window + hashmap
lanshee
2019-06-03 18:34:16 +08:00
with open('filepath') as f:
for line in f:
# 假定起始时间为 00:00:00
lanshee
2019-06-03 18:34:34 +08:00
@lanshee 完犊子.我还没写完.
lanshee
2019-06-03 18:43:28 +08:00
time_start = None
with open('filepath') as f:
for line in f:
# 1. 找到起始时间格式化字符串通过时间转换转成 int
# 2. 记录时间差为一分钟的结束时间
# 3. 判断是否在这一分钟内
# 4. 如果在,从该行日志中找到 ip
# 5. 利用 redis 为 ip 记录访问次数
# 6. 判断该次数是否超过 100,如果超过,就记录

ps: 求大神指点.

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

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

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

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

© 2021 V2EX