Extremes Geschwindigkeitsproblem mit 2 Containern

[Gast]

Ich arbeite grad an meiner Projektarbeit und steh vor einem Geschwindigkeitsproblem: Ich hab 1 short int Container x[i][k] mit ca. i = 4.000.000 und k = 5 und 1 short in Container y[l][m] mit l=1000 und m=5, wobei x öfter mal neu eingelesen wird.

Es muss geschaut werden, ob es zwischen x und y Übereinstimmungen gibt. Die Werte in den jeweiligen Containern sind bereits sortiert, nur das Vergleichen dauert immer noch ewig.

Hier mal der Codeschnipsel der Vergleichsfunktion:
for(long i ...) {
for(int k ...)
for(long l ...)
for(int m...)
if(x[i][k]==y[l][m]) counter++;
if(counter==5) gefunden
counter=0;
}


Nun dachte ich mir, ich könnte hergehen und erstmal x etwas kleiner machen, indem ich unzulässige Werte rauslösche:


for(long i ...)
for(int k ...)
if(x[i][k]>grenze) {
x.erase(x.begin()+i-counter)
counter++;
}


Nun dauert es aber 1s pro Löschvorgang. Gibt es eine Möglichkeit das etwas zu beschleunigen? Ich benutze derzeit ein Macbook mit einem Core 2 Duo mit 2 Ghz und 2 GB Arbeitsspeicher und Visual Studio 2008 prof. unter Windows XP. Meine Einstellungen unter VS 2008 sehen so aus:

/O2 /Oi /Ot /D "WIN32" /D "_DEBUG" /D "_CONSOLE" /D "_UNICODE" /D "UNICODE" /Gm /EHsc /MTd /arch:SSE2 /Fo"Debug\\" /Fd"Debug\vc90.pdb" /W3 /nologo /c /Zi /TP /errorReport:prompt

Ein Array sollte dank []-Operator und der Optimierung /O2 doch kaum noch Vorteile bringen, oder?

[Trap]

Du benutzt beim Vergleichen die bestehende Sortierung nicht, kein Wunder, dass es dann langsam ist.

Aktiviertes Debugging kann ziemlich viel Performance kosten, je nach Compiler (hab jetzt nicht im Kopf wie VS08 sich in der Hinsicht verhält). Eventuell werden da bei den Standardcontainern zusätzliche Überprüfungen aktiviert. Das Problem würde ich aber eher beim Algorithmus sehen.

[Berni]

Eine Performanceoptimierung könnte sein, dass du x[i], x[i][k] und y[l] an den entsprechenden Stellen in temporäre Variablen speicherst und dann über dieses gecacheten Variablen zugreifst. Arrayzugriffe sind zwar relativ schnell aber auf eine Variable gehts eben nochmal schneller.
Also in etwa so:
for(long i ...) {
short[] tmpI = x[i];
for(int k ...){
short tmpIK = tmpI[k];
for(long l ...){
short[] tmpL = y[l];
for(int m...){
if(tmpIK==tmpL[m]) counter++;
if(counter==5) gefunden
counter=0;
}
}
}
}
Edit: Im Sinne des Cachings der Variablen könnte es hier sinnvoller sein, x und y zu vertauschen. Denn das y-Array ist ja anscheinend wesentlich kleiner als das x-Array und somit könnte man wesentlich mehr vom Caching profitieren wenn man eben "andersrum" vergleicht!

Die Sortierung habe ich nicht ganz verstanden. Ist das x-Array nur innerhalb der k Werte sortiert oder das insgesamt schon komplett sortiert?

[Monger]

Ich bin ja nicht überzeugt davon, ob das hier nicht ein Joke Thread ist... Jedes von 20 Millionen Elementen wird mit 5000 anderen Elementen verglichen, und du wunderst dich dass das Zeit braucht?

Okay, nehmen wir es mal ernst. Was genau meinst du mit "Element rausschmeißen"? Wenn du jedesmal das Array dabei neu instanziierst, dauert es natürlich auch ne ganze Weile.

