Vergleich 2 Listen anhand der Timestamps

[boletus999]

Hallo liebe Forumsgemeinde,

ich beschäftige mich noch nicht allzulang mit Python und möchte mich eher als Anfänger bezeichnen.
Nun zu meiner Frage:
Ich habe mehrere Logdateien (jeweils mehrere 100 MB groß) mit einem Zeitstempel für jede Zeile

Datei 1 (Auszug):
12,2013-07-25 13:50:09,38.81,32.89,31.53,38.86,34.99,31.27,30.46,31.79,37.68,-51.28,
12,2013-07-25 14:00:09,38.37,31.83,31.18,38.08,31.39,30.24,29.57,29.72,37.08,-51.26,
12,2013-07-25 14:10:09,37.83,30.91,30.89,37.25,30.73,29.75,30.01,29.36,36.26,-51.29,
12,2013-07-25 14:20:09,37.52,30.34,30.55,36.69,30.66,29.44,30.32,29.1,35.66,-51.28,
12,2013-07-25 14:30:09,37.4,29.99,30.24,36.45,30.41,29.2,30.12,29.03,33.18,-51.26,
12,2013-07-25 14:40:09,37.17,30.05,30.2,36.12,30.15,29.09,29.96,28.95,31.01,-51.26,
....

Datei 2 (Auszug):
113,2013-07-25 14:25:06,4.459,3.03,.438,.941,78.8,59.97,8.37,-21.94,-5.19,-6.132,-8.14,-6.624,
113,2013-07-25 14:30:06,4.638,3.104,1.613,.214,-1.118,-2.372,8.4,-26.18,-6.254,-6.649,-6.649,
113,2013-07-25 14:35:06,5.046,3.495,1.963,.559,-.801,-2.087,8.4,-23.46,-9.48,-7.48,-7.2,-7.17,
113,2013-07-25 14:40:06,5.309,3.716,2.195,.741,-.633,-1.935,8.4,-19.2,-3.107,-5.743,-6.058,
113,2013-07-25 14:45:06,5.466,3.825,2.29,.821,-.55,-1.848,8.4,-18.93,-6.058,-6.649,-6.649,
113,2013-07-25 14:50:06,5.588,3.971,2.424,.961,-.445,-1.761,8.4,-24.04,-6.773,-6.773,-6.748,
....

Nun sollen beide Dateien miteinander verschnitten werden. Da der Zeitstempel nicht identisch ist, so muss nach der kleinsten Zeitabweichung gesucht werden. Anschließend sollen die Daten in Datei 2 um die in der Datei 1 gefundenen ehesten zeitlichen Übereinstimmung erweitert werden.

Die 1. und 2. Datei wird jeweils in 2 Listen gelesen

Code: Alles auswählen

FDR_data=[]
FDR_date=[]

S_date=[]
S_data=[]

FDR = open('FDR_test.dat',"r")
Simple = open('S_test.dat',"r")

csv_Sim = csv.reader(Simple)
for i in csv_Sim:
   S_date.append(i[1])
   S_data.append(i[2:])

csv_FDR = csv.reader(FDR)
for i in csv_FDR:
   FDR_date.append(i[1])
   FDR_data.append(i[2:])

Nun sollen die Daten einer jeden Zeile mit dem jeweils zeitlich passenden Inhalt der anderen Datei erweitert werden.
Mein stümperhafter Ansatz:

Code: Alles auswählen

time_format = "%Y-%m-%d %H:%M:%S"
delta=[]

for x, y in [(x,y) for x in xrange(len(FDR_date)) for y in xrange(len(S_date))]:
   delt1 = ((datetime.datetime.strptime(FDR_date[x], time_format) - datetime.datetime.strptime(S_date[y], time_format)))
   delt2 = ((datetime.datetime.strptime(S_date[x], time_format) - datetime.datetime.strptime(FDR_date[y], time_format)))
   delta.append(delt1.seconds + delt2.seconds)

   if delt1.seconds > -60 and delt1.seconds < 60:
      print "delt1", FDR_date[x], S_date[y], delt1.seconds
   elif delt2.seconds > -60 and delt2.seconds < 60:
      print "delt2", S_date[x], FDR_date[y], delt2.seconds

