Finding Auftreten Muster in einem Zeitstempel-Intervall

-2

ein Array von Zeitstempel (Epochenzeit) gegeben, wobei jeder Zeitstempel der Zeit darstellt, wenn ein EreignisFinding Auftreten Muster in einem Zeitstempel-Intervall

timestamps = [1467267654, 1467267657, 1467267660, ... 146726821]

aufgetreten I für ein Intervall von 30 Sekunden suchen muss, wo die Anzahl der Vorkommnisse höher als 5

sind also, wenn es mindestens 5 Elemente zwischen i und j und Zeitstempel sind [j] -timestamps [i] < = 30 Sekunden, dann true zurück.

Was ist der richtige Algorithmus hier zu verwenden? Denken Sie daran, ich benutze Python, vielleicht ist es bereits unter numpy implementiert. Irgendwelche Vorschläge sind hilfreich.

Quelle

2016-06-30 ctotolin

sortieren Ihre Daten? – 01axel01christian

Ja, das Array ist sortiert – ctotolin

Bitte geben Sie eindeutig an, was Sie mit "mindestens 5 Elemente zwischen" meinen. Wie viel muss "j-i" sein? –

Da die Daten sortiert sind, genügt ein Durchgang. Iteration durch das Array auf die folgende Weise:

den aktuellen Index i erinnern, lassen Sie uns diesen Index nennen start
Erhöhung i bis entweder i = start + 4 oder a[i] > a[start] + 30: im ersten Fall Rückkehr true, im zweiten Fall Update start = start + 1 und fortfahren

Gesamtkomplexität: O(n).

Bonus

wenn Sie wollen alle diese Intervalle zurück, dann in Fall, wenn Sie ein entsprechendes Intervall gefunden, erinnern seine Grenzen und gehen
, wenn Sie das längste Intervall zurückkehren mögen, dann hör nicht auf, wenn du i = start + 4 so findest, dass a[i] < a[start] + 30, aber das Intervall weiter verlängert. Wenn Sie schließlich Index erfüllen j so dass a[j] > a[start] + 30 die Grenzen dieses zur Zeit längsten Intervalls erinnern, aktualisiert start = start + 1 und gehe

Quelle

2016-06-30 07:00:24

Wenn Sie versuchen, die Zwischenelemente zwischen Start und Start + 5 zu überspringen, reicht es aus, die beiden Extreme zu vergleichen. Im schlimmsten Fall leisten Sie 5 Mal die Arbeit, die Sie benötigen. –

@ YvesDaoust Zustimmen. Ich war mir dessen bewusst, während ich eine Antwort schrieb, aber für eine kleine Intervallgröße (in diesem Fall 5) macht es asymptotisch keinen großen Unterschied (und es war besser als die andere vorgeschlagene Lösung, die O (nlogn) war). Ihre Lösung ist definitiv effizienter. –

alle Paare von Zeitstempel 4 Indizes auseinander Versuchen Sie, bis Sie einen finden, der von weniger als 30 Sekunden abweicht.

for i in range(len(timestamps) - 4): 
    if timestamp[i + 4] - timestamp[i] <= 30: 
     return true 
return false

Nach der Problembeschreibung muss die Intervallposition nicht gemeldet werden. Die Schleife nimmt genau I+1 Vergleiche, wobei I der Index des ersten übereinstimmenden Intervalls ist (N - 4, wenn es keine gibt).

bester Fall 1 Vergleich, worst case N-4, erwartete Fall p(E(I)+1)+(1-p)(N-4) wo E(I) die Erwartung I und p ist die Wahrscheinlichkeit, dass es ein geeignetes Intervall vorhanden ist.

In einer moderneren und vor allem ineffiziente Art (timestamp-t verkürzt),

reduce(lambda a, b: a or b, [t[i + 4] - t[i] <= 30 for i in range(len(t) - 4)])

Quelle

2016-06-30 07:27:28

Finding Auftreten Muster in einem Zeitstempel-Intervall

Antwort

Verwandte Themen