Sicherstellen dass keine Zufallszahl doppelt vorkommt? [Archiv]

Archiv verlassen und diese Seite im Standarddesign anzeigen : Sicherstellen dass keine Zufallszahl doppelt vorkommt?

Sephiroth

2009-11-24, 17:48:20

Welche Methoden gibt es, um sicherzustellen das zufällig angeordnete Objekte (in einem vorgegebenen Bereich) sich nicht überlagern? Mir fällt da nur eins ein: prüfen ob die Koordinaten schon einmal vergeben wurden bzw. sich dort bereits ein Objekt befindet. Würde es vielleicht schon reichen den seed des PRNGs jedesmal zu ändern? IMHO nicht ... so what else?

Spasstiger

2009-11-24, 18:14:34

Pinoccio

2009-11-24, 19:08:07

Bei einem Generatorpolynom kommt innerhalb einer Periode keine Zahl doppelt vor. Musst also in diesem Fall nur sicherstellen, dass man innerhalb einer Periode bleibt. Ein Generatorpolynom kannst du als rückgekoppeltes Schieberegister umsetzen.Ein Generatorpolynom spuckt aber keine sonderlich gut handhabbaren Zufallszahlen aus.
Sobald du diese auf Gleitkommazahlen in [0,1] umrechnest hast du vermutlich ein Problem.

@Seph: Durchtesten ist die simpelste Lösung (jeder gegen jeden ,~n^2). Je nach Problemstellung kann man dies etwas verbessern.
Eine Möglichkeit ist es, die Objekte nach Koordinaten zu sortieren und dann nur Nachbarn zu vergleichen (~n*log(n)).