Liefert schon mal Ergebnisse:

Code: Alles auswählen

delt2 2013-07-25 14:10:09 2013-07-25 14:10:06 3
delt2 2013-07-25 14:20:09 2013-07-25 14:20:06 3
delt2 2013-07-25 14:30:09 2013-07-25 14:30:06 3
delt2 2013-07-25 14:40:09 2013-07-25 14:40:06 3
delt2 2013-07-25 14:50:09 2013-07-25 14:50:06 3
delt2 2013-07-25 15:00:09 2013-07-25 15:00:06 3
delt2 2013-07-25 15:10:09 2013-07-25 15:10:06 3
delt2 2013-07-26 07:20:09 2013-07-25 07:20:06 3

Aber durch mein Einschränkung des Delta von -60 bis 60 fliegen die Daten zwischen den vollen 10 min raus.
So müste ich das für jeden Durchlauf von 2 neuen Dateien immer wieder neu definieren. Das geht bestimm auch einfacher zu beschreiben.

Gibt es vielleicht eine einfachere Möglichkeit eine zeitliche "Annäherung" der Zeitstempel zu finden?

So was in diese Richtung :
Suche den kleinsten (absolut gesehenen) delta.seconds und merge die Daten zusammen. Füge mir eine Spalte hinzu in der das delta.seconds ausgegeben wird, um die Qualität der Übereinstimmung später beurteilen zu können.

Vielen lieben Dank bereits im Voraus
**boletus**

[BlackJack]

@boletus999: Also erst einmal würde ich das Aufteilen auf *zwei* Listen (pro Liste) sein lassen. Zeit und Daten gehören ja jeweils zusammen und sollten deshalb auch ein Element in einer Liste ausmachen.

Dann ist das Vergleich von jedem Datensatz der einen Datei mit jedem Datensatz der anderen *in beide Richtungen* doppelt so Aufwändig als es sein müsste. Bei grossen Mengen an Datensätzen ist der Aufwand sowieso sehr hoch und wenn man sich anschaut, dass ein Match eigentlich nur in Frage kommt, wenn beide Datensätze im gleichen 120 Sekunden Fenster liegen, wird wahrscheinlich sehr viel völlig umsonst verglichen was man durch diese Einschränkung schon vorher hätte aussortieren können.

Man könnte den Ansatz von Mergesort verwenden (ich gehe mal davon aus die Daten sind in beiden Listen zeitlich aufsteigend sortiert). Also man nimmt sich einen Datensatz aus der einen Menge und füllt dann eine Queue (`collections.deque`) mit Datensätzen aus der anderen Menge die in dem 120 Sekunden-Fenster liegen. Dann kann man schauen welcher davon am nächsten heran kommt und die dann verbinden. Dann schmeisst man alle Datensätze bis dahin aus der Queue, nimmt sich den nächsten Datensatz aus der ersten Menge und füllt wieder die Queue mit dem in Frage kommenden Zeitfenster.

Wahrscheinlich braucht man nicht einmal die Queue wenn man es geschickt anfängt.

[boletus999]

Das hört sich gut an!

Das mit den jeweils 2 Listen hatte ich nur gemacht, da ich die Zeit der Zeilen in einem anderen Codeschnipsel in einen Unix-timestamp umgewandelt hatte (zum rumspielen).

Du hast völlig recht eine Liste pro Datei ist ausreichend.

*in beide Richtungen*
Auch aus diesem Standpunkt habe ich das noch garnicht betrachtet. Da spare ich auf jeden Fall nochmal eine Menge Zeit. Vielen Dank!!
Derzeit habe ich nur einen Test-data Frame (30.000 Datensätze) an dem ich das herumprobiere, daher ist mir die später lange Laufzeit des Scripts auch noch nicht aufgefallen.
Hier muss ich also noch ein bisschen aussortieren.

