Algorithmus gesucht: Vergleich großer Anzahl von int-Arrays

Miq

Hi,

ich habe mal wieder ein Optimierungsproblem...

Ich habe eine große Anzahl von int-Vektoren, die ich nach einem Schema alle miteinander vergleichen muss:
[*]Wenn die Elemente mit gleichem Index von zwei Vektoren gleich sind, erhalten beide Vektoren einen Wertungspunkt.

Beispiel:

Vektor A[4] = (1,2,3,4)
Vektor B[4] = (1,3,2,4)
Vektor C[4] = (1,3,2,2)

Die plain-vanilla-Lösung sähe so aus (sorry, Pseudocode - das wird knapper als C++ ):

Zaehler[C] = 0
loop v über A..B
   Zaehler[v]=0
   loop w über v+1..C
      loop i über 0..3
         if v[i]==w[i]
            Zaehler[v]++
            Zaehler[w]++
         fi
      endloop
   endloop
endloop

Damit ist am Ende

Zaehler[A]=3
Zaehler[B]=5
Zaehler[C]=4

Bei >20000 Vektoren mit jeweils >1000 Indizes sind das natürlich eine Menge Vergleiche, die teilweise unnötig sind. Wenn z.B. A[0] und B[0] schon gleich sind, sind beim Vergleich von A[0] und C[0] schon alle Fakten bekannt, um die Bewertungen von A, B und C sofort auf 3 zu setzen; der spätere Vergleich von B[0] und C[0] ist unnötig.
Wie kann ich das effizient programmieren? Eine Idee, die ich hatte: Alle unterschiedlichen Werte eines einzelnen Index quer über alle Vektoren in einem Hash speichern, bei Duplikaten einfach hochzählen. Dann kann man einen abschließenden Lauf linear über alle Vektoren machen und die Bewertung jeweils um das Zählergebnis aus dem Hash erhöhen. Aber: ist das wirklich schneller? Die Hashzugriffe kosten ja auch wieder Ausführungszeit...

volkard

Miq schrieb:

Bei >20000 Vektoren mit jeweils >1000 Indizes sind das natürlich eine Menge Vergleiche

mal schauen, wieviele.
sagen wir ertstmal, genau 20000 arrays und genau 1000 indizes.
da du jeses array mit jedem vergleichst, sinds ca 20000^2/2 arrayvergleiche mit je 1000 elementvergleichen, macht 200Mrd elementvergleiche.
also weniger als ne stunde. geht ja noch.

greifen wir mal den quadratischen anteil an, der kommt von "jedes array mit jedem array".

Wenn z.B. A[0] und B[0] schon gleich sind, sind beim Vergleich von A[0] und C[0] schon alle Fakten bekannt, um die Bewertungen von A, B und C sofort auf 3 zu setzen; der spätere Vergleich von B[0] und C[0] ist unnötig.

oh, machste ja schon.

Wie kann ich das effizient programmieren? Eine Idee, die ich hatte: Alle unterschiedlichen Werte eines einzelnen Index quer über alle Vektoren in einem Hash speichern, bei Duplikaten einfach hochzählen. Dann kann man einen abschließenden Lauf linear über alle Vektoren machen und die Bewertung jeweils um das Zählergebnis aus dem Hash erhöhen. Aber: ist das wirklich schneller? Die Hashzugriffe kosten ja auch wieder Ausführungszeit...

for die hashtable wählste als hashfunktion eine unsigned-plutimikation mit einer irrationalen konstanten ( mal 2^32 ). das sind 50 takte auf meinem prozessor. noch ein wenig hashtable-zeugs, 100 takte. und dein plaun vergleich wär 1 takt gewesen.
nu brauchste also 100-mal länger pro vergleich aber mußt 10000-mal weniger vergleichen. faktor 100 gewonnen.

sieht aber immernoch gut optimierungsbedürftig aus.

nö, eigentlich nicht.
sagen wir immernoch, genau 20000 arrays und genau 1000 indizes.
kannst auch statt durchzurasen und alles zu haschen und nochmal zu rasen und zu zählen, dir
-im ersten schritt die 20000 zahlen mit zugehörigem index in ein lokales array kopieren.
-> 20000 schritte
- im zweiten schritt das lokale sortieren.
-> 300000 schritte
- dann linar durchgehen und hochzählen und unique machen.
-> 20000 schritte.
sind nur 0,3Mrd schritte.

könnte ne alternative für kleine datenmengen sein. das sortieren hat O(n*log(n)) zeitbedarf, wenn es sehr viele array werden, isses irgendwann lahmer als beliebig langsames aber konstantes hashen. und für's hashen hab ich sehr teuer abgeschätzt. das geht vermutlich auch sehr gut ohne plutimikation mit ein paar shifts (wobei ich lieber annehme, daß moderne prozessoren sauschnell plutimizieren können) und die weiteren hashtable-sachen sind doch recht billig.

Hi,

ich hab noch einen Vorschlag, der allerdings auch ineffizient sein kann.
Hab mir das sooo genau nicht überlegt. Insbesondere verschweigst du, wie
wahrscheinlich es ist, dass zwei Werte gleich sind.

