Schleife sehr langsam, mögliche alternative?

Neo Gandar

Hallo zusammen.

Hab wieder ein, mehr oder weniger, Problem.
Der Code funktioniert zwar einwandfrei, jedoch dauert das durchlaufen der Schleife ewig (2 Listen mit je ~24.000 einträgen = ~500.000.000 Durchläufe)

Hier mal die Schleife:

for(tempiter = parseList.begin();tempiter != parseList.end(); ++tempiter){
		for(mainiter = mainList.begin(); mainiter != mainList.end(); ++mainiter){
			if(tempiter->get_typeID() == mainiter->get_typeID()&&
			   tempiter->get_locationID() == mainiter->get_locationID()){
				tempiter->data.set_adjusted(true);
				mainiter->data.set_adjusted(true);
				mainiter->set_squantity(tempiter->get_squantity());
				mainiter->quantities.set_quantity(tempiter->quantities.get_quantity());
				break;
			};
		};
		mainiter=mainList.begin();
	};

Der Code durchsucht 2 Listen. Wenn die an den Positionen des Iterators die typeID und die locationID gleich sind, ändert er die Werte.

Da ich es niemanden zumuten kann, stunden zu warten bis die schleife fertig ist (ich lass es grad mit nem counter laufen, in 10 minuten etwa 15mio durchläufe), wollt ich fragen ob es da Alternativen gibt, wie man diese Vergleichen beschläunigen könnte. Vielleicht die Daten nicht in einer Liste speichern?

Oder gibt es nen Algorithmus, der für das schnelle vergleichen von vielen Daten gemacht worden ist?

Neo Gandar

Ok, 1) std::cout ist langsam , also hat mein "counter" die schleife total abgebremst, wenn ich die durchläufe nur am ende Angebe, dauerts etwa 30 sekunden bis alles durchlaufen ist, ist zwar trotzdem noch ned schnell, aber noch akzeptabel.

in einer Folgefunktion übersehen, dass ein iterator nicht inkrementiert wird -> endlosschleife.

Würde mich aber trotzdem interessieren ob es da schnellere Lösungen für das Vergleichen von Daten gibt. Aja, die anzahl der Daten steht zu beginn nicht fest, müssen also dynamisch hinzugefügt werden können.

Tachyon

Vielleicht std::multiset ?

Beide Listen immer komplett durchzulaufen ist natürlich langwierig. Du solltest dir überlegen, was du von den Listen erwarten kannst, und was du vom Resultat erwartest.

Sind in den Listen duplicates? Also Objekte, die gleiche typeid und locationid haben? Wie gehst du damit um? möchtest du in mainList bei jeder Übereinstimmung die Werte neu setzen?
Wäre es evtl. sinnvoller, erst über die mainList zu iterieren, und bei einem Treffer in der innere Schlife den Lauf in der inneren Schleife abbrechen, als nicht mehr bis zum Ende iterieren?
Solltest du nur interesse an der letzten Übereinstimmung in tempList haben, iterier doch von hinter rein (tempIter--) und dann abbrechen.
Du kannst in dem if() in der inneren Schleife auch noch nach "!main_iter->data.is_adjusted()" fragen und eben nicht reingehen, wenn adjusted true ist.
Daten sortieren (nach typeID oder sonstwas) Und parallel durch beide itereieren, damit du nicht immer bei begin() anfangen musst obwohl du die meisten Sachen schon durch hast...
Die Elemente, die du durch hast aus der Liste rausschmeißen, dass der nächste Durchlauf schneller wird.

USWUSF

Musst halt selber überlegen, ob es Fälle gibt, bei denen du eine Schleife abbrechen kannst. Oder du irgendwie die Listen verkürzen kannst, sortieren, etc.

pumuckl

