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

Donnez-moi d'abord ma réponse :

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

N'oubliez pas d'importer datetime et timedelta pour le code ci-dessus.

Il s'agit d'une approche O(n), n est le nombre de timestrs.

Le code est un peu moche, je le corrigerai plus tard, mais afin de comparer la vitesse et l'exactitude, j'ai fait quelques expériences Voici le code complet que j'ai utilisé pour faire les expériences :

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)

Contient

• Un décorateur très cool pour le timing : simpletimer

  • Il décorera func, en imprimant le temps qu'il a fallu pour exécuter

• Une fonction qui génère des résultats de tests aléatoires : gentimestrs

  • Il générera count données de test de chaînes de temps, et l'intervalle de temps de chaque donnée est un entier aléatoire inférieur ou égal à delta

• Les findmax et findmax2 suivants sont respectivement mon approche et celle de @citaret (si vous êtes intéressé, vous pouvez imiter l'interface et ajouter vos propres fonctions, et le questionneur peut également utiliser son approche originale) Comparons) et utilisons simpletimer pour chronométrer.

• Lors des tests, générez d'abord les actifs de test, puis exécutez les fonctions à comparer dans funclst

L'exemple d'exécution est le suivant :

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

Voici quelques résultats :

Utilisez timeframe==5 pour tester le montant des fonds 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.

Utilisez timeframe==10 pour tester le montant des fonds 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. Si la durée de la période reste inchangée, les deux périodes afficheront une croissance linéaire du nombre de fonds de test

2. Mais lorsque le délai double, la deuxième méthode prendra deux fois plus de temps

Cela signifie que la complexité maximale de la méthode de @citaret doit être O(n * timeframe)

Un autre point est que parfois les résultats de ces deux méthodes ne sont pas les mêmes, il y aura une différence si le questionneur a une méthode, il peut en vérifier l'exactitude

.

La réponse que j'ai trouvée semble être correcte, mais veuillez me corriger si j'ai commis des erreurs. Merci !

Davantage de personnes sont invitées à discuter de cette question.

---

Questions auxquelles j'ai répondu : Python-QA

Answer 2

Il n'y a pas de données et pas de bon profil. Donnons d'abord une version pour voir si d'autres ont de meilleures solutions.

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 l'a testé en utilisant l'algorithme citaret. Pour une liste avec un total de 27 505 éléments (extraits d'un seul fichier journal de 630 000 lignes et agrégés à partir de plusieurs adresses IP sources), cela a pris 3,8842415850296845s. Mon temps initial a pris 16,544873371035163s. . L'efficacité s'est beaucoup améliorée. Bien que l'ordre de grandeur soit encore de quelques secondes, il ne s'agit que d'un fichier par jour. En même temps, cela m'a aidé à découvrir que le problème d'efficacité le plus grave est en fait l'extraction des lignes de journaux qui répondent aux exigences de la fonction. Merci à tous pour vos réponses et votre participation, merci !