Harte Variante: Bei voll ausgeschöpften 64 Bit für die Koordinaten beträgt die Chance auf eine Kollison bei 2e+8 Koordinaten rund 0,1%. (Zahlen aus en.WP (http://en.wikipedia.org/wiki/Birthday_attack)).

Mit etwas mehr Details kann man dir da mehr raten ...

mfg

Sephiroth

2009-11-24, 20:10:20

Konkret sieht das Problem wie folgt aus: rechteckige Objekte einheitlicher (und bekannter) Größe, die auf einer rechteckigen Gesamtfläche zufällig angeordnet werden sollen. Die Gesamtfläche ist groß genug um alle Objekte aufnehmen zu können. Aufgrund der festen Größe der Gesamtfläche lässt sich ermitteln, wie viele Objekte pro Zeile passen (maxNumItemsOnX) und somit wie viele Zeilen benötigt werden (maxNumItemsOnY).
Daraus ermitteln sich nun die x- und y-Koordinaten eines Objekte wie folgt:

Random rand = new Random();
for (O obj : objects) {
int x = rand.nextInt(maxNumItemsOnX) * obj.width;
int y = rand.nextInt(maxNumItemsOnY) * obj.height;
//place it ...
}

D.h. die Koordinaten ergeben sich aus der zufälligen Position in der Zeile und Spalte jeweils multipliziert mit Breite respektive Höhe des Objekts.

Prinzip: Schachbrett zufällig belegen (leere Felder natürlich zulässig) aber kein Feld darf doppelt belegt werden.

Von den Objekten gibt es ca. 1 Million Stück.

Tesseract

2009-11-24, 20:30:15

du könntest das schachbett als eine art quadtree speichern, dann ist die überprüfung ob an der position bereits ein objekt sitzt logarithmisch, also relativ billig.

Demirug

2009-11-24, 20:36:23

Wie wäre es mit mischen?

Zuerst füllst du das Schachbrett regelmäßig auf. Der Abstand zwischen zwei gesetzten Zellen hängt dabei von dem Bedeckungsgrad ab.

Nun bestimmst du in einer Schleife immer zwei Zufallszahlen und tauscht den Inhalt (=Belegungszustand) dieser beiden Zellen aus.

Am Ende läuft man noch einmal über das Feld und greift die Koordinaten der belegten Zellen ab.

Das Verfahren hat den Vorteil das man die Zeit die man zum mischen zur Verfügung stellen will recht frei wählen kann.

Der_Donnervogel

2009-11-24, 20:41:39

Wäre in diesem Fall eine "unsaubere" Lösung auch denkbar? Also nicht die Möglichkeit einer Kollision versuchen zu vermeiden, sondern diese Ausnahme zu behandeln? Also sich beispielsweise alle gezogenen Zufallszahlen merken und bei einer Kollision einfach mit der nächsten weiter machen, oder alle denkbaren Koordinaten an denen sich ein Rechteck befinden kann in eine Menge geben. Aus dieser Menge dann per Zufallszahlengenerator immer ein Feld entnehmen bis alle Rechtecke verteilt sind. Sollte eine Zahl doppelt vorkommen, befindet sich die Position nicht mehr in der Menge der noch verfügbaren und man nimmt einfach die nächste Zufallszahl.

Ist zwar nicht ganz so sauber, sollte aber funktionieren. :sneak:

Tesseract

2009-11-24, 20:46:21

Zuerst füllst du das Schachbrett regelmäßig auf. Der Abstand zwischen zwei gesetzten Zellen hängt dabei von dem Bedeckungsgrad ab.

Nun bestimmst du in einer Schleife immer zwei Zufallszahlen und tauscht den Inhalt (=Belegungszustand) dieser beiden Zellen aus.

Am Ende läuft man noch einmal über das Feld und greift die Koordinaten der belegten Zellen ab.
ohne jetzt nachgerechnet zu haben würde diese variante wohl mit wesentlich mehr rechenaufwand verbunden sein wenn man ein ordentliches ergebnis haben will.

wie gesagt: mach doch einfach einen quadtree, speicher da alle objekte rein und du hast nur ein paar lookups beim einfügen von objekten und bei geringer belegung massive ersparnis von speicherplatz gegenüber irgendwelchen mega-arrays. bei einer kollision müsste man dann halt irgendwie weitermachen. z.B. zuerst nochmal probieren es einzufügen und nach 3 kollisionen ins nächste oder geometisch nächste oder sowas.

Also nicht die Möglichkeit einer Kollision versuchen zu vermeiden, sondern diese Ausnahme zu behandeln?

kollisionen kannst du mit zufallszahlen sowieso nicht vermeiden sonst wären sie nicht zufällig.

Demirug

2009-11-24, 20:57:02

ohne jetzt nachgerechnet zu haben würde diese variante wohl mit wesentlich mehr rechenaufwand verbunden sein wenn man ein ordentliches ergebnis haben will.

Hängt vom Bedeckungsgrad ab. Wenn man ein recht volles Feld hat ist mischen in der Regel schneller. Bei einem eher schwachgefüllten Feld würde ich auch zu einem Set (Hashkey aus den Koordinaten) zur Kollisionsprüfung tendieren. Ich weiß leider nicht mehr genau wo die Grenze lag.

Tesseract

2009-11-24, 21:29:02

du kannst die beiden varianten ja kombinieren: erstmal gleichmäßig verteilen, dann n-mal versuchen es random zu platzieren (wie ich geschrieben habe) und wenn das schief geht (dann ist das brett wohl schon enorm voll) auf die n-te position setzen und das, was vorher da war mit der alten posi vom element tauschen. das verhindert auch die kettenbildung wenn man irgendwann das element in ein fast volles brett einsetzen müsste.

und überleg dir wirklich den tipp mit dem quadtree. wenn du mehrere zigtausend elemente auf dem brett platzierst wird jede lineare abarbeitung (jedes mit jedem vergleichen usw.) früher oder später unnötig langsam.

Pinoccio

2009-11-24, 22:41:15

du könntest das schachbett als eine art quadtree speichern, dann ist die überprüfung ob an der position bereits ein objekt sitzt logarithmisch, also relativ billig.Ja, für alle k Objekte durchzuführen und damit auch wieder O(k*log(k)).
(Und entspricht im wesentlichen meinem sortieren&vergleichen Vorschlag. Ebenfalls mit dem Nachteil, daß du eine sinnvolle Vergleichbarkeit benötigst.)Wie wäre es mit mischen?

Zuerst füllst du das Schachbrett regelmäßig auf. Der Abstand zwischen zwei gesetzten Zellen hängt dabei von dem Bedeckungsgrad ab.
Nun bestimmst du in einer Schleife immer zwei Zufallszahlen und tauscht den Inhalt (=Belegungszustand) dieser beiden Zellen aus.
Am Ende läuft man noch einmal über das Feld und greift die Koordinaten der belegten Zellen ab.

Das Verfahren hat den Vorteil das man die Zeit die man zum mischen zur Verfügung stellen will recht frei wählen kann.Um richtig zu mischen müsstest du einen PRNG haben, der mehr Zustände hat als mögliche Belegung auftreten können. Sollte hier aber nicht stören.
Ansosnten schlägst du gerade Fisher-Yates (http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) vor, der inplace und O(n) ist.

Demirug ist bei k Objekten in m Zellen mit O(m) u. U. langsamer als sortieren oder Tesseracts Vorschlag mit O(k*log(k)).

mfg

Sephiroth

2009-11-24, 23:41:20

Hui das sind ja viele nette Ideen und Beiträge. :)

Im Moment nutze ich die im Eingangsposting erwähnte Methode der Überprüfung ... mittels eines HashSet, wobei meine Einträge einfach nur Strings der Form "x;y" (wobei x und y eben die entsprechenden Koordinaten) sind. Die Anfangsgröße des Sets entspricht genau der Anzahl an Objekten und LoadFactor ist auf 1, weil es nicht mehr Einträge als n werden können. ;) (Anfangsgröße der zugrunde liegenden HashMap wird eh auf die nächst größere 2er Potenz gesetzt und ist somit stets >= n). Damit sollte der Zugriff bzw. die Suche, ob die Koordinaten schon vergeben wurden, in O(1) gehen. Ich würde dann eigentlich nur noch die Strings durch was schlankeres ersetzen.

