Array zufällig abgrasen
-
Hallo,
also ich wusste jetzt nicht ob ich das lieber ins Mathematik forum schreiben sollte, aber da es C++ ist und hier auch fähige Leute lesen, mach ichs einfach mal
Also, ich habe ein bool array mit X einträgen.
Davon sind beliebig viele Einträge == true. Dies bedeutet, dass diese Einträge zur Verarbeitung genutzt werden (eigentlich schaue ich ob ein Eintrag true ist und verwende dann den Index).Nun, was ich machen möchte ist, die Einträge welche true sind, zufällig abtasten, anstatt linear durch das ganze Array zu gehen. Ganz wichtig dabei ist aber, dass ich alle true Einträge erwische. Dies soll jedoch basierend auf einer Anzahl (K) an Abgrasungen geschehen.
Ein Beispiel:
const int k = 200; bool* arr; //hat 120 Einträge, davon sind 75 Einträge trueso, jetzt möchte ich zufällig diese 75 Einträge finden. Wenn ich jeden einzelnen Eintrag durchgehe, dann komme ich auf 75 Weiterverarbeitungen. Aber es sollen 200 Weiterverarbeitungen geschehen. Heisst also, 1 "true" Eintrag kann auch mehrfach für eine Weiterverarbeitung genutzt werden.
Klar? Hoffentlich
Ja, und dafür bräuchte ich irgendwie eine Lösung. Das Problem liegt also darin, dass ich diese Einträge in zufälliger Reihenfolge benötige und ich trotzdem alle 75 "true" Einträge mindestens 1x zur Weiterverarbeitung verwenden muss (sofern k>=75 versteht sich)
Bin für jeden Tipp und Hilfe dankbar!
lg
Sam
-
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.
-
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.
Das ist erstmal eine gute Idee, danke dafür!
Aber das bedeutet natürlich dass ich erstens durch das komplette Array muss um die Indizes im vector zu speichern und dann noch mehrere Durchgänge des random_shuffle auf den vector. Da ich hier mit arraygrößen von 1.000.000 und mehr arbeite, kann das natürlich ganz schön performance killen.
Hätte ich erwähnen sollen. Gibt es einen schnelleren Weg?
Danke!
-
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.