Array zufällig abgrasen
-
Warum benutzt du nicht gleich einen Vector? Oder ein bitset?
mfg.
-
Nutze rand für den Zugriff und sieh zu das sich die Zufallswerte im indexbereich befinden
-
Gibt es einen schnelleren Weg?
Vermutlich eher nicht. Wenn du sichergehen willst, daß jeder Index mindestens einmal verwendet wird, bleibt dir schon mal nichts anderes übrig als das gesamte Array zu durchlaufen.
Und für das multiple random_shuffle wüßte ich auch keine vernünftige Alternative (ok, nach dem ersten Durchlauf brauchst du nicht unbedingt noch mal neu zu shufflen, einfach zufällig einen Index aus dem Index-Array herauspicken tut es auch).
Wenn du nicht durchmischen willst, muß du diejenigen Indizies, die schon verwendet wurden, markieren und diese Markierung dann bei zukünftigen Suchen beachten. Ich habe das jetzt nicht ausprobiert, aber auf den ersten Blick klingt mir das noch aufwändiger als random_shuffle.
-
joomoo schrieb:
Warum benutzt du nicht gleich einen Vector? Oder ein bitset?
mfg.
Weil ich das Array geschickt bekomme. Das Array wurde vom Hauptprogramm gefüllt und mir übergeben. Und damit muss ich arbeiten.
-
Knuddlbaer schrieb:
Nutze rand für den Zugriff und sieh zu das sich die Zufallswerte im indexbereich befinden
Aber woher habe ich die gewissheit, dass ich nicht 10000x rand aufrufen muss bis er einen geeigneten Index findet? Die Einträge sind nicht geordnet als true definiert.
Somit fällt das raus.
-
Z2 schrieb:
Gibt es einen schnelleren Weg?
Vermutlich eher nicht. Wenn du sichergehen willst, daß jeder Index mindestens einmal verwendet wird, bleibt dir schon mal nichts anderes übrig als das gesamte Array zu durchlaufen.
Und für das multiple random_shuffle wüßte ich auch keine vernünftige Alternative (ok, nach dem ersten Durchlauf brauchst du nicht unbedingt noch mal neu zu shufflen, einfach zufällig einen Index aus dem Index-Array herauspicken tut es auch).
Wenn du nicht durchmischen willst, muß du diejenigen Indizies, die schon verwendet wurden, markieren und diese Markierung dann bei zukünftigen Suchen beachten. Ich habe das jetzt nicht ausprobiert, aber auf den ersten Blick klingt mir das noch aufwändiger als random_shuffle.
Ok, vielen dank. Dann werde ich erstmal das random_shuffle nutzen. Mal schauen ob es performancemäßig noch vertretbar ist.
Bin natürlich für weitere Wege offen und dankbar!
-
Z2 schrieb:
Die Indizes mit true in einen std::vector packen, ein paar mal std::random_shuffle drauf loslassen. Dann der Reihe nach verwenden. Wenn du mit dem Vektor durch bist, einfach noch mal std::random_shuffle und wieder beim ersten Vektor-Eintrag anfangen.
und wenns nicht ganz so zufällig sein muß, kann man sich das indexarray sparen und nur zwei zahlen würfeln, einen startpunkt (start) und eine zur arraygröße teilerfremde zahl (step). und dann geht man mit
int i=start;do{tuwas(i);i=(i+step)%size}while(i!=start);
durch.
-
schließ einfach mehrfache überprüfung aus BIS alle trues gefunden werden, wenn du danach weitersuchen lassen willst kannst du die beschränkung ja ab da wieder auflösen
-
volkard schrieb:
und wenns nicht ganz so zufällig sein muß, kann man sich das indexarray sparen und nur zwei zahlen würfeln, einen startpunkt (start) und eine zur arraygröße teilerfremde zahl (step). und dann geht man mit
int i=start;do{tuwas(i);i=(i+step)%size}while(i!=start);
durch.oh, das ist eine gute idee (merk ich mir!) aber leider sollten sie schon sehr zufällig sein.
-
ä schrieb:
schließ einfach mehrfache überprüfung aus BIS alle trues gefunden werden, wenn du danach weitersuchen lassen willst kannst du die beschränkung ja ab da wieder auflösen
Hmm, wie meinst du das genau? Einfach immer indizes überspringen? Das bedeutet aber wieder dass ich nicht vorraussagen kann, wieviele Durchläufe nötig sind und das ist mir zu unsicher. Ich muss wissen, wie sich das Programm in der Performance verhält.