Der_Donnervogel

2009-11-24, 23:55:55

kollisionen kannst du mit zufallszahlen sowieso nicht vermeiden sonst wären sie nicht zufällig.Wenn man es so sagt, stimmt das natürlich. ;)

Ich bin davon ausgegangen dass der TS einen Algorithmus will der eine Sequenz erzeugt, in der zwei Zahlen nicht zwei mal vorkommen. Solche Sequenzen werden auch von einem guten Zufallszahlengenerator erzeugt, wenn man den richtigen Seed hat. Ich habe mir gedacht, wird sicher irgend einen Algorithmus geben, der genau diese Aufgabe bewältigen kann und "Zufallszahlen" erzeugt die in einer gewissen Periode keine Wiederholungen haben.

Berni

2009-11-25, 00:09:05

Wenn das Schachbrett nicht zu groß ist kannst du einfach alle möglichen Punkte als ein eindimensionales Bitarray speichern (Java hat hierfür das Bitset aber evtl. gibts da auch noch bessere Klassen bei denen man in der Größe nicht auf Integer beschränkt ist). Die Position im Bitarray ergibt sich aus aus x + (Zeilenlänge *y). Das Array wird mit 0en initialisiert. Beim Einfügen wird geprüft ob der Eintrag besteht. Falls ja werden die nächsten 2 Zufallszahlen gesucht bis was frei ist. Ansonsten wird der Eintrag eben auf 1 gesetzt. Performancemäßig ist diese Lösung Baumstrukturen vermutlich deutlich überlegen, die Frage ist halt ob der RAM reicht...
Für den Fall, dass man mehr als die Hälfte der Felder belegen will (weiß man in deinem Szenario ja vorher) ist es besser wenn man das Problem einfach umdreht und die nicht belegten Felder ermittelt.

