Vereinigung von int-Arrays: so schnell wie nur möglich

pumuckl

Ich hab mir da mal was aufgemalt

Voraussetzungen:
a) du kennst dei Anzahl der Arrays
b) die Arrays sind sortiert
c) du hast ein ein weiteres Array aus Pointern, die auf das jeweils erste Element der einzelnen Arrays zeigen
d) du kennst die Laenge der einzelnen Arrays

Wie dein Beispiel oben zeigt, ist die Laenge des ergebnis-arrays vorher nicht bekannt, daher verwende ich hier einfach einen stack.

unsigned int nArrays;
int* firstElem[nArrays];
unsigned int len[nArrays];

std::stack<int> erg;

Die Idee ist, eine Rekursion laufen zu lassen, Umsetzung wie folgt:

void push_elems_to_stack(int max, int arrnum)
{
  for ( ;arrnum < nArrays; arrnum++) //alle arrays mit nummer > arrnum
  { 
    while (len[arrnum] > 0) {
      int kleinstes = *firstElem[arrnum];
      //nur elemente > max im array uebrig, while abbrechen      
      if(kleinstes > max) break;  
      if(kleinstes < max) { 
         //kleineres Element gefunden ->Push und rekursion starten
         erg.push(kleinstes);
         push_elems_to_stack(kleinstes, arrnum+1);
      }
      // zeiger auf erstes elem eins vor, restlaenge verkleinern
      // auch fuer kleinste == max, da schon auf dem stack
      ++firstElem[arrnum]; 
      --len[arrnum]; 
    }
  }
}

Im Hauptprogramm dann nurnoch

push_elems_to_stack(std::numeric_limits<int>::max(), 0); //fange erstes array an, alle ints ins ergebnis

Ich hab leider keinen Compiler um das zu testen, mache aber ein kleines Beispiel (folgt gleich)

Mati

Die 4 Voraussetzungen von Pumuckl sind erfüllt - nur falls jemand fragen sollte

das snippet vom ersten post ist nicht von mir ....
Im grunde wird der bitvector benutzt um eine binärzahl zu bauen die an pos kommt und anhand derer dann geprüft werden kann ob eine Zahl schon mal verwendet wurde (btest!). Falls über UND 0 rauskommt dann nicht und die neue zahl wird übernommen, andernfalls weiterschalten.

das mit den Modulo 32 und shift von 5 verstehe ich auch nicht so ganz...evtl. wegen den int-werten um keinen overflow zu kriegen? in der hinsicht weiß ichs noch nicht...

pumuckl

nehmen wir an, die Arras sehen wie folgt aus:

arr0: 2 4 8
arr1: 3 6 7 8
arr2: 0 1 4 6
arr3: 1 3 7

Stack: {}

als erstes wird 2 auf den stack gepusht, und die rekursion mit push_elems_to_stack(max = 2, arrnum = 1) aufgerufen, also wird als naechstes arr1 getestet.
ich nehme den advance des pointers schonmal vorweg, da er gleich nach der rueckkehr der rekursion erfolgt. die uebrigen arrtays sehen jetzt etwa so aus:

arr0:   4 8
arr1: 3 6 7 8
arr2: 0 1 4 6
arr3: 1 3 7

Stack: {2}

die 3 ist groesser als 2, break wird aufgerufen und arr2 getestet. 0<2, also naechste rekursion. da nichts kleiner oder gleich 0 ist, kehrt diese nach pruefung des ersten elems von arr3 zurueck und der pointer wird vorgeschoben:

arr0:   4 8
arr1: 3 6 7 8
arr2:   1 4 6
arr3: 1 3 7

Stack: {2, 0}

while geht weiter, 1<2, also push(1) und push_elems_to_stack(max = 1, arr = 3).
Da das erste Element von arr3 == 1 wird einfach ignoriert, der pointer advanced und die rekursion kehrt zurueck. nach dem advance in arr2 siehts so aus:

arr0:   4 8
arr1: 3 6 7 8
arr2:     4 6
arr3:   3 7

