Top-Themen

AppleEntwicklungHardwareInternetLinuxMicrosoftMultimediaNetzwerkeOff TopicSicherheitSonstige SystemeVirtualisierungWeiterbildungZusammenarbeit

Aktuelle Themen

Administrator.de FeedbackApache ServerAppleAssemblerAudioAusbildungAuslandBackupBasicBatch & ShellBenchmarksBibliotheken & ToolkitsBlogsCloud-DiensteClusterCMSCPU, RAM, MainboardsCSSC und C++DatenbankenDatenschutzDebianDigitiales FernsehenDNSDrucker und ScannerDSL, VDSLE-BooksE-BusinessE-MailEntwicklungErkennung und -AbwehrExchange ServerFestplatten, SSD, RaidFirewallFlatratesGoogle AndroidGrafikGrafikkarten & MonitoreGroupwareHardwareHosting & HousingHTMLHumor (lol)Hyper-VIconsIDE & EditorenInformationsdiensteInstallationInstant MessagingInternetInternet DomäneniOSISDN & AnaloganschlüsseiTunesJavaJavaScriptKiXtartKVMLAN, WAN, WirelessLinuxLinux DesktopLinux NetzwerkLinux ToolsLinux UserverwaltungLizenzierungMac OS XMicrosoftMicrosoft OfficeMikroTik RouterOSMonitoringMultimediaMultimedia & ZubehörNetzwerkeNetzwerkgrundlagenNetzwerkmanagementNetzwerkprotokolleNotebook & ZubehörNovell NetwareOff TopicOpenOffice, LibreOfficeOutlook & MailPapierkorbPascal und DelphiPeripheriegerätePerlPHPPythonRechtliche FragenRedHat, CentOS, FedoraRouter & RoutingSambaSAN, NAS, DASSchriftartenSchulung & TrainingSEOServerServer-HardwareSicherheitSicherheits-ToolsSicherheitsgrundlagenSolarisSonstige SystemeSoziale NetzwerkeSpeicherkartenStudentenjobs & PraktikumSuche ProjektpartnerSuseSwitche und HubsTipps & TricksTK-Netze & GeräteUbuntuUMTS, EDGE & GPRSUtilitiesVB for ApplicationsVerschlüsselung & ZertifikateVideo & StreamingViren und TrojanerVirtualisierungVisual StudioVmwareVoice over IPWebbrowserWebentwicklungWeiterbildungWindows 7Windows 8Windows 10Windows InstallationWindows MobileWindows NetzwerkWindows ServerWindows SystemdateienWindows ToolsWindows UpdateWindows UserverwaltungWindows VistaWindows XPXenserverXMLZusammenarbeit
GELÖST

Algorithmus für Listenvergleiche ?

Frage Entwicklung

Mitglied: RedWraith

RedWraith (Level 1) - Jetzt verbinden

28.04.2010 um 14:47 Uhr, 5336 Aufrufe, 7 Kommentare

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:

01.
ID   TIMESTAMP 
02.
1   2010-01-01_13:30:00 
03.
2   2010-01-22_11:00:00 
04.
3   2010-01-13_08:20:00
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:

01.
Liste A, B	#Die beiden Listen 
02.
#Iteration Liste A 
03.
for i=0 to A.count-1 
04.
	#Iteration Liste B 
05.
	for j=0 to B.count-1 
06.
		#Ist A[i] aktueller als B[j] ? 
07.
		if A[i].TIMESTAMP > B[j].TIMESTAMP then 
08.
			print A[i] 
09.
		else 
10.
			print B[j] 
11.
		end 
12.
	end 
13.
end
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 ?
Mitglied: LotPings
28.04.2010 um 15:08 Uhr
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.

  • 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
Bitte warten ..
Mitglied: RedWraith
28.04.2010 um 15:17 Uhr
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:

01.
Liste A, B	#Die beiden Listen 
02.
#Iteration Liste A 
03.
for i=0 to A.count-1 
04.
	#Iteration Liste B 
05.
	for j=0 to B.count-1 
06.
		if A[i].ID == B[j].ID then 
07.
			#Ist A[i] aktueller als B[j] ? 
08.
			if A[i].TIMESTAMP > B[j].TIMESTAMP then 
09.
				print A[i] 
10.
			else 
11.
				print B[j] 
12.
			end 
13.
		end 
14.
	end 
15.
end
Bitte warten ..
Mitglied: RedWraith
28.04.2010 um 15:32 Uhr
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:
01.
While ListeA.Count > 0 
02.
 
03.
	a = ListeA[ListeA.Count-1] 
04.
	b = NULL 
05.
 
06.
	For Each b In ListeB.Rows 
07.
		If a.ID = b.ID Then 
08.
			Exit For 
09.
		End If 
10.
	Next 
11.
 
12.
	If b != NULL Then 
13.
			If a.TIMESTAMP > b.TIMESTAMP Then 
14.
				print a 
15.
			Else 
16.
				print b 
17.
			End If 
18.
		End If 
19.
		ListeB.Remove[b] 
20.
		 
21.
	Else 
22.
		print a 
23.
	End If 
24.
	ListeA.Remove[a] 
25.
End While 
26.
 
27.
 
28.
While ListeB.Rows.Count > 0 
29.
	b = ListeB[ListeB.Count-1] 
30.
	print b 
31.
	ListeB.Remove[b] 
32.
End While
Bitte warten ..
Mitglied: LotPings
28.04.2010 um 15:58 Uhr
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
Bitte warten ..
Mitglied: maretz
28.04.2010 um 16:04 Uhr
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...)
Bitte warten ..
Mitglied: RedWraith
28.04.2010 um 16:17 Uhr
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*.
Bitte warten ..
Mitglied: maretz
28.04.2010 um 16:35 Uhr
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...
Bitte warten ..
Neuester Wissensbeitrag
Windows 10

Powershell 5 BSOD

(8)

Tipp von agowa338 zum Thema Windows 10 ...

Ähnliche Inhalte
Verschlüsselung & Zertifikate
Veracrypt: Welcher Algorithmus ist bei der Verschlüsselung zu empfehlen? (6)

Frage von NCCTech zum Thema Verschlüsselung & Zertifikate ...

Batch & Shell
gelöst Wlan-adapter such algorithmus in batch (7)

Frage von TicoWrite zum Thema Batch & Shell ...

Heiß diskutierte Inhalte
LAN, WAN, Wireless
gelöst Server erkennt Client nicht wenn er ausserhalb des DHCP Pools liegt (28)

Frage von Mar-west zum Thema LAN, WAN, Wireless ...

Outlook & Mail
gelöst Outlook 2010 findet ost datei nicht (19)

Frage von Floh21 zum Thema Outlook & Mail ...

Microsoft
Ordner mit LW-Buchstaben versehen und benennen (19)

Frage von Xaero1982 zum Thema Microsoft ...

Netzwerkmanagement
gelöst Anregungen, kleiner Betrieb, IT-Umgebung (18)

Frage von Unwichtig zum Thema Netzwerkmanagement ...