Bei deiner HashSet-Lösung kannst du übrigens auch einfach auf die von mir genannte Koordinatenberechnung zurückgreifen. Somit speicherst du nur eine Zahl.

Übrigens: Die Random-Klasse von Java ist nur bedingt empfehlenswert: http://blog.uncommons.org/2008/04/03/a-java-programmers-guide-to-random-numbers-part-1-beyond-javautilrandom/ Die Angabe der Periodenlänge bringt hier übrigens nichts weil das NICHTS darüber aussagt, dass eine Zahl nicht trotzdem doppelt vorkommen kann. Es geht nur darum dass sich die anfängliche Zahlenfolge 1:1 wiederholt.

pest

2009-11-25, 05:19:01

Pinoccio

2009-11-25, 09:17:38

klar kann man eine "Koordinatensequenz" erzeugen wo kein Wert im Laufe der Zeit doppelt vorkommt. Ist total simpel, aber ich finde eure Ansätze sehr interessant, da brauch ich mich über die Performance diverser Applikationen nicht wundern :tongue:

edit: verdammt, es ist 5:20 und ich stelle mal wieder fest das ich nicht genial bin, sondern mir nur das Fisher-Yates-Shuffle (von dem ich noch nie was gehört habe) eingefallen ist :DDiese Erkenntnis haben ziemlich viele ziemlich oft.der geht doch aber anders als das was Demirug vorgeschlagen hat (ja es ist früh ;))Jein. Demirug will mischen, so wie er es vorschlägt ist es aber etwas zu umständlich. Wenn er seinen Vorschlag ausformulieren würde und implementieren würde und darüber nachdenken würde, wie man ihn verbessern kann, würde er wohl (so wie du) bei FY landen.
(Noch oder schon wach?)es reicht theoretisch einen PRNG zu benutzen, der mehr Zustände hat, als max Anzahl an Belegungen <= mögliche BelegungenDas verstehe ich nicht ganz.
Wir haben Binomialkoeffizient(m über k) viele Möglichkeiten k Objekte auf m Plätze zu verteilen. Wenn wir jede davon mit gleicher Wahrscheinlichkeit auswählen wollen, dann benötigen wir einen PRNG, der mehr mögliche Zustände hat. Und wenn wir von 1 Millonen Objekten sprechen, dann ist damit selbst der an sich empfehlenswerte MT überfordert.
Hier (http://groups.google.com/group/comp.lang.c/browse_thread/thread/a9915080a4424068/) schlägt G. Marsaglia einen mit einer Periode von 2^131104 vor, selbst der würde theoretisch nicht reichen.
Aber wie gesagt, für eine einfache Simulation ist das evtl. nicht so wichtig.
Übrigens: Die Random-Klasse von Java ist nur bedingt empfehlenswert: http://blog.uncommons.org/2008/04/03/a-java-programmers-guide-to-random-numbers-part-1-beyond-javautilrandom/Auch wenn ich den verlinkten Beitrag unbefriedigend finde, so ist der Hinweis, JAVAs eingebauten PRNG (Math.Random) nicht zu nutzen natürlich richtig.
Ich bin davon ausgegangen dass der TS einen Algorithmus will der eine Sequenz erzeugt, in der zwei Zahlen nicht zwei mal vorkommen. Solche Sequenzen werden auch von einem guten Zufallszahlengenerator erzeugt, wenn man den richtigen Seed hat.Ja, aber wie ich oben schon schrieb nur im nativen Ausgabeformat (wie immer man das verstehen will) des PRNG. Sobald man den Output auf einen kleineres Zahlenformat umrechnet, bekommt man Doppelungen.
Bei LCG ist der Seed egal, m. W. n. sogar bei praktisch allen PRNG.
(Natürlich nur, wenn die Periodenlänge größer ist als der Umfang des Zahlenformates. Das sollte aber immer der Fall sein.)
Im Moment nutze ich die im Eingangsposting erwähnte Methode der Überprüfung ... mittels eines HashSet, wobei meine Einträge einfach nur Strings der Form "x;y" (wobei x und y eben die entsprechenden Koordinaten) sind. Die Anfangsgröße des Sets entspricht genau der Anzahl an Objekten und LoadFactor ist auf 1, weil es nicht mehr Einträge als n werden können. ;) (Anfangsgröße der zugrunde liegenden HashMap wird eh auf die nächst größere 2er Potenz gesetzt und ist somit stets >= n). Damit sollte der Zugriff bzw. die Suche, ob die Koordinaten schon vergeben wurden, in O(1) gehen. Ich würde dann eigentlich nur noch die Strings durch was schlankeres ersetzen.Strings sind, insbesondere in JAVA, Performance-Killer. LoadFactor auf 1 ist aus Performancesicht wohl ebenfalls ungünstig, iirc ist 0.7 eine gute Grenze.
Und das die Zugriffe pauschal O(1) sind, kann ich mir nicht vorstellen.

