Gewichtete zufällige Auswahl

[phanty]

die aufgabenstellung ist extrem einfach: ich möchte aus einem array ein element zufällig auswählen. der haken daran ist, dass jedes element eine andere gewichtung hat, sprich eine grössere oder kleinere chance hat ausgewählt zu werden.

bsp:
array[1] : 20.00% chance ausgewählt zu werden
array[2] : 10.00% chance ausgewählt zu werden
array[3] : 43.49% chance ausgewählt zu werden
array[4] : 26.51% chance ausgewählt zu werden

eine einfache lösung wäre jetzt zb. dass ich ein temporäres array mit einer grösse von 10000 elementen mache und das primäre array prozentual in das temporäre verteile. dann könnte ich einfach eine randomzahl von 1 bis 10000 generieren lassen und fertig.
das problem ist jedoch, dass diese lösung 1. extrem unschön ist und 2. für meine anwendung nicht möglich ist, da mein array nicht nur aus 4, sondern aus 100k elementen besteht. das würde den speicher sprengen. ;)

die richtige lösung ist vermutlich einfach, aber ich hab irgendwie grad ein blackout und komm nicht drauf.
kann mir da wer helfen? wäre ich wirklich sehr dankbar!

[Texter mit x]

Man könnte für jedes Element einen Zufallswert bestimmen (für alle Elemente innerhalb der gleichen Grenzen) und diesen Wert mit dem Prozentsatz des Elementes multiplizieren. Das Element mit dem höchsten Wert gewinnt.

[phanty]

Man könnte für jedes Element einen Zufallswert bestimmen (für alle Elemente innerhalb der gleichen Grenzen) und diesen Wert mit dem Prozentsatz des Elementes multiplizieren. Das Element mit dem höchsten Wert gewinnt.

eine schöne idee, aber leider nicht machbar bei einem 100k-array.
ich müsste mit sowenig "befehlen/taktzyklen" wie möglich zum ziel gelangen.

[Texter mit x]

»» Man könnte für jedes Element einen Zufallswert bestimmen (für alle Elemente innerhalb der gleichen Grenzen) und diesen Wert mit dem Prozentsatz des Elementes multiplizieren. Das Element mit dem höchsten Wert gewinnt.

eine schöne idee, aber leider nicht machbar bei einem 100k-array.
ich müsste mit sowenig "befehlen/taktzyklen" wie möglich zum ziel gelangen.

Du wirst nicht drumherumkommen für jedes Element den Prozentsatz zu berücksichtigen und eine Multiplikation ist eine relativ sparsame Operation.

Sparsamer könnte es mit einer anderen Datenbasis gehen. Wenn es nur eine begrenzte Anzahl an Wahrscheinlichkeiten gibt und alles Elemente mit der selben Wahrscheinlichkeit in einem Array stehen, könnte man anhand der Wahrscheinlichkeiten und der Anzahl der Elemente in den Array eine Zufallsauswahl treffen, aus welchem Array ein Element, wiederum per Zufall, entnommen wird.

[phanty]

Du wirst nicht drumherumkommen für jedes Element den Prozentsatz zu berücksichtigen und eine Multiplikation ist eine relativ sparsame Operation.

ich müsste also multiplizieren und jedes element noch mit dem höchsten wert vergelichen. die grundliegende idee gefällt mir zwar, aber nicht für diese aufgabenstellung. da wöre die lösung mit nur vergleichen von den anderen beiden antworten schneller.

Sparsamer könnte es mit einer anderen Datenbasis gehen. Wenn es nur eine begrenzte Anzahl an Wahrscheinlichkeiten gibt und alles Elemente mit der selben Wahrscheinlichkeit in einem Array stehen, könnte man anhand der Wahrscheinlichkeiten und der Anzahl der Elemente in den Array eine Zufallsauswahl treffen, aus welchem Array ein Element, wiederum per Zufall, entnommen wird.

verschiedene gruppen, auch das ist eine sehr gute idee. ist zwar etwas aufwand, lohnt sich aber sicher.
wenn keine bessere lösung mehr kommt, werde das wohl machen.
danke dir.