Wenn die Arrays wirklich vorsortiert sind, kannst du deine Suche abbrechen sobald du auf ein Element kleiner als der Vergleichswert triffst.
Signifikant schneller kannst du solch einen Algorithmus nur machen indem du die Menge der Operationen einschränkst. Bei einer Suche hilft es, so früh abzubrechen wie es nur geht.

[Abraxus]

Wenn das ganze vorsortiert ist, dann fühlt man dem am besten mit binarysearch auf den Zahn.

[Gast]

Schonmal danke für die Tipps, joke ist es keiner ;)

Hatte ganz vergessen auf Release zu schalten, danke. Aber mir fehlt hier immer noch ein Faktor 10 *duck*

Nach dem Caching muss ich mal schaun. Was genau limitiert denn hier? CPU, Arbeitsspeicher oder Festplatte? Würde es denn was bringen, wenn ich hier von short int auf char oder float gehen würde?

Ich hab mir auch schon überlegt ein paar Abbruchbedingungen reinzumachen, aber dachte mir das wäre langsamer wenn hier nochmal ne zusätzliche Abfrage drin wäre

[Senior Sanchez]

Wenn das ganze vorsortiert ist, dann fühlt man dem am besten mit binarysearch auf den Zahn.

Wenn ne Gleichverteilung der Daten in einem Intervall vorliegt, könnte man sogar interpolationsearch nutzen. :)

[Trap]

Nein, du brauchst keine Optimierung der Implementierung, sondern einen O(n log n) oder O(n) Algorithmus statt deinem mit O(n²).

[anderer Gast]

Falls Du nach Ausnutzung der Sortierung noch Zeitprobleme hast: Dein Problem läßt sich prima parallelisieren.

[Gast]

Parallelisieren lässt sich das auf alle Fälle, nur wie man sowas programmiert hab ich keine Ahnung. Ich denke nen Teil wird der Compiler schon gemacht haben, da ich derzeit eine Auslasung von 50% auf beiden Cores habe

[Berni]

Nö wenns genau 50% pro core sind wirds eben gerade nicht parallelisiert; du müsstest (annähernd) 100% pro Core haben. Aufteilen kannst dus indem du zwei Threads startest und jeder übernimmt die Hälfte des x-Arrays. Die Frage ist aber was dein "gefunden" und counter genau machen soll. Wenn man nicht am Ende der beiden Threads die Ergebnisse (der counter-Wert?) miteinander verrechnen kann, dann bringt eine Parallelisierung nämlich praktisch nix weil sie nur mit Synchronisierungsaufwand möglich wäre der den Performancegewinn dann zunichte macht...aber dazu müsstest du uns mal mitteilen, was denn nun genau für Daten vorliegen und wie diese sortiert sind und was genau rauskommen soll.

[Gast]

Versteh ich nicht, warum ist nicht parallelisiert, wenn beide Cores auf 50% laufen? Das heisst doch, dass nicht nur 1 Core genutzt wird, sondern beide. Ich denke hier könnte doch eine Limitierung durch irgendwas vorliegen und sei es nur der Compiler, der nicht weiter parellisieren kann

[Berni]

Die von dir beobachtete Auslastung liegt einfach nur am Scheduler des Betriebssystems und nicht an einer tatsächlichen Parallelisierung. Um Parallelisierung tatsächlich zu nutzen, muss man auch entsprechend multithreaded programmieren.

[Trap]

Mit OpenMP kann man das sehr einfach parallelisieren, aber das lohnt sich erst wenn man einen sinnvollen Algorithmus benutzt.

Je nachdem wieweit es genau sortiert ist würde ich entweder die Sortierung nutzen oder über Hashing vergleichen. Eine Hashfunktion von jedem 5er-Array auf ~10 bit Länge schreiben und nur 5er-Arrays mit gleicher Hash tatsächlich vergleichen.