Top-Themen

Aktuelle Themen (A bis Z)

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 ?

Mitglied: RedWraith

RedWraith (Level 1) - Jetzt verbinden

28.04.2010 um 14:47 Uhr, 6165 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 ..
Ähnliche Inhalte
Entwicklung
Alles Zufall (Algorithmus gesucht)
Frage von WPFORGEEntwicklung2 Kommentare

Hallo, ich bin auf der Suche nach einer Funktion, die einen bestimmten Betragsbereich (zum Beispiel 80000 -120000) in einzelnen ...

Batch & Shell
Wlan-adapter such algorithmus in batch
gelöst Frage von TicoWriteBatch & Shell7 Kommentare

Hallo zusammen, Ich möchte einen Wlan-adpater such algorithmus in batch erstellen, dazu fehlt mir aber der befehl in Dos. ...

Verschlüsselung & Zertifikate

Veracrypt: Welcher Algorithmus ist bei der Verschlüsselung zu empfehlen?

Frage von NCCTechVerschlüsselung & Zertifikate9 Kommentare

Hallo. Ich möchte eine externe HDD (Seagate Expansion Desktop 4TB) mit Veracrypt verschlüsseln. Nun stellt sich mir die Frage, ...

C und C++

C Sharp Algorithmus soll warten, bis eine Animation abgeschlossen ist

gelöst Frage von YanmaiC und C++6 Kommentare

Hallo ihr Administratoren, ich habe verschiedene Metroframework Animationen in meinem Projekt. Wenn nun die eine Animation ausgeführt werden soll, ...

Neue Wissensbeiträge
Router & Routing
Der "768k-Day" kommt
Information von LordGurke vor 17 StundenRouter & Routing2 Kommentare

Für Leute, die Router mit BGP-Fulltable betreiben vielleicht ein interessanter Hinweis: Die IPv4-Fulltable erreicht voraussichtlich innerhalb der nächsten 2-3 ...

Debian

Partition angeblich voll, dabei aber noch nicht mal zur Hälfte belegt

Anleitung von diemilz vor 19 StundenDebian8 Kommentare

Hallo zusammen, ich habe ein kleines Problem: Ich habe auf einem physischen Debian Linux Server als ZoneMinder-Server (HP ProLiant ...

Windows 7
Updategängelung auf Windows 10, die zweite
Information von Penny.Cilin vor 5 TagenWindows 72 Kommentare

Hallo, da Windows 7 im kommenden Jahr nicht mehr supportet wird, werden Nutzer von Window 7 home premium wieder ...

Internet
EU-Urheberrechtsreform: Zusammenfassung
Information von Frank vor 7 TagenInternet1 Kommentar

Auf golem.de gibt es eine Analyse von Friedhelm Greis, der das Thema EU-Urheberrechtsreform gut und strukturiert zusammenfasst. Zwar haben ...

Heiß diskutierte Inhalte
Backup
Veeam Community Edition
gelöst Frage von dgrebnerBackup21 Kommentare

Hallo Zusammen, kann jemand seine praktischen Erfahrungswerte mit der Veeam-Community Edition mit mir teilen? Es gab dazu ja schon ...

Festplatten, SSD, Raid
Harddisk kaputt, was sagt mir ChrystalDiskInfo
gelöst Frage von InfoSeekerFestplatten, SSD, Raid18 Kommentare

Hallo zusammen, Mein Rechner lahmt. Ich stell mir die Frage woran es liegt und bin der Meinung es ist ...

LAN, WAN, Wireless
Notebooks in Firmenwlan authentifizieren
gelöst Frage von EarthShakerLAN, WAN, Wireless17 Kommentare

Guten Tag, unsere Firma möchte gerne flächendeckend WLAN einführen und hat zu diesem Zweck einen Dienstleister beauftragt. Wir benötigen ...

Netzwerkmanagement
Netzwerk vorübergehend weg
gelöst Frage von ahstaxNetzwerkmanagement13 Kommentare

Hallo, folgendes Szenario stellt sich dar: Im Netzwerk mit Win7-PCs wurden Switche ausgetauscht. Grundsätzlich funktioniert alles mindestens so gut ...