[JürgenB]

Hallo phanty,

so habe ich es mal gemacht:

bsp:
array[1] : 20.00% chance ausgewählt zu werden
array[2] : 10.00% chance ausgewählt zu werden
array[3] : 43.49% chance ausgewählt zu werden
array[4] : 26.51% chance ausgewählt zu werden

erzeuge eine gleich verteilte Zufallszahl Z zwischen 0 und 10000 und wähle

Z <= 2000  -> 1
2000 < Z <= 3000  -> 1
3000 < Z <= 7349  -> 3
7349 < Z          -> 4

Gruß, Jürgen

[phanty]

Z <= 2000  -> 1
2000 < Z <= 3000  -> 2
3000 < Z <= 7349  -> 3
7349 < Z          -> 4

danke dir.
da es die selbe idee wie bei Hopsel ist, kannst du dort meine antwort lesen. ;)

[JürgenB]

Hallo phanty,

da es die selbe idee wie bei Hopsel ist, kannst du dort meine antwort lesen. ;)

hab ich schon. Such mal nach "gewichtete Zufallszahl". Vielleicht ist ja was dabei.

Gruß, Jürgen

[Hopsel]

Hi phanty!

array[1] : 20.00% chance ausgewählt zu werden
array[2] : 10.00% chance ausgewählt zu werden
array[3] : 43.49% chance ausgewählt zu werden
array[4] : 26.51% chance ausgewählt zu werden
kann mir da wer helfen? wäre ich wirklich sehr dankbar!

│  1  │2 │    3    │  4   │
├─────┼──┼─────────┼──────┤
0     20 30        73.49  100
│     │  │         │      │
├─20──┼10┼──43.49──┼26.51─┤

Eine beliebige Zahl zwischen 0 und 10000 geteilt durch 100 gibt dir ein Zahl, mit der du Anhand der Intervallgrenzen (mittlere Zeile) deinen Eintrag ermittelst.

MfG H☼psel

[phanty]

│  1  │2 │    3    │  4   │
├─────┼──┼─────────┼──────┤
0     20 30        73.49  100
│     │  │         │      │
├─20──┼10┼──43.49──┼26.51─┤

Eine beliebige Zahl zwischen 0 und 10000 geteilt durch 100 gibt dir ein Zahl, mit der du Anhand der Intervallgrenzen (mittlere Zeile) deinen Eintrag ermittelst.

und programmiertechnisch würd ich dann in einer schleifen durch das array gehen und schauen ob die zufallszahl zum element passt, oder?
bei einem array mit grösse 4 ist das kein problem, aber wie mach ich das mit einem array von 100k. jedes mal eine 100k schleifen durchrasseln lassen ist nicht gerade schön. ^^

[Hopsel]

Hi phanty!

und programmiertechnisch würd ich dann in einer schleifen durch das array gehen und schauen ob die zufallszahl zum element passt, oder?

Im Prinzip ja.

bei einem array mit grösse 4 ist das kein problem, aber wie mach ich das mit einem array von 100k. jedes mal eine 100k schleifen durchrasseln lassen ist nicht gerade schön. ^^

Optimierung ist aber nicht für lau zu bekommen, sondern erfordert erhöhten Verwaltungsaufwand.

Mein Vorschlag:
Baue das Array sortiert nach den Wahrscheinlichkeiten auf, wobei du zu jedem Element die Wahrscheinlichkeitssumme bis zu diesem Element mit abspeicherst (deshalb hatte ich die mittlere Zeile angegeben).
Mit der binären Suche findest du dein gewünschtes Element in höchstens 17 Schritten.

MfG H☼psel

[phanty]

Mein Vorschlag:
Baue das Array sortiert nach den Wahrscheinlichkeiten auf, wobei du zu jedem Element die Wahrscheinlichkeitssumme bis zu diesem Element mit abspeicherst (deshalb hatte ich die mittlere Zeile angegeben).
Mit der binären Suche findest du dein gewünschtes Element in höchstens 17 Schritten.

