7
Algorithmus für Listenvergleiche ?
Hallo und Guten Tag !
Ich steh vor einem kleinen Programm/Problem.
Und zwar möchte ich zwei ellenlange Listen miteinander vergleichen, allerdings fällt mir kein effektiverer Algorithmus dafür ein.
Die beiden Listen sehen so aus:
Die Listen haben zwar noch mehr Spalten, aber die sind nicht relevant, die ID ist einzigartig und kommt in jeder der beiden Listen 0-1 Mal vor und nach dem TIMESTAMP will ich vergleichen. Ich möchte letztendlich die aktuellsten Daten zu jeder ID bestimmen.
Bisher mache ich das folgendermaßen:
Das funktioniert auch, aber das simple Durchprobieren aller Kombinationen ist ein wenig "barbarisch" und in meinem Fall leider auch zu ineffizient, da beide Listen gut und gerne zwischen 1000 und 3000 Eintragungen haben.
Kennt ihr zufällig eine Möglichkeit, wie man das noch effizienter gestalten kann ?
Und zwar möchte ich zwei ellenlange Listen miteinander vergleichen, allerdings fällt mir kein effektiverer Algorithmus dafür ein.
Die beiden Listen sehen so aus:
ID TIMESTAMP
1 2010-01-01_13:30:00
2 2010-01-22_11:00:00
3 2010-01-13_08:20:00Die Listen haben zwar noch mehr Spalten, aber die sind nicht relevant, die ID ist einzigartig und kommt in jeder der beiden Listen 0-1 Mal vor und nach dem TIMESTAMP will ich vergleichen. Ich möchte letztendlich die aktuellsten Daten zu jeder ID bestimmen.
Bisher mache ich das folgendermaßen:
Liste A, B #Die beiden Listen
#Iteration Liste A
for i=0 to A.count-1
#Iteration Liste B
for j=0 to B.count-1
#Ist A[i] aktueller als B[j] ?
if A[i].TIMESTAMP > B[j].TIMESTAMP then
print A[i]
else
print B[j]
end
end
endDas funktioniert auch, aber das simple Durchprobieren aller Kombinationen ist ein wenig "barbarisch" und in meinem Fall leider auch zu ineffizient, da beide Listen gut und gerne zwischen 1000 und 3000 Eintragungen haben.
Kennt ihr zufällig eine Möglichkeit, wie man das noch effizienter gestalten kann ?
Share on Facebook
Share on Twitter
Share on Reddit
Share on LinkedinPlease also mark the comments that contributed to the solution of the article
Content-Key: 141654
Url: https://administrator.de/contentid/141654
Printed on: April 25, 2024 at 09:04 o'clock
7 Comments
Latest comment
Mon,moin.
Haben beide Listen immer die gleichen IDs?
Dann brauchst du nur eine Zählschleife - wenn nicht kann dein Beispiel nicht funktonieren du vergleichst die IDs ja garnicht.
Gruß
LotPings
Haben beide Listen immer die gleichen IDs?
Dann brauchst du nur eine Zählschleife - wenn nicht kann dein Beispiel nicht funktonieren du vergleichst die IDs ja garnicht.
- Deine Datum hat doch günstigerweise schon eine sortierfähige Formatierung, hänge beide Listen aneinander, sortiere sie und behalte immer nur den neuesten Eintrag jeder ID.
- Die Alternative wäre, beide Listen parallel durchzugehen und den bei gleicher ID neueren Eintrag auszugeben; das erhöhen der Zähler bei nicht vorhander ID wird etwas tricky.
Gruß
LotPings
Arg, ich hab beim Schreiben des Pseudocodes etwas geschlampt.
Ja, sie haben die gleichen IDs, ich hab den Abgleich nur vergessen.
So muss es eigendlich sein:
Ja, sie haben die gleichen IDs, ich hab den Abgleich nur vergessen.
So muss es eigendlich sein:
Liste A, B #Die beiden Listen
#Iteration Liste A
for i=0 to A.count-1
#Iteration Liste B
for j=0 to B.count-1
if A[i].ID == B[j].ID then
#Ist A[i] aktueller als B[j] ?
if A[i].TIMESTAMP > B[j].TIMESTAMP then
print A[i]
else
print B[j]
end
end
end
end
Ich habe eine Lösung gefunden, die fühlbar effizienter läuft.
Es gibt im drei Fälle, die es abzudecken gilt.
Fall 1 - Ist ID in ListeA und in ListeB, dann wird TIMESTAMP verglichen und das Aktuellere ausgegeben.
Fall 2- Ist ID in ListeA aber nicht in ListeB, wird der Eintrag ausgegeben.
Fall 3- Ist ID nicht in ListeA aber in ListeB, wird der Eintrag ebenfalls ausgegeben.
Der Code weiter unten schleift sollange dirch Liste A, bis diese leer ist.
Es wird immer das letzte Element a der Liste genommen, dann durchläuft eine Schleife komplett die Liste B und sucht dabei nach einem Element b, dass gleich a ist.
Wurde ein passendes b gefunden (Fall 1), wird die Schleife abgebrochen, danach werden die TIMESTAMPs von a und b verglichen, der aktuellere wird ausgegeben.
Anschließend wird das Element b aus der Liste B entfernt. Wurde kein passendes b gefunden (Fall 2), dann wird einfach a ausgegben.
In jedem Fall muss dann das Element a aus der Liste A entfernt werden.
Als letztes werden die verbleibenden Elemente b in Liste B durchlaufen und ausgegeben (Fall 3).
Manchmal kann es doch so einfach sein
Meine Lösung sieht folgendermaßen aus:
Es gibt im drei Fälle, die es abzudecken gilt.
Fall 1 - Ist ID in ListeA und in ListeB, dann wird TIMESTAMP verglichen und das Aktuellere ausgegeben.
Fall 2- Ist ID in ListeA aber nicht in ListeB, wird der Eintrag ausgegeben.
Fall 3- Ist ID nicht in ListeA aber in ListeB, wird der Eintrag ebenfalls ausgegeben.
Der Code weiter unten schleift sollange dirch Liste A, bis diese leer ist.
Es wird immer das letzte Element a der Liste genommen, dann durchläuft eine Schleife komplett die Liste B und sucht dabei nach einem Element b, dass gleich a ist.
Wurde ein passendes b gefunden (Fall 1), wird die Schleife abgebrochen, danach werden die TIMESTAMPs von a und b verglichen, der aktuellere wird ausgegeben.
Anschließend wird das Element b aus der Liste B entfernt. Wurde kein passendes b gefunden (Fall 2), dann wird einfach a ausgegben.
In jedem Fall muss dann das Element a aus der Liste A entfernt werden.
Als letztes werden die verbleibenden Elemente b in Liste B durchlaufen und ausgegeben (Fall 3).
Manchmal kann es doch so einfach sein
Meine Lösung sieht folgendermaßen aus:
While ListeA.Count > 0
a = ListeA[ListeA.Count-1]
b = NULL
For Each b In ListeB.Rows
If a.ID = b.ID Then
Exit For
End If
Next
If b != NULL Then
If a.TIMESTAMP > b.TIMESTAMP Then
print a
Else
print b
End If
End If
ListeB.Remove[b]
Else
print a
End If
ListeA.Remove[a]
End While
While ListeB.Rows.Count > 0
b = ListeB[ListeB.Count-1]
print b
ListeB.Remove[b]
End While
Gut wenn du eine bessere Lösung gefunden hast,
wenn ListeB aufsteigend nach ID sortiert ist, musst du die eigentlich auch nicht immer komplett durchlaufen, wenn du dir den letzten Index merkst, brauchst du nur da aufsetzen, aber natürlich keine foreach Schleife dann.
Gruß
LotPings
wenn ListeB aufsteigend nach ID sortiert ist, musst du die eigentlich auch nicht immer komplett durchlaufen, wenn du dir den letzten Index merkst, brauchst du nur da aufsetzen, aber natürlich keine foreach Schleife dann.
Gruß
LotPings
Moin,
als erstes würde ich empfehlen immer auf die ID zuerst zu vergleichen. Da das ein reiner Zahlenwert ist bedeutet dass das du einen Integer-Vergleich machst. Dies geht um ein vielfaches Schneller als ein komplexer String-Vergleich (im Endeffekt mit einem Maschinenbefehl - cjne u.ä.)
Dann ist die Frage: möchtest du schnell (und speicherintensiv) arbeiten? Falls das ok wäre würde ich das so machen das ich beide Listen vergleiche -> und immer wenn ich eine ID in beiden Listen finde dann wird diese ID in nem Array gepackt.
Danach gehe ich erst durch und sage das ich für jede ID die im Array ist die Datumswerte vergleiche... Das kostet zwar Speicher aber sorgt dafür das ich nur die Werte vergleiche die mich wirklich intressieren (intressant dabei wäre noch ob es eher viele Treffer sein werden - oder nur wenige Treffer zu erwarten sind... Im letzten Fall kann man auch gleich die Datumswerte in den Speicher packen -> dann brauch ich die Liste nicht erst mehrfach von der Platte lesen...)
als erstes würde ich empfehlen immer auf die ID zuerst zu vergleichen. Da das ein reiner Zahlenwert ist bedeutet dass das du einen Integer-Vergleich machst. Dies geht um ein vielfaches Schneller als ein komplexer String-Vergleich (im Endeffekt mit einem Maschinenbefehl - cjne u.ä.)
Dann ist die Frage: möchtest du schnell (und speicherintensiv) arbeiten? Falls das ok wäre würde ich das so machen das ich beide Listen vergleiche -> und immer wenn ich eine ID in beiden Listen finde dann wird diese ID in nem Array gepackt.
Danach gehe ich erst durch und sage das ich für jede ID die im Array ist die Datumswerte vergleiche... Das kostet zwar Speicher aber sorgt dafür das ich nur die Werte vergleiche die mich wirklich intressieren (intressant dabei wäre noch ob es eher viele Treffer sein werden - oder nur wenige Treffer zu erwarten sind... Im letzten Fall kann man auch gleich die Datumswerte in den Speicher packen -> dann brauch ich die Liste nicht erst mehrfach von der Platte lesen...)
Die Idee ist nicht schlecht maretz
In meinem Fall gibt es eigentlich keine ID, die nicht abgearbeitet werden soll.
Zum Hintergrund:
Es geht darum zwei völlig redundante Systeme zur Gestellverwaltung zusammenzuführen. Wir haben hier ein paar tausend Gestelle, die fortlaufend durchnummeriert sind und so banal es auch klingt, ich soll eine Auflistung erstellen, welche Gestelle noch außer Haus sind und zwar seit wann und bei wem.
Die Perversitäten gehen damit los, dass wir zwei Standorte haben und jeder hat ein eigenes Gestellverwaltungsprogramm, welche nicht miteinander synchronisiert werden. Dazu kommt noch, dass die Gestelle nicht Standortgebunden sind. Die Gestelle mit den IDs 1 bis 5000 sind in beiden Systemen angelegt, also meint die ID in System A dasselbe Gestell wie in System B.
Jetzt könnte man einfach hingehen und die ausgebuchten Gestelle aus Standort A und die aus Standort B abrufen und einfach zusammenschustern, aber leider kommen Gestelle nicht immer wieder dort an, wo sie ausgebucht sind.
Zum Beispiel wird Gestell 4711 in Standort A als "Versandt" gebucht und eine Woche später dann in Standort B ins "Lager" gebucht.
Davon kriegt aber das System in Standort A garnicht mit, dort ist 4711 immernoch als "Versandt" gebucht.
Einzige Lösung ist eine Liste aller aktuellen Gestellzustände aus beiden Systemen abrufen und dann über den Timestamp vergleichen.
Und das am Besten in unter 2 Minuten *hust*.
In meinem Fall gibt es eigentlich keine ID, die nicht abgearbeitet werden soll.
Zum Hintergrund:
Es geht darum zwei völlig redundante Systeme zur Gestellverwaltung zusammenzuführen. Wir haben hier ein paar tausend Gestelle, die fortlaufend durchnummeriert sind und so banal es auch klingt, ich soll eine Auflistung erstellen, welche Gestelle noch außer Haus sind und zwar seit wann und bei wem.
Die Perversitäten gehen damit los, dass wir zwei Standorte haben und jeder hat ein eigenes Gestellverwaltungsprogramm, welche nicht miteinander synchronisiert werden. Dazu kommt noch, dass die Gestelle nicht Standortgebunden sind. Die Gestelle mit den IDs 1 bis 5000 sind in beiden Systemen angelegt, also meint die ID in System A dasselbe Gestell wie in System B.
Jetzt könnte man einfach hingehen und die ausgebuchten Gestelle aus Standort A und die aus Standort B abrufen und einfach zusammenschustern, aber leider kommen Gestelle nicht immer wieder dort an, wo sie ausgebucht sind.
Zum Beispiel wird Gestell 4711 in Standort A als "Versandt" gebucht und eine Woche später dann in Standort B ins "Lager" gebucht.
Davon kriegt aber das System in Standort A garnicht mit, dort ist 4711 immernoch als "Versandt" gebucht.
Einzige Lösung ist eine Liste aller aktuellen Gestellzustände aus beiden Systemen abrufen und dann über den Timestamp vergleichen.
Und das am Besten in unter 2 Minuten *hust*.
Naja - ob du jetzt ne normale ID hast oder ne Gestell-ID -> das bleibt sich gleich... Das Problem für dich fängt an wenn du versuchst 2 Strings (und nen Timestamp ist erstmal nichts anderes) zu vergleichen. Du kannst den jetzt entweder in nen Unix-Timestamp umwandeln - das kostet Zeit... Oder du vergleichst 2 Strings -> das Kostet auch Zeit.
Ist eigentlich auch ganz einfach: Im Maschinencode kannst du entweder (vereinfacht) sagen:
cje (R0,2,xyz)
-> Vergleiche den Wert in Register Null mit ner 2 -> wenn R0 auch eine Zwei enthält springe. Machst du das ganze jetzt mit 2 Texten dann muss er sich ja deinen Text erst in ein nutzbares Format (z.B. Hex,...) umwandeln und das dann Zeichen für Zeichen vergleichen. Selbst wenn man davon ausgeht das der Compare-Befehl 2 Takte benötigt dann ist es glaub ich nachvollziehbar das es bei einem Vergleich von mehreren Tausend Werten einen gewaltigen Unterschied machst ob du jetzt 1000x 2 Takte opferst -> oder 1000 * 19 * 2 Takte (19 weil 2009-01-01 10:00:00 genau 19 Zeichen sind). Wenn du jetzt noch davon ausgehst das jede CPU heute mit Pipelines arbeitet und die bei nem Sprung ggf. noch zurückbearbeitet werden müssen usw. -> dann ist dieser Zeitunterschied gigantisch... Das kann den Unterschied zwischen 2 und 20 Minuten machen...
Was du natürlich auch machen kannst: Du wirst ja vermutlich in einer Datenbank arbeiten -> was wäre denn wenn du einfach die DB die Arbeit machen lässt? Du importierst die Daten von Standort 2 einfach bei Standort 1. Dann lässt du dir eine Liste ausgeben:
Select s1.timestamp, s2.timestamp, s1.id, s2.id from Standort1, Standort2 where s1.id=s2.id
Jetzt hast du schonmal EINE Liste bei der die IDs mit Timestamp vorhanden sind die in beiden Listen sind. Das ganze kannst du natürlich noch verfeinern -> und dein Problem verringert sich sofort erheblich...
Ist eigentlich auch ganz einfach: Im Maschinencode kannst du entweder (vereinfacht) sagen:
cje (R0,2,xyz)
-> Vergleiche den Wert in Register Null mit ner 2 -> wenn R0 auch eine Zwei enthält springe. Machst du das ganze jetzt mit 2 Texten dann muss er sich ja deinen Text erst in ein nutzbares Format (z.B. Hex,...) umwandeln und das dann Zeichen für Zeichen vergleichen. Selbst wenn man davon ausgeht das der Compare-Befehl 2 Takte benötigt dann ist es glaub ich nachvollziehbar das es bei einem Vergleich von mehreren Tausend Werten einen gewaltigen Unterschied machst ob du jetzt 1000x 2 Takte opferst -> oder 1000 * 19 * 2 Takte (19 weil 2009-01-01 10:00:00 genau 19 Zeichen sind). Wenn du jetzt noch davon ausgehst das jede CPU heute mit Pipelines arbeitet und die bei nem Sprung ggf. noch zurückbearbeitet werden müssen usw. -> dann ist dieser Zeitunterschied gigantisch... Das kann den Unterschied zwischen 2 und 20 Minuten machen...
Was du natürlich auch machen kannst: Du wirst ja vermutlich in einer Datenbank arbeiten -> was wäre denn wenn du einfach die DB die Arbeit machen lässt? Du importierst die Daten von Standort 2 einfach bei Standort 1. Dann lässt du dir eine Liste ausgeben:
Select s1.timestamp, s2.timestamp, s1.id, s2.id from Standort1, Standort2 where s1.id=s2.id
Jetzt hast du schonmal EINE Liste bei der die IDs mit Timestamp vorhanden sind die in beiden Listen sind. Das ganze kannst du natürlich noch verfeinern -> und dein Problem verringert sich sofort erheblich...