Nimm doch zwei Vektoren V1, V2 mit Zeigern auf die Vektoren.
V1 wird mit allen gefüllt, V2 ist erst leer. Dann so:

Schleife des Index durchgehen. Wert gleich ? dann in V1 löschen und in
V2 einfügen. Anschliessend noch den Startvektor nach V2.

Das solange, bis V1 leer ist und mit dem nächsten Index das gleiche von V2 nach V1.

Wie gesagt, kann totaler Schrott sein, aber wenn viele Werte gleich sind,
dann ist das glaube ich ganz gut.

Jockel

Miq

@Jockelx:
Das klingt interessant, ich verstehe es aber nicht ganz. Ich habe also in V1 anfänglich die Zeiger auf alle 20.000 Vektoren. Wenn ich bei meiner Vergleichsschleife zwei finde, die an dem Index identisch sind, fliegt das Duplikat aus V1 'raus, so dass ich mit dem nächsten Vektor schonmal einen weniger checken muss. Soweit verstanden - finde ich auch eine gute Idee. Ich muss nur einen Duplikatzähler mitführen, der mir die Anzahl der Treffer pro Index behält. Dann habe ich am Ende in V1 nur noch die Vektoren stehen, die entweder einzigartig an diesem Index sind, oder die die ersten mit einem Wert sind - alle Duplikate sind ja weg.
Wie verpasse ich jetzt aber allen Duplikaten den Wert, der beim verbliebenen ersten Vektor in V1 steht? Da müsste ich doch auch so eine Art verkettete Liste der Duplikate pflegen, oder?
Ganz aussetzen tut's bei mir dann mit der Fortsetzung: Wozu muss ich den Rest dann nach V2 kopieren? Eigentlich müsste ich doch für den nächsten Index wieder alle Vektoren in V1 schreiben und das ganze mit den Werten am neuen Index wiederholen, oder? Oder meinst Du, da ja die Duplikate eh' schon alle in V2 stehen, braucht man nur noch die Unikate dazu setzen, und hat wieder einen kompletten Satz, und das, ohne 20.000 Adressen schreiben zu müssen?

Ich mach mal dein Beispiel:

Vektor A[4] = (1,2,3,4)
Vektor B[4] = (1,3,2,4)
Vektor C[4] = (1,3,2,2)

V1 = {A,B,C}, V2 = {}

index = 0:
V1_A[0] == V1_B[0] ?
Ja => V1 -= B, V2 += B
V1_A[0] == V1_C[0] ?
Ja => V1 -= C, V2 += C
Ende der Schleife:
V1 -= A, V2 += A.

Nächster Durchlauf, gibt's aber nicht, da V1 leer, also
weiter mit Index 1:

V2_A[1] == V2_B[1] ?
Nein, also weiter
V2_A[1] == V2_C[1] ?
Nein, also weiter, durchlauf zuende
=> V2 -= A, V1 += A

V2_B[1] == V2_C[1] ?
Ja, V2 -= C, V1 += C
Ende der Schleife:
V2 -= B, V1 += B

Nächster Durchlauf, gibt's aber nicht, da V2 leer, also
weiter mit Index 2...

Das mit dem Wert erhöhen sollte doch kein Problem sein.
Wird ein Treffer gefunden, dann wird der Wert des zu kopierenden Elements
erhöht und mit einem bool merkst du dir, das das Ausgangselement
nach Abarbeitung auch erhöht werden muss.

Jockel

Miq

Ah, Danke!

Das probiere ich mal aus, ich denke, das könnte gut laufen. Ich habe zwischenzeitlich mal gecheckt: es sind meist ca. 50% der Werte eines Index gleich, also verringert sich mit Deiner Methode die Anzahl der Durchläufe dramatisch.

volkard

Jockelx schrieb:

Wie gesagt, kann totaler Schrott sein, aber wenn viele Werte gleich sind, dann ist das glaube ich ganz gut.

kann sogar ein wenig schrottig sein, wenn 50% der werte eine 1 sind und die anderen 50% gleichverteilt.
aber bei ner kleinen wertemenge isses fein. bei nur 10 verschiedenen zahlen haste nicht mehr als 10 durchgänge.

sagen wir ertstmal, genau 20000 arrays und genau 1000 indizes.
dein verfahren braucht dann höchstens 20000*1000*abs(wertemenge) schritte.
ein bißchen weniger, weil während des laufens über einen index die menge der arrays abnimmt. bei gleichverteilten werten wohl
20000*500*abs(wertemenge) schritte.
bei ungleichverteilten vermutlich noch besser, das kann ich schlecht abschätzen.

macht bei nur 100 werten vielleicht
20000*500*100 == 1Mrd schritte

was würde statt der hashtable eine std::map kosten bei nur 100 weren?
ein suchzugriff auf den binärbaum macht 7 schritte
20000*1000*7*2 == 0,28Mrd schritte

und es wäre stabiler gegen doch mal mehr verschiedene werte, weils nur mit log(abs(wertemenge)) hochgeht.