an die heapsortierung habe ich auch schon gedacht. damit hab ich sogar schon erfahrung gesammelt (dank dem A*-Algorithmus ^^).

muss diese lösung mal der gruppen-lösung gegenüberstellen...
das waren auf jeden fall gute inputs, die ich da bekommen habe.
danke dir.

[peterS.]

gruss phanty,

hunderttausend eintraege ist schon eine ganze menge.

die gewichtung solltest Du, falls es Dir moeglich ist,
in diesem fall schon serverseitig festlegen, indem Du
die anzahl eines jeden eintrags seiner haeufigkeit
entsprechend vermehrst.
dann einmal gut durchmischen - die groesse deines
arrays duerfte jetzt  bei mehreren 100k eintraegen
liegen. deshalb darfst Du es jetzt in 50 bis 100
einzelne arrays zerlegen.

clientseitig waere dann ein kinderspiel - die erste
ziehung ermittelt genau das array, aus dem im zweiten
schritt die richtige ziehung erfolgt.

wir behelfen uns also mit dem trick eines intervalls
ueber eine moeglichst ideal gemischte menge.
die bewertung ueber die zulaessigkeit dieses kniffs
muss ich allerdings den statistik-experten ueberlassen.

waeren die tatsaechliche struktur und die art Deiner
eintraege bekannt, liessen sich auch aussagen ueber
moeglichkeiten zur optimierung der geschwindigkeit
und gegebenenfalls sogar zu einer rein clientseitigen
implementierung treffen.

so long - peterS. - [e-mail]

[phanty]

danke für die antwort.

die gewichtung solltest Du, falls es Dir moeglich ist,
in diesem fall schon serverseitig festlegen, indem Du
die anzahl eines jeden eintrags seiner haeufigkeit
entsprechend vermehrst.
dann einmal gut durchmischen - die groesse deines
arrays duerfte jetzt  bei mehreren 100k eintraegen
liegen. deshalb darfst Du es jetzt in 50 bis 100
einzelne arrays zerlegen.

ich bin mir nicht sicher ob ich das richtig verstanden habe, aber ist das nicht genau die lösung die ich vorgeschlagen habe und gesagt habe dass sie nicht so gut ist wegen der datenmenge?
das problem ist ja, wenn ein eintrag 50% chance hat und ein eintrag 0.01% chance hat ausgewählt zu werden, wären das nicht mehrer 100k, sondern 500m einträge. :(

clientseitig waere dann ein kinderspiel - die erste
ziehung ermittelt genau das array, aus dem im zweiten
schritt die richtige ziehung erfolgt.

um ehrlich zu sein, das läuft alles auf dem server. ist also kein javascript, sondern eine hintergrundverarbeitung. ;)

[peterS.]

hallo again phanty,

... wenn ein eintrag 50 % chance hat und ein eintrag 0.01 % chance hat
ausgewählt zu werden, wären das nicht mehrer 100k, sondern 500m einträge
...

ich glaub', da liegst Du um den faktor 100 daneben - 5 millionen kaemen
aber auf basis der von Dir geschilderten ausgangslage (500.000 voneinander
verschiedene eintraege) schon zusammen.

gegeben seien die eintraege "foo" mit einer gewichtung von 0.01 sowie
"bar" mit einer gewichtung von 50.
der von mir vorgeschlagene ansatz kaeme auf eine loesung mit insgesamt
10.000 eintraegen bei einmaligem vorkommen von "foo" und genau 5.000
eintragen von "bar" - 4.999 eintraege liegen jetzt erstmal brach.

schon bei 100.000 voneinander verschiedenen eintragen laege die ideale
natuerliche gewichtung jedes einzelnen elements bei 0.001 - um dort
auf 0.01 fuer nur ein einziges dieser elemente zu kommen benoetigte
der loesungsvorschlag tatsaechlich 100 identische eintraege auf einer
million gesamteintrage - ABER: die noch nicht angepasste gewichtung
aller anderen elemente waere aus praktischer sicht jetzt schon extrem
verschoben - die chance, eines dieser elemente zu ziehen laege jetzt
bei eins zu einer million.

wer macht denn sowas?