Die Daten sind Chronologisch geordnet. Ich werde mir daher gleich mal deinen Vorschlag von Mergesort ansehen.


Danke für die richtigen Denkanstupser und Vorschläge

[boletus999]

Wie bereit gesagt bin ich Python-Anfänger.
Ich habe in meinem oben erwähnten Code 2 Fehler entdeckt, die hier noch schnell mal korrigieren möchte:

Code: Alles auswählen

time_format = "%Y-%m-%d %H:%M:%S"
delta=[]

for x, y in [(x,y) for x in xrange(len(FDR_date)) for y in xrange(len(S_date))]:
   delt1 = ((datetime.datetime.strptime(FDR_date[x], time_format) - datetime.datetime.strptime(S_date[y], time_format)))
   delt2 = ((datetime.datetime.strptime(S_date[x], time_format) - datetime.datetime.strptime(FDR_date[y], time_format)))
   delta.append(delt1.seconds + delt2.seconds)

   if delt1.seconds > -60 and delt1.seconds < 60:
      print "delt1", FDR_date[x], S_date[y], delt1.seconds
   elif delt2.seconds > -60 and delt2.seconds < 60:
      print "delt2", S_date[x], FDR_date[y], delt2.seconds

muss bei der If und elif so lauten:

Code: Alles auswählen

if delt1.seconds < 120 and delt1.days == 0:
...
elif delt2.seconds < 120 and delt2.days == 0:

weil:
.seconds immer als positive Zahl angegeben wird (soweit wie ich das verstanden habe)

und der Unterschied der Tage also .days nicht in den sekunden mit enthalten ist. Somit zusätzlich das "and" in der If und elif.


Beim Thema Mergesort bin ich noch nicht weiter gekommen. Da muss ich mich noch etwas tiefer "Eindenken". Doch was ich bisher darüber erfahren habe, gefällt mir recht gut.

[snafu]

Zum Thema Mergesort: Sofern man die Phase des Aufteilens vorwegnimmt, landet man bei einer Konstellation, wo alle Elemente deiner Liste (oder was auch immer du da hast) einzeln betrachtet werden. Nun gilt es, Pärchen zu bilden. Dies bedeutet, dass du zunächst Zweier-Pärchen anlegst, sodass das erste Element gemäß einer wie auch immer gearteten Sortiervorschrift (z.B. alphabetisch bei Zeichenketten oder numerisch bei Zahlen) immer kleiner ist als das zweite Element.

Wenn du dann alle Pärchen beisammen hast, musst du die Zweier-Pärchen zu Vierer-Pärchen machen. Hier setzt du eine Art Zeiger auf das jeweils erste Element der beiden Pärchen und vergleichst das eine Element unter dem ersten Zeiger mit dem Element unter dem anderen Zeiger. Wieder "gewinnt" das kleinere Element und rutscht entsprechend ins Vierer-Pärchen rein. Der Zeiger verschiebt sich dadurch auf einer der beiden Seiten zum nächsten Element (da ja ein Element rausgeschmissen wurde), während der Zeiger im anderen Pärchen an seiner Position bleibt. Jetzt werden wieder die aktuellen Elemente unter der jeweiligen Zeigerposition verglichen, usw.

Die Besonderheit an Mergesort ist, dass Vergleiche eingespart werden, sobald eins der beiden zu mergenden Pärchen keine Elemente mehr übrig hat (also wenn alle Elemente daraus ins nächste Pärchen verschoben wurden). Dann nämlich wird einfach der Rest des anderen Pärchens an das Ende des Pärchens aus der höheren Stufe verschoben, weil klar ist, dass die Reihenfolge in der nächsthöheren Ebene dann so oder so richtig sein wird. Je nachdem, wie aufwändig ein solcher Vergleich ist, kann das bei sehr großen Datensätzen durchaus zeitlich ins Gewicht fallen.