Du könntest Beispielsweise beide Listen nach typeID und locationID sortieren, dann kannst du das alles auf eine Schleife reduzieren, die parallel durch beide Contaier läuft. Dann würd ich mir an deiner Stelle noch die Algorithmen der Standardbibliothek anschauen (siehe http://www.cplusplus.com/reference/algorithm/), ob die deine Arbeit evtl. vereinfachen können.

1. Beide Listen sortieren nach den Vergleichskriterien (typeID, locationID).
2. Wenn in der inneren Schleife die Vergleichskriterien größer geworden sind, als in der äußeren, innere Schleife abbrechen (nicht gefunden), aber den Satz merken - nicht wieder von vorne beginnen, sondern mit dem nächsten Satz der äußeren Schleife erst wieder gegen diesen prüfen.

So durchläufst Du jede Liste nur einmal.

Da war ich wohl zu langsam ...

Ich würde einfach mit Quicksort sortieren. Und dann "Binäre Suche" verwenden.

Neo Gandar

Danke für die Antworten, bin gerade erst vom Arbeiten heimgekommen.

Zu den Listen.

Sortieren, und dann parallel vergleichen funktioniert leider nicht.

Kurz zur beschreibung der Listen:

Die Einträge in der ParseList sind aktuelle Informationen über den Lagerbestand, also neue Gegenstände im Lager und geänderte Stückzahlen.

Die Einträge in der Mainlist, ist der Zuletzt abgerufenen Lagerbestand. Hier sind weitere Daten enthalten, wie Mindest- und Maximal Stückzahlen.

Da sich die ParseList immer ändert, neue Gegenstände hinzukommen, alte wegfallen, kann ich sie nicht sortieren und dann parallel vergleichen.

Die Daten sind jedoch schon vom Import her immer in der etwa gleichen Reihenfolge (ausser es ändert sich was, verständlich).

Sind in den Listen duplicates? Also Objekte, die gleiche typeid und locationid haben? Wie gehst du damit um? möchtest du in mainList bei jeder Übereinstimmung die Werte neu setzen?

Ja, es sind Objekte mit gleichen TypeID und LocationID, jedoch -siehe oben-. Ja, ich möchte bei jeder übereinstimmung die Werte neu setzten. Das ist immer noch schneller, als zu überprüfen ob sich die Werte seit dem letztem Import verändert haben.

Wäre es evtl. sinnvoller, erst über die mainList zu iterieren, und bei einem Treffer in der innere Schlife den Lauf in der inneren Schleife abbrechen, als nicht mehr bis zum Ende iterieren?

Da beide Listen annähernd gleich groß sind, ist es egal von welcher Liste iteriert wird. Der durchlauf wird beim ersten Fund sowieso abgebrochen.

Solltest du nur interesse an der letzten Übereinstimmung in tempList haben, iterier doch von hinter rein (tempIter--) und dann abbrechen.

Die Daten sollten schon vollständig miteinander verglichen werden

Du kannst in dem if() in der inneren Schleife auch noch nach "!main_iter->data.is_adjusted()" fragen und eben nicht reingehen, wenn adjusted true ist.

Das Adjusted dient einem anderen Zweck. Wenn von einem Gegenstand nichts mehr da ist, ist er auch in den Daten in der Parselist nicht mehr vorhanden. Da aber Mindest/Max bestand trotzdem gewährleistet sein muss, dienst dies dazu Gegenstände, die eben nicht geändert wurden (und damit nicht mehr vorhanden sind laut import) auf Stückzahl 0 zu setzten.

Die Elemente, die du durch hast aus der Liste rausschmeißen, dass der nächste Durchlauf schneller wird.

Das wäre vielleicht eine Idee, dazu muss ich allerdings von der anderen Liste iterieren. Mal ausprobieren.

Vielleicht std::multiset?

Wär das schneller als ne std::list?

volkard

mir scheint, das posting von pumuckl hat gewonnen mit O(n*log(n)) wenn n die größe der größeren der beiden listen ist.
um das zu verinnerlichen, nimm die mal ein paar stunden zeit und schau dir mergesort ganz intensiv an.

darüberhinaus kannst du, wenn ich das recht verstehe, die sehr wenigen änderungen (weil per hand gemacht) ausklinken, getrennt sortieren und zurückmergen vor dem dicken merge. mit m=anzahlDerHandÄnderungen biste bei O(m*log(m)+n). also einfach blitzschnell. damit meine ich zeiten von deutlich weniger als einer sekunde.

Neo Gandar

oh ja, Mergesort scheint genau das richtige zu sein. Werd mich da mal einarbeiten.

Vielen Dank

volkard

eventuell wäre es gut, wenn du dir zur mittsommernacht, falls du sie überlebst, den sedgewick/C
Algorithmen in C | ISBN: 3893193766
schenken würdest. nicht, daß du ihn dringend nötig hättest, aber er ist der geilste einstieg in die algorithmenbücher für praktiker, die keine gamecoderz sind.
und nicht ausweichen auf sedgewick/C++, sedgewick/Java, sedgewick/Larifari. da reitet der verlag nur auf dem erfolg und baut diversen bockmist.

Neo Gandar

Danke, werd ich mir bei möglichkeit zulegen. Benutzte seit einiger Zeit das Buch vom Verlag Galileo Computing, "C++ von A bis Z" von Jürgen Wolf. In dem wird zwar kurz auf Algorithmen eingegangen, jedoch nur auf die der STL.

Tachyon

Neo Gandar schrieb:

Vielleicht std::multiset?
Wär das schneller als ne std::list?

Das hängt von den Umgebungsbedingungen ab. Die Multiset ist schon sortiert. Die Objekte werden bereits beim Einfügen in die Map gemäß des vorgegebenen Kriteriums sortiert.
Außerdem kann man sich Ranges von gleichen Objekten herausziehen (sofern es bei dir Doubletten gibt).

Neo Gandar

@Tachyon: Nein, es gibt keine Doubletten. Werd aber dennoch Mergesort nehmen, da dies eine Aufgabe is, an der ich meine Kenntnisse verbessern kann, und mein Verständnis für alternative Lösungen verbessert wird.

Mir ist, während der Arbeit ^^, noch eine wesentliche Bremse aufgefallen (wurde kurz schon in nem anderen post von mir erwähnt von jemandem). Es ist um einiges schneller, normale Variablen (int, double, long...) zu verlgeichen, als std::strings miteinander zu vergleichen. Der unterschied dazwischen kommt bei meinem Beispiel sehr gut hervor. Wenn ich gleich zu beginn, alle werte von std::string in unsigned long konvertiere (also alle IDs), und dann die Schleife laufen lasse, ist das nochmal um etwa 1/3 schneller als davor. Ich freu mich schon richtig wie schnell das dann mit mergesort wird

#Edit @Volkard Zu deinem Buchtipp. Hab ein bisschen gesucht, und gesehen, dass die Ausgabe "Algorithmen in C" bei sehr vielen Verlagen als "nicht mehr Lieferbar/auf unbestimmte Zeit" gesetzt ist. Ich versuche es am Samstag noch beim Buchhändler meines Vertrauens, aber wenn der mir das auch sagt, wär es ne Alternative doch "Algorithmen in C++" zu nehmen? Diese wäre noch verfügbar.

volkard

Neo Gandar schrieb:

#Edit @Volkard Zu deinem Buchtipp. Hab ein bisschen gesucht, und gesehen, dass die Ausgabe "Algorithmen in C" bei sehr vielen Verlagen als "nicht mehr Lieferbar/auf unbestimmte Zeit" gesetzt ist. Ich versuche es am Samstag noch beim Buchhändler meines Vertrauens, aber wenn der mir das auch sagt, wär es ne Alternative doch "Algorithmen in C++" zu nehmen? Diese wäre noch verfügbar.

Jup. Auch ein durchschnittliches Käsebrötchen ist besser, als zu hungern zu müssen.