UND: die summe _aller_ gewichtungen muss doch hoffentlich immer 100 ergeben.

neugierig fragend zurueckbleibend - peterS. - [e-mail]

[phanty]

die chance, eines dieser elemente zu ziehen laege jetzt
bei eins zu einer million.
wer macht denn sowas?

ich. :)
wenn man ca. 50k mal auf diese gewichtete tabelle zugreift, dann kommen auch die "kleinen" ab und zu mal dran. und die ganz kleinen eben nicht - genau das was ich will.

UND: die summe _aller_ gewichtungen muss doch hoffentlich immer 100 ergeben.

ja klar, das war nur ein beispiel von zwei herausgenommen elementen um folgenden sachverhalt zu verdeutlichen.
ich wollte damit nur sagen, dass wenn die gewichtung eines elements 5000 mal grösser ist als die eines anderen, dass mein neues array dann 5000 mal so gross wird wie das ursprüngliche, da ich auf die kleinst mögliche basis muss.
von daher lieg ich meiner meinung nach eben nicht um faktor 100 daneben.

[peterS.]

hallo again,

lol - ja, ja,.. die JavaScript-Brille ... die hatte ich mal wieder
nicht abgenommen - was also bleibt von  meinem vorschlag uebrig?:

... die gewichtung solltest Du, ... festlegen, indem Du
die anzahl eines jeden eintrags seiner haeufigkeit
entsprechend vermehrst.
dann einmal gut durchmischen - die groesse deines
arrays duerfte jetzt  bei mehreren 100k eintraegen
liegen.

und jetzt genau einmal ueber die x * 100.000 eintraege ziehen.

so long - peterS. - [e-mail]

[Bademeister]

Hi phanty,

vorneweg, ich schliesse mich Hopsels Vorschlag an. Besser wirst Du es auf deterministische Weise nicht hinbekommen.

Ich schlage als Alternative aber einen probabilistischen Ansatz vor, der u.U. sehr effizient ist (das haengt allerdings von der Verteilung der Gewichte ab).

Idee:

Du generierst zwei Zufallszahlen:
Z ganzzahlig zwischen 1 und der Laenge des Arrays
und P zwischen 0 und 1 (mit hinreichender Genauigkeit).

Ist nun P kleiner als das Gewicht von array[Z], dann nimmste array[Z]. Anderenfalls machste das ganze nochmal.

Und dann geht man noch her und produziert P nicht zwischen 0 und 1, sondern zwischen 0 und dem Maximum aller Gewichte. Das aendert nichts an der Verteilung des Ergebnisses und macht den Algorithmus sehr effizient, sofern die Gewichte nicht zu verschieden sind.

viele Gruesse,
der Bademeister

[phanty]

hi Bademeister

Du generierst zwei Zufallszahlen:
Z ganzzahlig zwischen 1 und der Laenge des Arrays
und P zwischen 0 und 1 (mit hinreichender Genauigkeit).

Ist nun P kleiner als das Gewicht von array[Z], dann nimmste array[Z]. Anderenfalls machste das ganze nochmal.

so ne art Brute-Force-Methode. ^^
ich denke nicht dass das eine gute variante für mein problem ist.

Und dann geht man noch her und produziert P nicht zwischen 0 und 1, sondern zwischen 0 und dem Maximum aller Gewichte. Das aendert nichts an der Verteilung des Ergebnisses und macht den Algorithmus sehr effizient, sofern die Gewichte nicht zu verschieden sind.

den punkt hab ich jetzt nicht verstanden. kannst du mir das vielleicht in einem beispiel erläutern?

[Bademeister]

Hi,

kannst du mir das vielleicht in einem beispiel erläutern?

Dein Array hat 2 Elemente:

array[0] mit 40% Wahrscheinlichkeit
array[1] mit 60% Wahrscheinlichkeit

Wir waehlen nun P zwischen 0 und 1 (erster Ansatz). Wenn nun aber P groesser ist als 0.6,* musst Du ohnehin nochmal ran, weil keine Zahl ein so grosses Gewicht hat. Insgesamt wird in dem Beispiel in der Haelfte der Faelle der erste Versuch fehlschlagen.

