datetime - 关于一个日期时间间隔计算相关的算法(Python)

Question

求一个关于日期时间间隔计算相关的算法，具体问题如下：
当前有一个比较大（上万个）日期时间的list（时间递增但无规律），假设 dt=[
'2015-01-02 10:21:02',
'2015-01-02 10:21:02'
'2015-01-02 10:21:03'
'2015-01-02 10:21:04'
'2015-01-02 10:21:06'
'2015-01-02 10:21:10'
'2015-01-02 10:21:11'
'2015-01-02 10:21:13'
'2015-01-02 10:22:00'
'2015-01-02 10:22:12'
... ...
]
给定一个时间间隔timeframe（假设4s），现在问题是：求在给定连续时间间隔内，list中最多项数目。

最简单的方法是依次对于list中每个项x，向后查找直至大于timeframe+x的项并统计个数。但由于这个list数量庞大，同时还要涉及时间运算，算法难以达到要求，特来请教！

Answer 1

先给出我的答案：

def findmax(timestrs, timeframe):
    fmt = "%Y-%m-%d %H:%M:%S"
    times = [datetime.strptime(timestr, fmt) for timestr in timestrs]
    frame = timedelta(seconds=timeframe)
    window = dict(bidx=0, eidx=0)
    maxwindow = dict(bidx=0, eidx=0)

    # search
    for idx, time in enumerate(times):
        if time-times[window['bidx']] > frame:
            count = window['eidx'] - window['bidx'] + 1
            if count > maxwindow['eidx'] - maxwindow['bidx']:
                maxwindow = dict(window)
        while time-times[window['bidx']] > frame:
            window['bidx'] += 1
        window['eidx'] = idx
    else:
        count = window['eidx'] - window['bidx'] + 1
        if count > maxwindow['eidx'] - maxwindow['bidx']:
            maxwindow = dict(window)

    # output results
    maxcount = maxwindow['eidx'] - maxwindow['bidx'] + 1
    print('max count:{} of winodw from {}:{} to {}:{}'.format(
        maxcount, maxwindow['bidx'], timestrs[maxwindow['bidx']],
        maxwindow['eidx'], timestrs[maxwindow['eidx']]))

上述的 code 要记得 import datetime 和 timedelta． datetime 和 timedelta．

這是一個 O(n) 的做法, n 為 timestrs 的數量．

code 有點醜, 晚一點再修, 不過為了比較速度跟正確性, 我做了一些實驗, 以下是我用來做實驗完整的 code:

from datetime import datetime, timedelta
import collections
import random
import sys


def simpletimer(func):
    """ a simple decorator to time a function"""
    import time
    def modified_func(*args, **kwargs):
        btime = time.time()
        result = func(*args, **kwargs)
        print('[time]', time.time()-btime, 'sec.')
        return result
    return modified_func


def gentimestrs(count, delta):
    """ generate time strings for input data"""
    timestrs = []
    time = datetime(2015, 1, 2)
    for i in range(count):
        time = time + timedelta(seconds=random.randrange(delta))
        timestrs.append(str(time))
    return timestrs

@simpletimer
def findmax(timestrs, timeframe):

    fmt = "%Y-%m-%d %H:%M:%S"
    times = [datetime.strptime(timestr, fmt) for timestr in timestrs]
    frame = timedelta(seconds=timeframe)

    window = dict(bidx=0, eidx=0)
    maxwindow = dict(bidx=0, eidx=0)

    for idx, time in enumerate(times):
        if time-times[window['bidx']] > frame:
            count = window['eidx'] - window['bidx'] + 1
            if count > maxwindow['eidx'] - maxwindow['bidx']:
                maxwindow = dict(window)
        while time-times[window['bidx']] > frame:
            window['bidx'] += 1
        window['eidx'] = idx
    else:
        count = window['eidx'] - window['bidx'] + 1
        if count > maxwindow['eidx'] - maxwindow['bidx']:
            maxwindow = dict(window)

    maxcount = maxwindow['eidx'] - maxwindow['bidx'] + 1
    print('max count:{} of winodw from {}:{} to {}:{}'.format(
        maxcount, maxwindow['bidx'], timestrs[maxwindow['bidx']],
        maxwindow['eidx'], timestrs[maxwindow['eidx']]))


@simpletimer
def findmax2(timestrs, timeframe):
    fmt = "%Y-%m-%d %H:%M:%S"
    ys = ((datetime.strptime(x, fmt) + timedelta(seconds=-i)).strftime(fmt) for x in timestrs for i in range(timeframe))
    print(collections.Counter(ys).most_common(1))


if __name__ == '__main__':

    count = int(sys.argv[1])
    delta = int(sys.argv[2])
    frame = int(sys.argv[3])

    timestrs = gentimestrs(count, delta)
    with open('timestrs', 'w') as writer:
        for timestr in timestrs:
            print(timestr, file=writer)

    funclst = [findmax, findmax2]

    for func in funclst:
        func(timestrs, frame)

包含了

• 一個很陽春用來計時的 decorator: simpletimer

  • 他會裝飾 func, 印出執行所花的時間

• 一個產生隨機測資的 function: gentimestrs

  • 他會產生 count 筆 time strings 測資, 且各資料的時間間隔是小於等於 delta 的隨機整數

• 接下來的 findmax 和 findmax2 分別是我的做法跟 @citaret 的做法 (有興趣的大家可以自行仿照介面加入自己的 function, 題主也可以把自己原先的做法拿來比比看), 並且用 simpletimer 計時．

• 測試的時候先產生測資, 再分別執行 funclst 中要比較的 funcion

