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．

這是一個 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 測試測資數量 1000, 10000, 100000

$ 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.

1. 若維持 timeframe 大小不變, 兩者的時間對測資數量都呈現線性成長

2. 可是當 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，效率提升不少，虽然数量级还在秒，但这仅仅是一天的一个文件。同时帮我发现效率问题更严重的其实是在函数内部对满足要求日志行的提取上，感谢大家的回答与参与，谢谢！