Waehlst Du nun aber P gleich nur zwischen 0 und 0.6,* so wird das an der Ergebnisverteilung natuerlich nichts aendern, aber ein Versuch wird nur mit Wahrscheinlichkeit von einem Sechstel schiefgehen.

viele Gruesse,
der Bademeister

* was schlaegt der Duden vor, wenn vor einem Komma eine Kommazahl steht?

[Jens Holzkämper]

Tach,

* was schlaegt der Duden vor, wenn vor einem Komma eine Kommazahl steht?

ich denke mal nichts: Wenn klar ist, dass das Komma das Dezimaltrennzeichen ist, kann
1. ein Komma auf das ein Leerzeichen folgt kein Dezimaltrennzeichen sein und
2. kann das Dezimaltrennzeichen nicht zweimal innerhalb einer Zahl auftauchen.

Beispiel: Pi ist etwa 3,14, außer man rundet anders.

In Texten, die viele Zahlen und/oder Formeln enthalten sind, werden diese häufig kursiv bzw. nicht kursiv gesetzt.

mfg
Woodfighter

[Bademeister]

Hi Jens,

ich denke mal nichts:

ja, wahrscheinlich nicht.

Wenn klar ist, dass das Komma das Dezimaltrennzeichen ist, kann

1. ein Komma auf das ein Leerzeichen folgt kein Dezimaltrennzeichen sein und
2. kann das Dezimaltrennzeichen nicht zweimal innerhalb einer Zahl auftauchen.

Klar, es gibt da keine Mehrdeutigkeiten. Mein Problem war eher:

Beispiel: Pi ist etwa 3,14, außer man rundet anders.

Es sieht scheisse aus ;-)

In Texten, die viele Zahlen und/oder Formeln enthalten sind, werden diese häufig kursiv bzw. nicht kursiv gesetzt.

Ah ok, das ist, wenn auch nicht hier im Forum, ne elegante Loesung, sofern sich kursive und normale Darstellung des Kommas vernuenftig optisch unterscheiden.

danke, viele Gruesse,
der Bademeister

[phanty]

ok, danke. nun ist alles klar.
den zwischenschritt mit 0..1 hätte es gar nicht gebraucht. das hat mich wohl etwas verwirrt. ;)

[Don P]

Hallo,

die aufgabenstellung ist extrem einfach: ich möchte aus einem array ein element zufällig auswählen. der haken daran ist, dass jedes element eine andere gewichtung hat, sprich eine grössere oder kleinere chance hat ausgewählt zu werden.

bsp:
array[1] : 20.00% chance ausgewählt zu werden
array[2] : 10.00% chance ausgewählt zu werden
array[3] : 43.49% chance ausgewählt zu werden
array[4] : 26.51% chance ausgewählt zu werden

Die Aufgabenstellung scheint mir gar nicht einfach, oder es fehlen wichtige Angaben. Du willst also die unterschiedliche Gewichtung nicht haben? Es geht dir darum, dass  alle mit gleicher Wahrscheinlichkeit ausgewählt werden können?

Wenn der erzeugten Zufallszahl eine Gleichverteilung zugrunde liegt (dafür kannst du im Zufallsalgorithus ja sorgen), dann hat natürlich jedes Array-Element auch die gleiche Chance ausgewählt zu werden.

Wenn das aber trotzdem nicht der Fall ist, kann das nur einen Grund haben: Du hast gar keinen direkten Zugriff auf das "Array" über seine Indizes.
Ist das so? Dann würde ich versuchen, einen dirkten Zugriff zu erhalten, und gut. So ein Array ist mir aber noch nie untergekommen. Gibt es sowas überhaupt?

Falls aber direkter Zugriff besteht, dann geht es wohl nicht wirklich um die Indizes, die unterschiedliche Chancen haben, sondern eher um die Inhalte der Array-Elemente, weil es da Duplikate gibt. Wenn dem so ist, dann würde ich halt die Duplikate zuerst eliminieren. Mit einem SQL-Statement in einer Datenbank-Tabelle geht das recht einfach.

