V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
leisurelylicht
V2EX  ›  Python

请教一道面试题!

  •  
  •   leisurelylicht · 2019-05-19 13:51:29 +08:00 · 4829 次点击
    这是一个创建于 2000 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

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

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

    第 1 条附言  ·  2019-05-21 20:23:32 +08:00

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

    改自@Vegetable的代码

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

    35 条回复    2019-06-03 18:43:28 +08:00
    oblivious
        1
    oblivious  
       2019-05-19 14:43:53 +08:00
    文件有多大?

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

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

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

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

    https://gist.github.com/luliangce/22c2ece57d0b22faf51827ebe47e1d6b
    hhhsuan
        18
    hhhsuan  
       2019-05-19 16:41:22 +08:00
    思路应该还是比较容易想到的,但我肯定 10 分钟内写不出来,算上 debug 的时间我觉得我要花 1 个小时。
    Pzqqt
        19
    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
        20
    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
    leisurelylicht
        21
    leisurelylicht  
    OP
       2019-05-19 17:40:18 +08:00
    @Vegetable
    @binux
    @Pzqqt
    @oblivious
    @lhx2008
    @owt5008137
    按这么考虑还真的是 10 分钟量的代码,是我当时考虑的太复杂了

    @Vegetable 你的代码缩进乱掉了,虽然我还是看懂了
    makdon
        22
    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
        23
    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
        24
    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
        25
    zgl263885  
       2019-05-19 20:47:02 +08:00 via iPhone
    滑动窗口算法,窗口宽度为一分钟,统计窗口内 ip 访问次数超过 100 次的 ip。
    MissThee
        26
    MissThee  
       2019-05-19 20:47:17 +08:00 via iPhone
    虽然不会 puthon,但是感觉用一门语言实现读取文件,计数,1 分钟执行一次的循环任务,应该不会很难吧😅
    Oz2011
        27
    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
        28
    Oz2011  
       2019-05-19 22:10:35 +08:00
    这个外部排序分割文件没关系啊,顺序处理就行了
    zgq3337
        29
    zgq3337  
       2019-05-20 08:36:58 +08:00 via Android
    用 Dict,以 IP 为 key,时间加入列表,每次对应 key 有变化,就对当前索引前 100 次作时间差计算,超过 1 分钟标记
    Pythoner666666
        30
    Pythoner666666  
       2019-05-20 09:06:26 +08:00
    python 不是有迭代器么,每次只读一行到内存中,这样就可以解决了吧
    crazypig14
        31
    crazypig14  
       2019-05-20 13:30:17 +08:00
    实际写代码虽然顺序处理为了并发还是得文件切割,切割处小心一点,得有 100 秒的重合
    luckymerlin
        32
    luckymerlin  
       2019-05-20 14:11:35 +08:00 via Android
    不是 sorted 的先 sort,然后 sliding window + hashmap
    lanshee
        33
    lanshee  
       2019-06-03 18:34:16 +08:00
    with open('filepath') as f:
    for line in f:
    # 假定起始时间为 00:00:00
    lanshee
        34
    lanshee  
       2019-06-03 18:34:34 +08:00
    @lanshee 完犊子.我还没写完.
    lanshee
        35
    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: 求大神指点.
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1689 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 16:49 · PVG 00:49 · LAX 08:49 · JFK 11:49
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.