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

Beri saya jawapan saya dahulu:

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']]))

Ingat untuk mengimport datetime dan timedelta untuk kod di atas.

Ini ialah pendekatan O(n), n ialah bilangan timestrs.

Kod itu agak hodoh, saya akan membetulkannya kemudian, tetapi untuk membandingkan kelajuan dan ketepatan, saya telah melakukan beberapa percubaan Berikut ialah kod lengkap yang saya gunakan untuk melakukan eksperimen:

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)

Mengandungi

• Penghias yang sangat keren untuk pemasaan: simpletimer

  • Dia akan menghias func, mencetak masa yang diambil untuk melaksanakan

• Fungsi yang menjana keputusan ujian rawak: gentimestrs

  • Ia akan menjana count data ujian rentetan masa dan selang masa setiap data ialah integer rawak kurang daripada atau sama dengan delta

• Berikut findmax dan findmax2 masing-masing adalah pendekatan saya dan pendekatan @citaret (jika anda berminat, anda boleh meniru antara muka dan menambah fungsi anda sendiri, dan penyoal juga boleh menggunakan pendekatan asalnya) Mari bandingkan), dan gunakan simpletimer mengikut masa.

• Apabila menguji, mula-mula jana aset ujian, dan kemudian laksanakan fungsi untuk dibandingkan dalam funclst

Contoh pelaksanaan adalah seperti berikut:

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

Berikut ialah beberapa keputusan:

Gunakan timeframe==5 untuk menguji jumlah dana 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.

Gunakan timeframe==10 untuk menguji jumlah dana 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. Jika saiz jangka masa dikekalkan tidak berubah, kedua-dua masa akan menunjukkan pertumbuhan linear dalam bilangan dana ujian

2. Tetapi apabila jangka masa berganda, kaedah kedua juga akan mengambil masa dua kali lebih lama

Ini bermakna kerumitan kaedah maksimum @citaret hendaklah O(n * jangka masa)

Perkara lain ialah kadang-kadang hasil kedua-dua kaedah ini tidak sama, akan ada perbezaan Jika penyoal mempunyai kaedah, dia boleh mengesahkan kebenaran

Jawapan yang saya dapati nampaknya betul, tetapi sila betulkan saya jika saya ada membuat sebarang kesilapan. Terima kasih!

Kami juga mengalu-alukan lebih ramai orang untuk membincangkan isu ini.

---

Soalan yang saya jawab: Python-QA

Answer 2

Tiada data dan tiada profil yang baik Mari berikan versi dahulu untuk melihat sama ada orang lain mempunyai penyelesaian yang lebih baik.

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 mengujinya menggunakan algoritma citaret Untuk senarai dengan jumlah 27505 elemen (diekstrak daripada fail log tunggal dengan 630,000 baris dan diagregatkan daripada berbilang IP sumber), ia mengambil masa 3.8842415850296845s . Pada masa yang sama, ia membantu saya mendapati bahawa masalah kecekapan yang lebih serius sebenarnya adalah pengekstrakan garis log yang memenuhi keperluan dalam fungsi Terima kasih atas jawapan dan penyertaan anda, terima kasih!