Gruß, Don P

[phanty]

hi

Falls aber direkter Zugriff besteht, dann geht es wohl nicht wirklich um die Indizes, die unterschiedliche Chancen haben, sondern eher um die Inhalte der Array-Elemente, weil es da Duplikate gibt. Wenn dem so ist, dann würde ich halt die Duplikate zuerst eliminieren. Mit einem SQL-Statement in einer Datenbank-Tabelle geht das recht einfach.

ja, da war ich vielleicht nicht ganz präzise bei der formulierung und dem beispiel. es geht wirklich um die inhalte. aber die anderen habens ja verstanden. :p

auf der anderen seite steht "array[1]" ja für den inhalt. index wäre in diesem fall ja nur die 1. ;)

duplikate gibts übrigens keine. das ist alles unique.

[Don P]

Hallo,

ja, da war ich vielleicht nicht ganz präzise bei der formulierung und dem beispiel. es geht wirklich um die inhalte. aber die anderen habens ja verstanden. :p

auf der anderen seite steht "array[1]" ja für den inhalt. index wäre in diesem fall ja nur die 1. ;)

duplikate gibts übrigens keine. das ist alles unique.

Ach so, du willst die unterschiedliche Gewichtung erst herstellen bzw. berücksichtigen, die jedes Element haben *soll*.

Das könnte so gehen:

Die W'keit, dass irgend ein ein Array-Element gewählt wird, ist 1. Insofern sind erst mal alle gleichwertig.
Also wählt man zunächst zufällig mit Gleichverteilung eins aus und fragt das gefundene Element nach seiner Gewichtung.
Entsprechend dieser Gewichtung entscheidet man mit Hilfe einer weiteren Zufallszahl, ob es auch wirklich würdig ist.

Beispiel:

Schritt 1 liefert array[25920] und dessen Gewicht ist p = 0.1

In Schritt 2 ermittelt man nun eine gleichverteilte Zufallszahl zwischen 1 und 1/p, also zwischen 1 und 10 (incl.).
Ist sie 1, so wird das Array-Element akzepiert, sonst nicht, usw. usf.

So wird mit Sicherheit im zweiten Schritt jedes Element mit der ihm gebührenden Gewichtung gezogen. Die Vor-Auswahl im 1. Schritt verfälscht nichts, da sie für alle gleich ist.

Der Ansatz ist, wie mir scheint, ziemlich ähnlich mit dem, den Andras Pflug beschreibt. Schneller bzw. einfacher wird es kaum gehen, wenn du das Array nicht irgendwie vorbehandeln willst.

Gruß, Don P

[phanty]

Beispiel:
Schritt 1 liefert array[25920] und dessen Gewicht ist p = 0.1

In Schritt 2 ermittelt man nun eine gleichverteilte Zufallszahl zwischen 1 und 1/p, also zwischen 1 und 10 (incl.).
Ist sie 1, so wird das Array-Element akzepiert, sonst nicht, usw. usf.

das würde dann in richtung brute-force-methode hinauslaufen und das wäre mir zu langsam.