Toll. Und wer macht meine Arbeit? :freak:

mfg

pest

2009-11-25, 09:37:44

(Noch oder schon wach?)

schon, warum auch immer

Wir haben Binomialkoeffizient(m über k) viele Möglichkeiten k Objekte auf m Plätze zu verteilen. Wenn wir jede davon mit gleicher Wahrscheinlichkeit auswählen wollen, dann benötigen wir einen PRNG, der mehr mögliche Zustände hat.

ja meine variante funktioniert nur, wenn wir m objekte auf m plätze verteilen wollen. allerdings kann man die hohe benötigte genauigkeit des prngs umgehen.

wollen wir k objekte auf m plätze verteilen, nehmen wir die rel. häufigkeit k/m
laufen alle m plätze durch und ziehen jeweils eine gleichverteilte zufallszahl p aus [0,1]. ist p < k/m wird der platz mit einem objekt belegt, und dieses aus der liste der noch zu verteilenden objekte gestrichen.

Pinoccio

2009-11-25, 10:37:30

ja meine variante funktioniert nur, wenn wir m objekte auf m plätze verteilen wollen. allerdings kann man die hohe benötigte genauigkeit des prngs umgehen.m Objekte auf m Plätze verteilen wäre, wenn ich Sephiroth richtig interpretiere, nicht sinnvoll, da seine Objekte nicht unterschieden werden. Für m gleichartige Objekte und m Plätzze gibt es dann genau eine möglicher Verteilung.wollen wir k objekte auf m plätze verteilen, nehmen wir die rel. häufigkeit k/m
laufen alle m plätze durch und ziehen jeweils eine gleichverteilte zufallszahl p aus [0,1]. ist p < k/m wird der platz mit einem objekt belegt, und dieses aus der liste der noch zu verteilenden objekte gestrichen.Das ist die Lösung zu einem anderen Problem. :tongue:
Wenn du das so machst, werden zwar im Mittel k Plätze besetzt, aber du hast in der Anzahl der bestzten Plätze eine Varianz von k*(1-k/m).

mfg

Trap

2009-11-25, 10:45:54

Wenn man eine raumfüllende Kurve nimmt kann man das Problem von 2 Dimensionen auf eine vereinfachen. Wenn man dann noch eine Methode findet die möglichen x von y Belegungen aufzuzählen, reichen entsprechend viele zufällige Bits (so dass 2^n > Anzahl möglicher Belegungen) um die Belegung festzulegen.

Die Zuordnung der Objekte zu den belegten Plätzen kann man auch als 2. Schritt machen, die Objekte mischen und der Reihenfolge nach die als belegt markierten Plätze auffüllen.

Pinoccio

2009-11-25, 11:01:54

