Effizientes sortieren von Listen

[Jenson]

Guten Morgen Zusammen,

ich sitze jetzt schon etwas länger an folgendem Problem, das ich euch hier reduziert vorstellen möchte. Ich bekomme Messdaten mit einem Timestamp. Die sehen folgendermaßen aus (sind in Wirklichkeit sehr viel größer, das / t steht für Tab):

Datei1:

01.01.2018 11:11:11 /t 5
01.01.2018 11:11:11 /t 5
01.01.2018 11:11:11 /t 5
01.01.2018 11:11:12 /t 5
01.01.2018 11:11:12 /t 5
01.01.2018 11:11:12 /t 5
01.01.2018 11:11:13 /t 5
...

Datei2:
01.01.2018 11:11:12 /t 45
01.01.2018 11:11:13 /t 65
...

ich lese das ganze mittels Numpy ein und möchte nur die Werte betrachten die einen übereinstimmenden Zeitstempel besitzen und davon auch nur den Ersten.

Code: Alles auswählen

import numpy

Flanke_Zeit = numpy.genfromtxt("Datei2.txt", usecols=0, delimiter="\t", dtype=str)

Temp_Zeit = numpy.genfromtxt("Datei1.txt", usecols=0, delimiter="\t", dtype=str)

Temp = numpy.genfromtxt("Datei1.txt", usecols=1, delimiter="\t", dtype=str)

mixed = numpy.column_stack((Temp_Zeit,Temp))

zeit_sync = []

for tempzeit in range(0,len(Temp)):
    for FLZ in range(0,len(Flanke_Zeit)):
        if mixed[tempzeit][0] == Flanke_Zeit[FLZ]:
            eintrag = [mixed[tempzeit]]
            zeit_sync.append(eintrag)
            break

wie ihr wahrscheinlich schon erkannt habt, dann wird die For-Schleife mit steigender Anzahl der Einträge sehr lange dauern. Dies ist mein Problem.
Ich habe folgendes schon versucht, doch leider nicht umsetzen können.
- Da die Zeitstempel cronologisch sind, wollte ich immer nur den ersten von Datei2 vergleichen --> funktioniert aber liefert nur ungefährt 0.1 der Werte zurück.
- Löschen aus Np.arrays geht ja leider nicht und immer ein neuen eingabe array habe ich nicht hinbekommen.

Das wirklich schlimme an der Sache ist nun, dass ein Kollege dieses Problem mit "Lua" in 30 Sekunden Laufzeit hinbekommt, wo mein Skript 30 Minuten rechnet. Was mache ich falsch?

Bin für alle Vorschläge offen:-)

[MagBen]

Ich würde die beiden Arrays an numpy.searchsorted übergeben
und dann die Elemente bei den zurückgegebenen Indizes vergleichen.

[Sirius3]

@Jenson: warum liest Du die Datei1 zweimal ein um dann jeweils nur eine Spalte zu benutzen und diese dann auch noch nachträglich zusammenpappen?

Du löst ein O(N)-Problem mit einem O(n²)-Algorithmus. Also kein Wunder, dass das lange dauert. Deine Logik ist auch falschherum. Du suchst ja zu jedem Flankenzeitpunkt einen Temp_Zeitpunkt und nicht umgekehrt.

Code: Alles auswählen

import numpy
from itertools import dropwhile

flanke_zeit = numpy.genfromtxt("Datei2.txt", usecols=0, delimiter="\t", dtype=str)
temp_zeit = numpy.genfromtxt("Datei1.txt", usecols=[0, 1], delimiter="\t", dtype=str)

temp_zeit_iter = iter(temp_zeit)
zeit_sync = [
	next(dropwhile(lambda x: x[0] != zeit, temp_zeit_iter))
	for zeit in flanke_zeit
]

die Lösung benutzt jetzt eigentlich kein numpy, so dass Du auch einfach mit csv arbeiten könntest.

@MagBen: das Problem mit searchsorted ist, dass die Zeiten nicht lexikalisch sortiert sind.

[Sirius3]

Wenn es Dir nur darum geht, doppelte Einträge loszuwerden, dann sieht das so aus:

Code: Alles auswählen

temp_zeit = numpy.vstack([[temp_zeit[0]], temp_zeit[1:][temp_zeit[0:-1,0] != temp_zeit[1:,0]]])

[MagBen]

das Problem mit searchsorted ist, dass die Zeiten nicht lexikalisch sortiert sind.

Zeitstempel aus einer Log-Datei sollten doch aufsteigend sortiert sein.

OK ich seh's, die Zeit ist sortiert aber nicht der String.-
Ohne eine Sortierung wird aber aus dem O(n^2) kein O(n log(n) ) Problem.

[__deets__]

Es ist ja auch kein n log n Problem. Die Daten sind schon sortiert. In dem Moment muss man nur einmal iterieren, wie Sirius3 zeigt. Ist also ein O(n) Problem.

[Jenson]

erstmal danke sehr für die Tipps.

den Tipp von MagBen habe ich umgesetzt und verstanden. Leider hängt es noch an einem kleinen Detail:

Code: Alles auswählen

array = [1,2,3,4,5,6,7,8,9]
test = [1,3,4,6]

mod = numpy.searchsorted(array, test)
print (mod)

print(numpy.delete(array, test, None))

print(numpy.where(array == mod))

ich brauche ja die Übereinstimmungen und die bekomme ich irgendwie nicht raus. Der Zeitgewinn ist allerdings schon sehr spürbar:-)

@Sirius3

Der Tipp mit dem Laden war schon ein echter gewinn! Leider fehlt mir noch einiges an Wissen um den Rest deines Codes zu verstehen aber wenn ich ihn für mein Beispiel benutze bricht er aus irgendeinem Grund an der For-Schleife ab. Ich werde mich jetzt erst einmal mit Lambda-funktionen beschäftigen und dann dass hoffentlich besser verstehen.

hier nochmal die Fehlermeldung und deinen modifizierten Code:

Code: Alles auswählen

import numpy
from itertools import dropwhile
     
flanke_zeit = numpy.genfromtxt("Flanke1_bereinigt.txt", usecols=0, delimiter="\t", dtype=str)
temp_zeit = numpy.genfromtxt("Temp_bereinigt.txt", usecols=[0, 1], delimiter="\t", dtype=str)
     
temp_zeit_iter = iter(temp_zeit)
zeit_sync = [
    next(dropwhile(lambda x: x[0] != zeit, temp_zeit_iter))
    for zeit in flanke_zeit
]
numpy.savetxt("Temp_sync.txt", zeit_sync , fmt="%s", delimiter="\t") 

ergebniss ist StopIteration aber es wird keine Datei geschrieben.

Ich werde jetzt mal mit euren Tipps weiter versuchen. Danke nochmal;-)

[Sirius3]

@Jenson: es gibt einen Zeitpunkt in flanke_zeit der nicht in temp_zeit vorhanden ist. Du mußt halt das Ganze fehlertolerant machen.

Code: Alles auswählen

def convert(zeit):
    return "{2} {1} {0} {3}".format(*"01.01.2018 11:11:11".replace(' ','.').split('.'))

temp_zeit_iter = iter(temp_zeit)
zeit_sync = []
last = None
for zeit in flanke_zeit:
    if not last or last[0] < zeit:
        czeit = convert(zeit)
        last = next(dropwhile(lambda x: convert(x[0]) < czeit, temp_zeit_iter), None)
    if not last or last[0] > zeit:
        print("Zeitpunkt {} nicht gefunden".format(zeit))
    else:
        zeit_sync.append(last)