ich hab heute schon zum dritten mal "gleichverteilte zufallszahl" gelesen.
ist die zufallszahl der meisten programmiersprachen (in meinem fall c#) nicht schon von haus aus gleichverteilt oder muss ich da noch was machen? was hat es mit diesem "gleichverteilt" auf sich? ^^

[Don P]

Hallo,

ich hab heute schon zum dritten mal "gleichverteilte zufallszahl" gelesen.
ist die zufallszahl der meisten programmiersprachen (in meinem fall c#) nicht schon von haus aus gleichverteilt oder muss ich da noch was machen? was hat es mit diesem "gleichverteilt" auf sich? ^^

Naja, meines Wissens ist ist die Zufallszahl der "meisten" Programmiersprachen gleichverteilt zwischen 0 und 1. Wenn man eine zwischen 0 und 5 gleichverteilt haben will, bringt's z.B. die 0,815 nicht wirklich. Die musste ja dann noch umrechnen. *Das* ist damit gemeint, und natürlich um den Unterschied zu anderen Verteilungen zu betonen, die es in der Welt ja auch noch gibt oder geben soll, wie in deinem Array ;-)

das würde dann in richtung brute-force-methode hinauslaufen und das wäre mir zu langsam.

Ok. Habe da noch eine ähnliche, aber vielleicht doch bessere Idee.
Obwohl mir irgendwie schwant, dass da ein Denkfehler drin sein könnte:

• Angenommen, es sind 100'000 Array-Elemente.
• Man sucht sich gleichverteilt ;-) eines aus und stellt fest, es hat das Gewicht 0,1.
• Es ist mit einer W'keit von nur p = 1/100'000 = 0.00001 gewählt worden
• Die W'keit, dass es das richtige ist, muss also 1/p = 10'000 mal größer sein
• Eine weitere Zufallszahl zw. 1 und 10'000 liefert das Ergebnis: Ist sie > 1, dann haben wir das richtige, sonst nicht.

Das dürfte in den meisten Fällen sofort klappen...

Gruß, Don P

[phanty]

• Angenommen, es sind 100'000 Array-Elemente.
• Man sucht sich gleichverteilt ;-) eines aus und stellt fest, es hat das Gewicht 0.1
• Es ist mit einer W'keit von nur p = 0.1/100'000 = 0.00001 gewählt worden

du mischt die anzahl der elemente mit der gewichtung?

• Die W'keit, dass es das richtige ist, muss also 1/p = 10'000 mal größer sein

es gibt eigentlich kein richtig, bloss ein auswählen oder nicht.
und "grösser sein" als was?

• Eine weitere Zufallszahl zw. 1 und 10'000 liefert das Ergebnis: Ist sie > 1, dann haben wir das richtige, sonst nicht.

Das dürfte in den meisten Fällen sofort klappen...

vermutlich liegts an mir und ich bin schon zu müde, aber ich versteh nur bahnhof. sorry.
so oder so, brute-force kommt bei mir nicht in frage, das dauert viel zu lange.

ps: zum anderen post: mir ist schon klar dass es echte zufallszahlen gar nicht gibt. selbst wenn man die zufallszahl mit 37 potenziert, dann den cosinus davon nimmt und drei mal die wurzel zieht ist es immer noch keine zufallszahl. also wer auch immer behauptet er kann eine echte zufallszahl generieren, der lügt. ;)
aber für meine zwecke genügt auch eine gefakete.

[Jens Holzkämper]

Tach,

ps: zum anderen post: mir ist schon klar dass es echte zufallszahlen gar nicht gibt.

doch, der Aufwand ist nur größer: z.B. http://random.org/

mfg
Woodfighter

[Don P]

Sorry,

• Die W'keit, dass es das richtige ist, muss also 1/p = 10'000 mal größer sein

Es muss natürlich heißen:

• Die W'keit, dass es das richtige ist, muss also 0.1/p = 10'000 mal größer sein

Ist auch brute-force, wäre aber vielleicht einen Versuch wert, wenn du Speicher sparen musst und kein Denkfehler drin ist...

Eine Simulation sollte das leicht klären können.

Gruß, Don P

[Don P]

Hallo phanty,

Tschuggelung, wenn ich so lange darauf herumhacke, aber Zufallsthemen interessiern mich nunmal.

ist die zufallszahl der meisten programmiersprachen (in meinem fall c#) nicht schon von haus aus gleichverteilt oder muss ich da noch was machen?

Wie su sicher weißt, sind das immer nur Pseudo-Zufallszahlen. Der Unterschied mag für viele irrelevant sein, aber natürlich gibt's auch genügend Fälle, wo man wirklich *echte* Zufallszahlen braucht.

Solche gibt's z.B. bei random.org.

Gruß, Don P

[Andreas Pflug]

die aufgabenstellung ist extrem einfach: ich möchte aus einem array ein element zufällig auswählen. der haken daran ist, dass jedes element eine andere gewichtung hat,
[...]
das problem ist jedoch, dass diese lösung 1. extrem unschön ist und 2. für meine anwendung nicht möglich ist, da mein array nicht nur aus 4, sondern aus 100k elementen besteht. das würde den speicher sprengen. ;)