Stack: {2, 0, 1}

Da die 4 in arr2 groesser ist als 2(wir befinden uns wieder im ersten rekursionsaufruf) gehts weiter zu arr3 und direkt danach kerhrt auch diese rekursion zurueck (denn 3>2) und wir landen wieder in arr0. => push(4)

arr0:     8
arr1: 3 6 7 8
arr2:     4 6
arr3:   3 7

Stack: {2, 0, 1, 4}

Das spiel geht jetzt so weiter. fuer die 3 gehts nochmal eine rekursion zurueck und so weiter.
Am ende sieht der Stack so aus:

Stack: {2, 0, 1, 4, 3, 8, 6, 7}

Zur Komplexitaet kann ich nicht so viel sagen, nur dass die Funktion fuer N verschiedene Zahlen im Ergebnisarray genau N+1 mal aufgerufen wird: zu jedem der N pushes ein Aufruf und der urspruengliche Aufruf.
Du kannst auch ohne Probleme aus deinen sortierten Arrays alle Zahlen kleiner als x rausholen indem du statt numeric_limits::max x angibst.

Mati

danke schon mal an dieser stelle pumuckl....ich bin gerade dabei deinen code zu verstehen

Also wenn das gegebene Programm das macht, was ich denke, dann wird es nicht viel schneller gehen. Was mich stört ist diese Aussage.

Mati schrieb:

//der bitvector ist so groß wie das grösste array! Kann als gegeben
//vorausgesetzt werden

Wenn das großte Array nur 4 Felder groß wäre und bitvec dann auch, wie soll sich dann pos so berechnen lassen?
pos = ptr >> log_nbits_of_int;
Das wäre schnell mehr als 4. Wie groß ist den bitvector?

Mati

ah deswegen das 18 Bit.
ja bei einem wert von 1e+18 krachts. Mit 17 gehts noch....

ich bin auch am rumüberlegen jetzt....aber so stehts da wirklich....

also bitte um bestätigung: ein unsigned int - damit kann ich doch 2^32 darstellen oder?

wäre ja viel grösser als 2^18

EDIT: Es kracht an einer anderen stelle....jetzt bin ich verwirrt.

Ne, die 18 war nur ein Beispiel.

Wie groß ist den nun bitvec?

Mati

jetzt glaube ich hab ichs:

also die zahlen die in den arrays auftreten sind immer kleiner als bitvec. D.h bitvec ist so groß wie die grösste Zahl die in den arrays auftreten kann.

Jetzt müsste es passen.

Weiss ja nicht. Vielleicht stehe ich ja auf'n Schlauch.

Wurde hier doch auch schon vorgeschlagen.
Was spricht hier gegen ein einfaches:

set<int> Result;
set_union(vec1.begin(), vec1.end(),vec2.begin(), vec2.end(),inserter(Result,Result.begin()));

Wenn das bitvec array kleiner ist, als die anderen arrays zusammen, dann kannst du versuchen den btest und das wert im erg_arr speichern weg lassen.

//weg  if (! btest( bitvec[pos], bit )) {
        setbit( &bitvec[pos], bit );
//weg    //speichere wert in nächster stelle in erg_arr

nur am schluss das ganze bitvec array durchlaufen und die gesetzten werte ins erg_arr eintragen.

CaramelLord schrieb:

Wenn das bitvec array kleiner ist, als die anderen arrays zusammen, dann kannst du versuchen den btest und das wert im erg_arr speichern weg lassen.
//weg  if (! btest( bitvec[pos], bit )) {
        setbit( &bitvec[pos], bit );
//weg    //speichere wert in nächster stelle in erg_arr
nur am schluss das ganze bitvec array durchlaufen und die gesetzten werte ins erg_arr eintragen.

Oder den ganzen Blödsinn lassen und das set_union nehmen...

Ich wette jetzt mal 1000€ das set_union viel langsamer ist, wenn du damit 1000 Array vereinigen willst.

Ich erhöhe auf 2000€ das set_union schneller ist.