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

Mati

Hallo,

ich arbeite gerade an einem algorithmus bei dem es vor allem um geschwindigkeit geht.
Ich habe eine stelle an der ich z.B 10 oder aber auch 1000 arrays habe die mit int-werten gefüllt sind.
Es geht jetzt darum ein einziges ergebnisarray zu haben das die vereinigung aller ist sozusagen.

ein Beispiel:

arr1 = {2,4}
arr2 = {1,2,4}
arr3 = {5}

erg_arr = {1,2,4,5}

Hört sich nach ner einfachen aufgabe an - man kann es aber bestimmt mit Bitshifts und schnelle bit-operationen hinbekommen.
Ich hab schon eine variante hier die aber bestimmt noch schneller geht:

Ach ja: Bitte nicht stören lassen an den macros - die kommen natürlich weg

#define setbit(ptr,bit)  ((*ptr) |= (1 << (bit)))
#define btest(word,bit)  ((word) & (1 << (bit)))

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

  for (//laufe über anzahl arrays) {

	//hole erstes array
        //Länge des arrays ist über eine variable zugänglich also 
       //schon gegeben = len

    for (j=0; j<len; j++) {
      ptr = arr[j]; //erster  
      pos = ptr >> log_nbits_of_int; // log_nbits_of_int = 5;
      bit = ptr % nbits_of_int;           //nbits_of_int = 32;
      if (! btest( bitvec[pos], bit )) { 
		setbit( &bitvec[pos], bit ); 
		//speichere wert in nächster stelle in erg_arr
      }
   }

was ist in dem bitvector?
ist da das 18te bit gesetzt, wenn eine 18 dabei ist?

Krux

Ich denke, dass die einfachste Lösung auch die schnellste ist. Alle größen addieren, und mit hilfe der so errechneten größe ein neues array anlegen, und dies dann mit den Daten füllen. Wiso ist die geschwindigkeit dennn so wichtig?

Undertaker

sind die ausgangs-array sortiert?
sollen das ergebnis-array sortiert sein?
hast du einen begrenzten wertebereich, oder ist jeder int-wert erlaubt?
vielleicht wäre es das beste (wenn's schnell sein soll) auf das vereinigen zu verzichten und stattdessen eine spezielle zugriffsfunktion zu basteln.

Checker*amp*Murckser

Also wenn das Ergebnis sortiert sein soll, dann würde ich die beiden Ausgangsarrays einfach in n std::set schmeißen.
Und wenn das Ding danach schnell zu handhaben sein soll, dann würde ich das std::set in nen vector übertragen ...

HumeSikkins

Checker&Murckser schrieb:

Also wenn das Ergebnis sortiert sein soll, dann würde ich die beiden Ausgangsarrays einfach in n std::set schmeißen.
Und wenn das Ding danach schnell zu handhaben sein soll, dann würde ich das std::set in nen vector übertragen ...

Also wenn man schon die Standardmittel verwendet, dann würde ich statt
einem vector -> set -> vector, doch eher ein sort, sort, set_union, oder, falls es nicht es nicht allzu viele Duplikate gibt, ein sort + unique vorschlagen.

Mati

was ist in dem bitvector?
ist da das 18te bit gesetzt, wenn eine 18 dabei ist?

Also in dem Bitvector sind im Moment nur int werte - er wird zu begin (also vor den for-schleifen) mit 0 initialisiert.
Das mit dem 18Bit verstehe ich leider (noch) nicht. wie wenn eine 18 dabei ist?
Der Bitvector ist C-artig so angelegt:

memset(bitvec, 0, n * sizeof(unsigned int));

Alle größen addieren, und mit hilfe der so errechneten größe ein neues array anlegen, und dies dann mit den Daten füllen. Wiso ist die geschwindigkeit dennn so wichtig?

eh....das verstehe ich leider auch nicht -was meinst du mit alle größen addieren und dann ein erg-array anlegen?
Es gilt einen referenz-algorithmus zu schlagen der das eben so macht...an dieser stelle wird sehr viel rechenzeit insgesamt verbraten ....er läuft durchaus 1000 mal an diese stelle und kann dann durchauch 1000 arrays mit jeweils 500 elementen oder mehr haben. Es geht insgesamt um performance...

sind die ausgangs-array sortiert?
sollen das ergebnis-array sortiert sein?
hast du einen begrenzten wertebereich, oder ist jeder int-wert erlaubt?

Sorry - das hatte ich vergessen zu sagen
JA- die ausgangs-arrays sind sortiert.
das ergebnisarray muss nicht unbedingt sortiert sein - könnte ja in nem darauffolgenden schritt sortieren - aber wenns schon gleichzeitig geht dann JA. ich werde eine sortierung wohl brauchen.
der wertebereich ist nicht begrenzt. jeder int-wert ist erlaubt.

Ich würde gerne am ende ein "stinknormales" array haben. Also ein int* arr .
Der Grund dafür ist, dass ich das in ne Datenstruktur verplanzt habe die eben ein solches hat. (Kein Bock auf redesign)

Danke euch vielmals

rapso

mach es so wie manch andere auch und lass dir die aufgabe einfach loesen indem du es als contest machst

Mati schrieb:

for (j=0; j<len; j++) {
      ptr = arr[j]; //erster  
      pos = ptr >> log_nbits_of_int; // log_nbits_of_int = 5;
      bit = ptr % nbits_of_int;           //nbits_of_int = 32;
      if (! btest( bitvec[pos], bit )) { 
		setbit( &bitvec[pos], bit ); 
		//speichere wert in nächster stelle in erg_arr
      }
   }

Was macht das?

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.