Wenn man dann noch eine Methode findet die möglichen x von y Belegungen aufzuzählen, reichen entsprechend viele zufällige Bits (so dass 2^n > Anzahl möglicher Belegungen) um die Belegung festzulegen.Mögliche Belegung von 1 Mio Objekten in 2 Mio Plätzen: ~ 2^1000000 (http://www.wolframalpha.com/input/?i=round%28log%28binomial%282*10%5E6%2C+10%5E6%29%29%2Flog%282%29%29). Theoretisch funktioniert deine Variante, aber praktikabel ist sie nicht.
Selbst für 32 Objekte in 64 Plätzen (aka Schachbrett) hat man 2^61 (http://www.wolframalpha.com/input/?i=round%28log%28binomial%2864%2C+32%29%29%2Flog%282%29%29) mögliche Belegungen (abzüglich Symmetrie). Das wäre vielleicht noch speicherbar, aber nichtmehr "rechenbar".

mfg

Trap

2009-11-25, 11:11:29

Du hast da was falsch verstanden, bei 2^x möglichen Belegungen braucht man natürlich nur x Zufallsbits um eine davon auszuwählen, nicht 2^x.

Das Problem ist eher bei der Aufzählung der Belegungen und bei der Umsetzung der festgelegten Belegung, da bin ich mir noch nicht sicher, dass das effizient geht.

Pinoccio

2009-11-25, 14:33:19

Sephiroth

2009-11-25, 15:07:50

Strings sind, insbesondere in JAVA, Performance-Killer. LoadFactor auf 1 ist aus Performancesicht wohl ebenfalls ungünstig, iirc ist 0.7 eine gute Grenze.
Und das die Zugriffe pauschal O(1) sind, kann ich mir nicht vorstellen.

Toll. Und wer macht meine Arbeit? :freak:

mfg
Ein Loadfactor von 0.7 bedeutet doch: bei 70% Belegung verdoppel die Kapazität. Aus 1 Mio. (bzw. 2^20) werden 2 Mio (bzw. 2^21). Ein Vergrößerung bedeutet aber jedesmal ein neues Array anzulegen und die Einträge aus dem alten Array an die neue Stelle im neuen Array zu kopieren. Das mag ok sein, wenn man nicht weiß wie viele Elemente die Map enthalten soll aber da ich weiß wie viele am Ende enthalten sein werden, spar ich mir das lieber.
Zugriff in O(1), weil man die Position in dem Array eben in O(1) bestimmt werden kann.

Un die Sache mit den Strings weiß ich ja selber, daher probier ich den Vorschlag von Berni mal aus.

Pinoccio

2009-11-25, 15:23:01

Ein Loadfactor von 0.7 bedeutet doch: bei 70% Belegung verdoppel die Kapazität. Loadfactor: da haben wir uns missverstanden, ich meinte diesen Aspekt (http://en.wikipedia.org/wiki/Hash_table#Load_factor), also im Sinne von Auslastung.. JAVA nutz diesen Begriff im Collection-Framework etwas anders, hätte ich wissen müssen. Mea culpa.
Meine Aussage in der Begrifflichkeit wäre also: setze die initalCapacity auf etwa 1,4*Anzahl der Objekte.

mfg

Trap

2009-11-25, 16:22:49

Stimmt, ich verstehe das nicht, bzw. falsch. Könntest du es mir bitte etwas erläutern?
Wenn man eine Aufzählung aller möglichen Belegungen x von y Zellen hat (als Konzept), reicht es eine der möglichen Belegungen auszuwählen, um festzulegen, welche Zellen belegt und welche frei sind.

Um eine von 2^n möglichen Alternativen zufällig auszuwählen braucht man n Zufallsbits.

Damit das tatsächlich eine effiziente Problemlösung ist, braucht man eine Aufzählungsvorschrift, mit der man bei gegebener Auswahl "Belegung 72348" direkt und mit vertretbarem Aufwand die tatsächlich belegten und freien Felder ermitteln kann.

pest

2009-11-25, 16:41:52

Wenn du das so machst, werden zwar im Mittel k Plätze besetzt, aber du hast in der Anzahl der bestzten Plätze eine Varianz von k*(1-k/m).

sicher, aber das ist doch das geringste problem, da wird die wahrscheinlichkeit einfach laufend angepasst, und wenn dann tatsächlich am ende noch zu viele objekte übrig sein sollten verwendet man eben brute-force.

ich sehe das so
pest denkt 5min nach, und denkt sich einen algo mit Laufzeit O(m) aus
der rest vom 3dcenter denkt mehrere stunden nach, und kommt auf quadtrees und eingebettete kurven...:wink::tongue::P aka einfache probleme, haben oft einfache lösungen

Pinoccio

2009-11-25, 17:31:29

ich sehe das so
pest denkt 5min nach, und denkt sich einen algo mit Laufzeit O(m) aus
der rest vom 3dcenter denkt mehrere stunden nach, und kommt auf quadtrees und eingebettete kurven...:wink::tongue::P aka einfache probleme, haben oft einfache lösungenDein Verfahren löst aber nicht das Problem, k viele Objekte zufällig gleichverteilt auf m viele Zellen zu verteilen.
Ein gegebenes Problem durch ein anderes, einfacheres zu ersetzen mag üblich sein, aber naja ... ;-)

mfg

Berni

2009-11-25, 19:24:27

Übrigens: Wenns um Performance geht, so solltest du die Datenstrukturen optimieren und keiensfalls ein Standard-Hashset nehmen! Allein die Verwendung realer primitiver Datentypen (im Normalfall wird Autoboxing verwendet und ein int nach Integer gewandelt!) bringt Einiges an Performance (und braucht meist erheblich weniger RAM). Du kannst ja einfach den zugrundeliegenden Code aus dem OpenJDK nehmen und die Variablendefinition entsprechend ändern. Alternativ kannst du dir das aber auch sparen und direkt fertig optimierte Klassen wie z.B. aus trove nehmen (TIntSet bzw. TLongSet). Auch ein Performancevergleich mit den Klassen von javolution kann was bringen (es gibt auch noch paar andere, siehe http://karussell.wordpress.com/2009/09/03/java-collections-are-there-alternatives/ ).

wry

2009-11-25, 19:28:28

Ich hab jetzt nicht alles gelesen in diesem Thread, aber ich würd so machen:

1) Alle möglichen (x/y)-Koordinaten-Paare als Liste speichern.
2) Eine Zufallszahl z erzeugen, 0<=z<Liste.length
3) Das Objekt an die Koordinate (x/y), auf die z zeigt, speichern und dann die Koordinate aus der Liste rauslöschen.
4) Gehe zu Schritt 2). Ende wenn alle Objekte gespeichert sind.

pest

2009-11-26, 23:32:06

Ein gegebenes Problem durch ein anderes, einfacheres zu ersetzen mag üblich sein, aber naja ... ;-)

man kann das auch anders betrachten
das eigentliche problem kennen wir nicht wirklich, nur ein vom ts ausgewähltes teilproblem.

vielleicht ist der einfluss auf das ausgangsproblem gering, oder spiegelt es sogar besser wieder,
so dass wir die problemstellung ohne große auswirkungen abändern können, indem wir eben im mittel k objekte mit einer bestimmten rel. häufigkeit verteilen.

der algorithmus von wry ist beim vernachlässigen des speicherplatzes (also wenn m nicht viel größer als k ist), die weitaus intelligentere variante ;)
- zumindest wenn man die liste als array speichert, und dann direktes hashing zum suchen verwendet. wird trotzdem schwer mit dem exakten ansatz O(m) zu erreichen

üblich trifft es da nicht ganz. manchmal hat man gar keine andere wahl,
um bei bestimmten problemen überhaupt analytische lösungen bestimmen zu können,
aber wem erzähl ich das ;)

gruss