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

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.