edit: du hast vermutlich doch nur 0,25Mrd schritte wegen der erhöhten wahrscheinlichkeit früh einen häufig vertretenen wert zu finden. vielleicht sogar viel weniger schritte, wenn die daten ausreichend schief liegen.

dein verfahren ließe sich fein mit sowas wie ner killer-heuristik aufmotzen. für den nächsten index werden zuerst die arrays genommen, die den häufigsten wert hatten, in der hoffnung, daß man beim nächsten durchlauf deswegen zufällig wieder früh einen wert findet, der häufig vorkommt. na, andererseits ist eh schon der fall, daß gute arrays wahrscheinlicher kommen, die heuristik würde nur noch verstärken (falls diese abhängigkeit überhaupt in den daten vorliegt, weiß ich ja nicht).

andererseits lassen sich beim baum auch modifizierungen machen, die bei schiefen wahrscheinlichkeiten mehr performanche bringen. bei ganz schiefen move-to-front-lists, sonst spreizbäume? oder einfach nur einen einelementigen cache vor dem baum.

Miq: Du solltest jetzt Laufzeiten im Sekundenbereich haben. Wenn die noch nicht genug sind, müßest Du mehr über die Zahlen sagen, da Spezialanfertigungen wie Jockelx' Verfahren für ungleichverteilte Wertemengen oft genug jedes allgemeine Verfahren abhängen können.

Miq

@volkard:
Danke schön für Deine Analyse. Sie bestärkt mich darin, es mit Jockelx' Verfahren zu probieren, denn ich habe inzwischen ein bisschen Statistik betrieben: bei manchen Indizes gibt es nur einstellig viele unterschiedliche Werte, was die Performance massiv fördert. Ich hatte allerdings auch schon pathologische Fälle á la "20.000 Werte, alle verschieden". Kommt zum Glück aber eher selten vor.
Endgültig kann ich das erst am WE ausprobieren, bis dahin muss ich noch ein wenig für meinen Arbeitgeber schaffen

volkard

Miq schrieb:

@volkard:
Danke schön für Deine Analyse.

die war nicht ganz richtig.
mindestens wird für jeden index das erste array mit jedem anderen verglichen, was mindestens 20000*1000*1 macht. denken wir und 10 gleichverteilte werte, isses bei
20000*1000*10
die map-version war angenommen mit
20000*1000*4*2 wobei das *2 davon kommt, daß man pro index einmal durchrennt um zu zählen und dann nochmal um einzutragen.
wird natürlich ne map, die als wert ne liste hat, wo die arrays eingetragen werden und dann braucht man nur einen durchlauf.
20000*1000*4

kurzum: ich glaube nicht an jockelx' version. kann es nicht genau begründen, aber sie fühlt sich irgendwie schmutzig an, und deine version war von anfang an gut (hashtable durch map ersetzen und nur ein durchlauf sind nur detailverbesserungen).

verfahren sind aber zu dicht aneinander, um abzuschätzen, welches schneller ist. tut das eine den chache besser ausnutzen, gewinnt es. tut das andere oft den operatore new aufrufen, verliert es (drauf achten, und nicht std::list nehmen, vielleicht ne eigene implemetierung oder std::queue (zu viel speicher), vielleicht ne intrisive list oder std::list mit allocator. nö, einfach nen vector).

wenn du jockelx' version testest, tu mir den gefallen, und teste die version mit der map ebenfalls.

Miq

Ich konnte doch die Finger nicht davon lassen...

Dieser Code hier implementiert Jockelx' Idee in meinem Programm:

//    Neuer Versuch mit Metrik...
      memset(metrik,0,POPSIZE*sizeof(add *));
      unsigned int maxmetrik = 0;
      unsigned int zaehlen = 0;
      for(i=0;i<POPSIZE;++i)
      {
         if(pop[i]->IsDupe()) continue;
         metrik[maxmetrik++] = pop[i];
      }
      for(i=0;i<add::CODESIZE();++i)
      {
         memcpy(metrik2,metrik,maxmetrik*sizeof(add *));
         for(j=0;j<maxmetrik-1;++j)
         {
            if(!metrik2[j]) continue;
            unsigned int c = metrik2[j]->Cmd(i);
            for(k=j+1;k<maxmetrik;++k)
            {
               if(!metrik2[k]) continue;
               zaehlen++;
               if(metrik2[k]->Cmd(i)==c)
               {
                  metrik2[j] = 0;
                  metrik2[k] = 0;
               }
            }
         }
         for(j=0;j<maxmetrik;++j)
         {
            if(metrik2[j])
            {
               metrik2[j]->SetMetrik(metrik2[j]->Metrik()+1);
            }
         }
      }
cout << "Metrik: " << zaehlen << " Vergleiche." << endl;

Mit einem "kleinen" Testsatz von 15.000 pop-Vektoren á 20 Cmd-Elementen wäre der brute-force-Ansatz auf 15.000*14.999*20=knapp 4,5 Mrd. Vergleiche gekommen. Die Variante oben pendelt so zwischen 5 und 7 Mio. - Faktor 800-1000 gewonnen!

Danke schön nochmal.