求一个关于日期时间间隔计算相关的算法，具体问题如下：
当前有一个比较大（上万个）日期时间的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数量庞大，同时还要涉及时间运算，算法难以达到要求，特来请教！
没有数据，不好 profile，先给出一版，看看别人是不是有更好的处理。
微博登录
QQ登录
微信扫码登录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)]
先給出我的答案：
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.若維持 timeframe 大小不變, 兩者的時間對測資數量都呈現線性成長
可是當 timeframe 變成兩倍時, 第二種做法的時間也會多一倍
這表示 @citaret 大的方法複雜度應該是 O(n * timeframe)
還有一點就是有時候這兩個做法的結果不太相同, 會差一, 題主若有方法可以驗證一下正確性
我單單看我找出來的答案似乎沒錯, 但若有疏忽還請大家指正我, 謝謝！
也歡迎更多人討論這題．
我回答過的問題: Python-QA
鄂公网安备 42090202000075号 - 鄂ICP备2021002952号-1