執行的範例如下:

                           timeframe
                           ＿
$ python3 test.py 10000 30 6
                  ^^^^^ ^^ 
                  測資數 隨機最大時間間隔

這邊列出一些結果：

用 timeframe==5 測試測資數量 1000, 10000, 100000

$ python3 td.py 1000 30 5
max count:4 of winodw from 798:2015-01-02 03:25:56 to 801:2015-01-02 03:26:01
[time] 0.02829718589782715 sec.
[('2015-01-02 03:25:56', 3)]
[time] 0.15825390815734863 sec.

$ python3 td.py 10000 30 5
max count:5 of winodw from 1624:2015-01-02 06:37:32 to 1628:2015-01-02 06:37:37
[time] 0.19979143142700195 sec.
[('2015-01-02 12:17:22', 4)]
[time] 1.6265528202056885 sec.

$ python3 td.py 100000 30 5
max count:6 of winodw from 91688:2015-01-17 09:41:33 to 91693:2015-01-17 09:41:38
[time] 1.8956780433654785 sec.
[('2015-01-15 01:36:41', 5)]
[time] 15.950862407684326 sec.

用 timeframe==10

这是一个

O(n)
1. 的做法, n 为 timestrs 的数量．
   code 有点丑, 晚一点再修, 不过为了比较速度跟正确性, 我做了一些实验, 以下是我用来做实验完整的 code:

$ python3 td.py 1000 30 10
max count:5 of winodw from 910:2015-01-02 03:36:08 to 914:2015-01-02 03:36:17
[time] 0.02788376808166504 sec.
[('2015-01-02 03:24:06', 5)]
[time] 0.3295907974243164 sec.

$ python3 td.py 10000 30 10
max count:6 of winodw from 5304:2015-01-02 21:45:41 to 5309:2015-01-02 21:45:47
[time] 0.20185112953186035 sec.
[('2015-01-02 21:45:38', 6)]
[time] 3.2009713649749756 sec.

$ python3 td.py 100000 30 10
max count:7 of winodw from 16224:2015-01-04 17:16:17 to 16230:2015-01-04 17:16:23
[time] 1.8946728706359863 sec.
[('2015-01-04 17:16:17', 7)]
[time] 33.85069417953491 sec.

2. 包含了
一个很阳春用来计时的 decorator: simpletimer

他会装饰 func, 印出执行所花的时间

一个产生随机测资的 function: gentimestrs

他会产生count 笔time strings 测资, 且各资料的时间间隔是小于等于delta 的随机整数#🎜 🎜#

---

接下来的findmax 和findmax2 分别是我的做法跟@citaret 的做法(有兴趣的大家可以自行仿照介面加入自己的function, 题主也可以把自己原先的做法拿来比比看), 并且用simpletimer 计时．

#🎜🎜# #🎜🎜##🎜🎜#测试的时候先产生测资, 再分别执行 funclst 中要比较的 funcion#🎜🎜##🎜🎜# #🎜🎜#执行的范例如下:#🎜🎜# rrreee #🎜🎜#这边列出一些结果：#🎜🎜# #🎜🎜#用 timeframe==5 测试测资数量 1000, 10000, 100000#🎜🎜# rrreee #🎜🎜#用 timeframe==10 测试测资数量 1000, 10000, 100000#🎜🎜# rrreee #🎜🎜# #🎜🎜##🎜🎜#若维持 timeframe 大小不变, 两者的时间对测资数量都呈现线性成长#🎜🎜##🎜🎜# #🎜🎜##🎜🎜#可是当 timeframe 变成两倍时, 第二种做法的时间也会多一倍#🎜🎜##🎜🎜# #🎜🎜# #🎜🎜#这表示 @citaret 大的方法复杂度应该是 #🎜🎜#O(n * timeframe)#🎜🎜##🎜🎜# #🎜🎜#还有一点就是有时候这两个做法的结果不太相同, 会差一, 题主若有方法可以验证一下正确性#🎜🎜# #🎜🎜#我单单看我找出来的答案似乎没错, 但若有疏忽还请大家指正我, 谢谢！ #🎜🎜# #🎜🎜#也欢迎更多人讨论这题． #🎜🎜# #🎜🎜# #🎜🎜##🎜🎜#我回答过的问题#🎜🎜#: Python-QA#🎜🎜#

Answer 2

没有数据，不好 profile，先给出一版，看看别人是不是有更好的处理。

xs = [
'2015-01-02 10:21:02',
'2015-01-02 10:21:02',
'2015-01-02 10:21:03',
'2015-01-02 10:21:04',
'2015-01-02 10:21:06',
'2015-01-02 10:21:10',
'2015-01-02 10:21:11',
'2015-01-02 10:21:13',
'2015-01-02 10:22:00',
'2015-01-02 10:22:12' ]

from datetime import datetime, timedelta
import collections

delta = 5
fmt = "%Y-%m-%d %H:%M:%S"
ys = ((datetime.strptime(x, fmt) + timedelta(seconds=-i)).strftime(fmt) for x in xs for i in range(delta))
print collections.Counter(ys).most_common(1)
# output: [('2015-01-02 10:21:02', 5)]

Answer 3

@dokelung 使用citaret算法测试了下，对于共27505个元素的list（从有63万行单个日志文件中提取，多个源ip汇总）耗时3.8842415850296845s，我原来时耗时16.544873371035163s，效率提升不少，虽然数量级还在秒，但这仅仅是一天的一个文件。同时帮我发现效率问题更严重的其实是在函数内部对满足要求日志行的提取上，感谢大家的回答与参与，谢谢！