Kannste ja mal in Programmcode ausformulieren. Für die Ebene mit den einzelnen Elementen brauchst du übrigens keine Sonderbehandlung (falls das bei der Beschreibung so rüberkam). Man nimmt dann einfach nur einen Zeiger für ein einzelnes Element und wenn das kleinere "hochgeschoben" wurde, dann ist das andere halt das übrig gebliebene Element, was ja wie gesagt automatisch hinten ans neue Pärchen angehangen wird.

Ich hoffe, du bist halbwegs mitgekommen. Ansonsten zeichne dir den Ablauf mal auf oder suche nach gängigen Grafiken zum Thema Mergesort.

[BlackJack]

@snafu: Du beschreibst hier ein ganz allgemeines Mergesort was von unsortierten Daten ausgeht (bilden von 2er-, 4er-Päckchen, usw.) wir haben doch aber schon zwei grosse „Pakete” die komplett sortiert sind. Die beiden Datenmengen liegen ja schon sortiert vor.

[snafu]

@BlackJack: Na, der OP hat sich ja offenbar zum Thema Mergesort ein paar Infos angelesen und ich wollte diese nochmal zusammenfassen, damit er versteht, worum es bei Mergesort grundsätzlich geht. Ich hatte es nur irgendwie versäumt, den Bogen bezüglich der Übertragung auf den konkreten Anwendungsfall zu schlagen in meiner Schreibwut. Das stimmt wohl.

[boletus999]

Da bin ich mal wieder.
Die Umsetung von Mergesort ist mir nicht gelungen
Ich habe aber an der Preformance gefeilt und aus den 2 Dateien die durchsucht werden sollen sind 3 geworden.
1. Datei aller 1sec ein Zeitstempel
2. Datei aller 5 min
3. Datei aller 10 min

D.h. mein erster Lösungsansatz von ganz oben würde jetz eine for-Schleife n^3 sein (das kann dauern).
Das ist also Quatsch.

Somit habe ich mir den Vorschlag von BlackJack angenommen und baue jetzt Zeitfenster in einer queue-Liste zusammen.
Ich beginne von Hinten mit der niedrigsten Auflösung (10min Datei)

Diese werden in der 1.Datei gesucht, wenn gefunden --> baue ein Zeitfenster drumrum.
Merge alle Funde im Zeitfenster zusammen, schreibe sie in eine Liste und lösche die Einträge aus der 1. Datei und alles was chronologisch davor kommt.
Lösche queue und nimm die nächsten 10 min.

Somit wird der Skriptdurchlauf sukzessive immer schneller.

Danach analog zur 10min-Datei, die 5min-Datei. Wobei hier die neu entstandene Liste verwendet wird, da ich ja nur Vergleiche haben möchte bei den alle 3 Dateienschnipsel zusammenpassen.

Ich arbeite beim Mergen mit den Listen.index(en). Dabei hat sich herausgestellt, dass wenn ich für jede Datei zwei Listen anlege (ein mit dem Timestamp (1), die andere mit allem (2)), läuft das Skript wesentlich schneller. Weil wenn in den Listen etwas gesucht wird die Timestampliste wesentlich kleiner ist als die alles in einer Liste.
Ich suche also in der (1) und hole die Daten aus der (2)

Liebe Grüße und schönes WE
**boletus**

Beim Testlauf verwendete ich:
1. Datei mit 20 Spalten und 73.000 Zeilen
2. Datei mit 64 Spalten und 300 Zeilen
3. Datei mit 130 Spalten und 150 Zeilen
Dauer: 5min 40sec bei 2Ghz

[BlackJack]

