Wer liefert schnellste version :) Vereinigung über int-arrays

Mati

Hallo,

ich arbeite gerade an einem algorithmus bei dem es vor allem um geschwindigkeit geht.
Ich habe eine stelle die durchaus 5000 mal angesprungen wird 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 schnellen 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
      }
   }

Also in dem Bitvector sind im Moment nur int werte - er wird zu begin (also vor den for-schleifen) mit 0 initialisiert.
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 verpflanzt habe die eben ein solches hat. (Kein Bock auf redesign)

Kommen alle möglichen int-Werte vor oder nur ein eingeschränkter Wertebereich? Das ist ja schonmal entscheidend dafür, ob ein Bitvektor geeignet ist.

megaweber

Wieso postet du das gleiche in verschiedenen Foren?

Mati

Kommen alle möglichen int-Werte vor oder nur ein eingeschränkter Wertebereich? Das ist ja schonmal entscheidend dafür, ob ein Bitvektor geeignet ist.

wie oben beschrieben: es sind alle möglichen int-werte möglich

Wieso postet du das gleiche in verschiedenen Foren?

Weil ich insbesondere vom Moderator rapso darauf aufmerksam gemacht worden bin es so zu tun.
Siehe Post #8 auf Seite 1 dort.

rüdiger

ne, nix Crosspost hier. Da hast du rapso falsch verstanden. Geht im alten Thread weiter..