Eine speicherschonende Methode wäre folgende:

1. Wähle ein Element i gleichverteilt-zufällig aus
2. Bestimme den Quotienten q = random() / gewichtung[i]
3. Wenn q<1, dann wähle das Element *wirklich* aus,
      ansonsten: Wiederholung bei Punkt 1

IMHO hat die Methode einen Namen wie 'Acceptance-Reject method'.
Voraussetzung ist natürlich, dass die Summe aller Gewichtungen 1 ist
(andernfalls muss entsprechend normiert werden).

Das Problem dabei ist, dass die Anzahl erforderlicher
Wiederholungen, bis ein Element dann wirklich mal akzeptiert wird,
sehr groß werden kann und die Sache dadurch langsam wird. Das
gilt vor allem dann, wenn einige wenige Array-Elemente eine
sehr große Gewichtung (und dafür die anderen eine entsprechend
kleine Gewichtung) haben.

Eine Alternative: Bilde ein zweites, gleichgroßes Array, in
dem sukzessive die Summe der Gewichtungen gespeichert wird.

Beispiel in C-Syntax (A1[] sei das ursprüngliche Array, A2[] das zweite Array mit den Gewichtungs-Summen, gew[] seien die Gewichtungen):

  
double sum_gew = 0.0;  
for(i=0; i<length; ++i) {  
  sum_gew += gew[i];  
  A2[i] = sum_gew;  
}  
// sum_gew sollte am Ende, abgesehen von Rundungsfehlern, 1.0 enthalten  
  
// [...]  
  
// Nun ein Beispiel zur gewichteten Selektierung:  
  
double r = random();  // Zufallszahl zw. 0 und 1  
int i=0;  
while(r>A2[i]) ++i;  
int iselected = i;  
  

Diese Methode ist vermutlich etwas schneller, erfordert jedoch
Speicherplatz für ein zweites, gleichgroßes Array mit
Fließkommazahlen.Was jetzt wichtiger ist - Speicherplatz
oder Performance - musst Du abwägen...

MfG

Andreas

[Andreas Pflug]

// Nun ein Beispiel zur gewichteten Selektierung:

double r = random();  // Zufallszahl zw. 0 und 1
int i=0;
while(r>A2[i]) ++i;
int iselected = i;

Es fiel woanders im Thread noch das Stichwort
'Binäre Suche'. Diese könnte man
hier wie folgt realisieren (in Pseudo-Code):

  
double r=random();  
int    i=0, imin=0, imax=length-1;  
while(imax-imin>1) {  
  i = imin + (imax-imin)/2; // wird automatisch gerundet, da vom Typ 'int'  
  if (r>A2[i]) { imin=i; } else { imax=i; }  
}  
int iselected = r>A2[imin] ? imax : imin;  

Das sollte auch bei 1 Mio Elementen noch ausreichend schnell sein
und die 8 MB für das Gewichtungs-Array sollten auch noch
über sein... ;-)

MfG

Andreas

[phanty]

double sum_gew = 0.0;
for(i=0; i<length; ++i) {
  sum_gew += gew[i];
  A2[i] = sum_gew;
}
// sum_gew sollte am Ende, abgesehen von Rundungsfehlern, 1.0 enthalten

// [...]

// Nun ein Beispiel zur gewichteten Selektierung:

double r = random();  // Zufallszahl zw. 0 und 1
int i=0;
while(r>A2[i]) ++i;
int iselected = i;

  
danke dir. das ist eigentlich eine ähnliche lösung wie bereits vorgeschlagen wurde, bloss dass hier anstelle von sortiert, aufsummiert wird - also schneller. guter input.

[Hopsel]

Hi phanty!

das ist eigentlich eine ähnliche lösung wie bereits vorgeschlagen wurde, bloss dass hier anstelle von sortiert, aufsummiert wird - also schneller.

Das ist exakt das, was ich meinte! =)

guter input.

Allerdings.

MfG H☼psel