@boletus999: Ähm, mein Vorschlag war der Mergesort-*Ansatz* mit einer Queue mit einem Zeitfenster. Dabei wird jede Liste nur einmal linear durchlaufen. Wenn die Abstände der Zeitstempel *so* gross sind, also man sagen kann, das ein Datensatz aus der 5 Minuten-Datei ca. alle 300 Einträge aus der 1 Sekunden-Datei eingefügt werden muss, dann sollte man sogar mit einem ganz kleinen Fenster auskommen, nämlich in dem man sich immer nur einen zusätzlichen vergangenen Wert von der 1-Sekunden-Datei merkt. Dann gibt man Werte von der 1 Sekunden-Datei solange unverändert weiter wie der Zeitabstand zum aktuellen 5-Minuten-Wert kleiner wird. Sowie der Abstand grösser wird, weiss man das der letzte 1-Sekunden-Wert der gesuchte ist zu dem man mergen will. Das gleiche macht man dann mit dem Ergebnis dieses Mergens mit der dritten Datei. Man muss also nur eine Funktion schreiben die zwei Datenströme merged, und wendet die zweimal an. Wenn man eine Generatorfunktion schreibt, brauchen die Daten noch nicht einmal komplett im Speicher vorliegen, weder die Eingabedaten noch die Ausgabedaten.

[boletus999]

@BlackJack

alle 300 Einträge aus der 1 Sekunden-Datei eingefügt werden muss...nur einen zusätzlichen vergangenen Wert von der 1-Sekunden-Datei merkt

Das ist auch eine gute Idee!

...Sowie der Abstand grösser wird, weiss man das der letzte 1-Sekunden-Wert...

Nein, so sollte es nicht werden.

-150sec < 5min > + 150sec | -300sec < 10 min > +300sec
Ich möchte, dass an jedem 1 Sekundenwert der naheliegenste 5min und 10 min Wert angehangen wird.
Aber nur wenn der Sekundenwert (Datei 1) +-150 Sekunden vom 5min Wert (Datei 2) und +-300 Sekunden vom 10min Wert (Datei 3) entfernt ist.
D.h. für 600 aufeinandefolgende Sekunden der 1.Datei werden 2 aus der 2.Datei und 1 aus der 3.Datei angehangen.
So:
[Datei 1], [Datei 3], [Datei 2]

Code: Alles auswählen

...
(['2013-07-20 15:22:33', ...Daten...], ['2013-07-20 15:20:09', ...Daten... '']),['2013-07-20 15:20:06', ...Daten... ''],
(['2013-07-20 15:22:34', ...Daten...], ['2013-07-20 15:20:09', ...Daten... '']),['2013-07-20 15:20:06', ...Daten... ''],
(['2013-07-20 15:22:35', ...Daten...], ['2013-07-20 15:20:09', ...Daten... '']),['2013-07-20 15:20:06', ...Daten... ''],
(['2013-07-20 15:22:36', ...Daten...], ['2013-07-20 15:20:09', ...Daten... '']),['2013-07-20 15:25:06', ...Daten... ''],
(['2013-07-20 15:22:37', ...Daten...], ['2013-07-20 15:20:09', ...Daten... '']),['2013-07-20 15:25:06', ...Daten... ''],
...

Deshalb fange ich von Hinten an (Datei 3). Weil hier weniger Zeilen gefunden werden müssen. Erst wenn das der Fall ist, wird im zweiten Schritt geschaut ob es auch einen Treffer in Datei 2 gibt. Wenn das das auch zutrifft --> wird das Zeitfenster aus dem queue darüber gelegt und die 600 Zeilen der 1.Datei mit den dazugehörigen Werten aus 2. u 3. Datei erweitert.

Derzeit läuft das Ganze noch in 2 hintereinander folgenden for-Schleifen, da ich mich da besser zurecht finde. Dei können aber später auch vereint werden.

**boletus**

[BlackJack]

@boletus999: Na dann muss man halt noch den Abstand auf den Grenzwert prüfen, aber ansonsten müsste das doch funktionieren wenn man, sowie der Abstand wieder grösser wird, den letzten Satz als Kandidaten nimmt, denn der war am nächsten dran.