先給出我的答案：

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)

還有一點就是有時候這兩個做法的結果不太相同, 會差一, 題主若有方法可以驗證一下正確性

我單單看我找出來的答案似乎沒錯, 但若有疏忽還請大家指正我, 謝謝！

也歡迎更多人討論這題．