Daten vergleichen

Hallo,

ich habe in meiner Anwendung 2 unsortierte Datensätze (Strings variabler Länge) mit einer variablen Anzahl von Elementen. Fest steht dass in Datensatz 1 kein Element doppelt vorkommt. Jetzt ist der Datensatz 2 so zu prüfen ob die Elemente schon in Datensatz 1 vorkommen (identische Strings!). Wenn das durch ist dann muss innerhalb des Datensatzes 2 nochmals geprüft werden ob doppelte Elemente vorhanden sind. Die Datensätze können schon mal 100.000 Elemente enthalten.

Welche Vorhegensweise haltet ihr für effektiv, sprich von der Programmlaufzeit am schnellsten.

Wer weis was?

Martin Richter

Nimm eine map<string,long> für Datensatz 1.
Dann lies Datensatz 2 durch und für jeden Treffer in der map den Long um 1.
Dann hast Du beides in einem Aufwasch.

Danke Martin für die Antwort. Ich kann aber nichts damit anfangen, ich hab mal gegooglet, map scheint wohl eine c++ Klasse zu sein. Ich schreib mein Programm aber in C. Hast du da auch einen passenden Tip? (Ausser: lerne c++)

Martin Richter

Dann verwende das gleiche verfahren, obwohl das ungleich schwerre ist.

Baue einen Baum oder eine Hashmap auf mit Datensatz1 + Zähler. (Je nach Typ ist der Aufwand n*log(n)). Schrittweises binäres einfügen geht auch.

Dann liest Du Datensatz 2 ein und greifst über einen Hash oder eben binäre Suche in Deiner Datenstruktur. Bei einem Treffer zählst Du den Zähler hoch.

1. Es ändert sich nichts am Verfahren!
2. Du kannst auch ein einem C Programm C++ verwenden.
3. Selbst wenn Du C programmierst sollten Dir Verfahren aus C++ geläufig sein.

volkard

Ich schlage ein anderes Verfahren vor:
Beide Listen sortieren und dann parallel durchgehen (ähnlich zu Mergesort).

Guten Morgen,

Ich habe jetzt mal begonnen die Sache umzusetzten, soweit ich sie verstanden habe und soweit es in meinem programmiertechnischen Fähigkeiten lag.

Der vorläufige Plan:
1. beide Datensätze sortieren (nach Strings)
2. Elementvergleich Datensatz1 mit Datensatz2 durchführen (nach Strings)
3. Elementvergleich benachbarter Elemente (da ja jetzt sortiert) in Datensatz2 durchführen (nach Strings)

Der IST-Stand:
1. beide Datensätze sortieren (nach Strings)
Meine bisherige Variante: sehr ineffektiv

for(i = 0; i < (anzahl_elemente - 1); i++){
		for(j = 0; j < (anzahl_elemente - 1); j++){
			if(_stricmp((ppzfileinfo[j])->name, (ppzfileinfo[j+1])->name) > 0){
				pzfileinfo_help = ppzfileinfo[j];
				ppzfileinfo[j] = ppzfileinfo[j+1];
				ppzfileinfo[j+1] =pzfileinfo_help;
			}
		}
	}

obiger Code dauert mit ca 45000 Elementen ca 600 Sekunden, nachfolgender Code dauert ohne "_stricmp" nur 3,2 Sekunden

for(i = 0; i < (anzahl_elemente - 1); i++){
		for(j = 0; j < (anzahl_elemente - 1); j++){

		}
	}

Jetzt hat Martin von Hash gesprochen, möglicherweise meinst du damit im Vorfeld schon einen Hash vom String (lowercase Strings) bilden und mit abspeichern, danach nur noch die gespeicherten Hashs vergleichen, müsste wesentlich schneller gehen. Welches Hash-Verfahren sollte ich dann da benutzen?

Was haltet ihr von dem Lösungsansatz?

volkard

Sortieren mit qsort(), Quicksort, Heapsort, Mergesort, die sind alle ähnlich schnell.

qsort war ein guter Tip, danke.