pole náhodných čísel

[g58692]

Jak efektivně vygenerovat pole náhodných čísel, které se neopakují v rozsahu 0 až (délka_pole -1). Dělám to tak, že vygeneruji náhodné číslo a procházím pole, pokud vygenerované číslo není v poli, tak ho tam přidám.
Existuje nějaký efektivnější způsob (tohle je moc pomalé)?

[wojta]

Hned mě nic přímo nenapadá. Možná bych nalezená čísla aspoň cpal do binárního vyhledávacího stromu, což by složitost snížilo (tuším z N^2 na Nlog N). Zkus pogooglit.

[Drasha2]

Ja to delam tak, ze si udelam pole boolu o velikosti delka_pole, vsechno nastavim na false a kdyz vygeneruju cislo, tak akorat pouziju to cislo jako index a zkonfrontuju s obsahem...
@wojta: tohle ma slozitost konstantni... trumfni to :-B

[Benjamin]

To co se snazis provest se jmenuje generovani nahodnych permutaci a vsechny ulohy, ktere s tim souvisi jsou obecne docela zajimava oblast. Popis presne toho, co se snazis provest je tady (http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK4/NODE151.HTM):

Generating random permutations is an important little problem that people stumble across often, and often botch up. The right way is the following two-line, linear-time algorithm. We assume that Random[i,n] generates a random integer between i and n, inclusive.


for i=1 to n do a[i] = i;

for i=1 to n-1 do swap[ a[i], a[ Random[i,n] ];

That this algorithm generates all permutations uniformly at random is not obvious. If you think so, explain convincingly why the following algorithm does not generate permutations uniformly:


for i=1 to n do a[i] = i;

for i=1 to n-1 do swap[ a[i], a[ Random[1,n] ];

Such subtleties demonstrate why you must be very careful with random generation algorithms. Indeed, we recommend that you try some reasonably extensive experiments with any random generator before really believing it. For example, generate 10,000 random permutations of length 4 and see whether all 24 of them occur approximately the same number of times. If you understand how to measure statistical significance, you are in even better shape.

Nevim, jestli umis anglicky - tomu kodu je rozumet i tak, ale podstatne je i to, co pisou pod tim.

[Benjamin]

2 Drasha2: Rozhodne nemas konstantni slozitost. Dokonce pokud budes velky smolar, tak nemusis nikdy skoncit...

Ten mnou nalezeny algoritmus je zjevne linearni.
Coz je zjevne optimum, protoze zadny lepsi nez linearni algoritmus nemuze mit sanci vygenerovat vsechny permutace.

[manasus]

Já bych použil pomocné pole, které bych vyplnil posloupností. Pak bych generoval číslo v rozsahu 0 až n-1 kde n je počet prvků pomocného pole. To bych pak použil jako index pro výběr hodnoty z pomocného pole. Hodnota by se předala do zamíchaného pole. Po výběru by se v pomocném poli zbytek hodnot za vybraným prvkem přesunul o jedno místo vlevo a celé pole se zkrátilo o 1.
Ještě lepší než pole by bylo použít seznam dynamických prvků (s ukazateli na následující člen). Pak by odpadlo přesouvání (stačilo by počítadlo na přechod mezi prvky).
Nevím jestli jsem to napsal dostatečně srozumitelně...

[wojta]

Čili, jak jsem pochopil. Tak to do pole o délce n zapíše čísla od 1 do n, čili ta, která jsou různá. Pak je náhodně promíchá.

[tomko]

jo, pochopil. Kdysi jsem podobně dělal zasedací pořádek pro přijímačky...

[g58692]

Diky to je přesně ono.

[logout]

To manasus:
Zamysli se, a zjistíš, že Tvé řešení je úplně stejné jako řešení které navrhuje Benjamin, akorát hůře naipmplementované (musíš mít externí pole, zatímco v Benjaminově řešení se jak původní tak zamíchané pole vejde do jednoho).

Dynamické pole (spojový seznam) je pro tento účel úplně stejně (vhodné/nevhodné) jako normální pole: v jednom musíš přesouvat,
v druhém zas nenajdeš snadno n-tý člen.

Benjaminovo řešení je optimální:
To již někdo psal, že rychleji než lineárně to prostě nejde, a
benjamín dělá v jednom kroku čtyři instrukce (generování náh. čísla + výměna dvou čísel), takže jeden krok půjde také těžko urychlit.

...a správné:
To lze dokázat: náhodná permutace n prvků, je náhodně vybraný prvek a náhodná permutace n-1 prvků; zbytek důkazu se udělá matematickou indukcí.

Matyáš

[manasus]

No, průchod seznamem s následnou jednou úpravou by byl asi rychlejší, než přerovnávání pole. Ale třeba se pletu, budu rád, když mi v tom někdo udělá víc jasno. Teorii o složitosti zas tak zmáknutou nemám
Ale jinak díky za doplnění

[logout]

Ahoj,
chceš-li odstranit j-tý prvek z n-ti, tak
u spojového seznamu musíš projít
j prvků, než najdeš j-tý. (to procházení znamená u
každého přečíst pointer).
U pole musíš prvky j+1 až n zapsat na místo j až n-1 - tzn.
opět přečíst a zapsat n-j-1 hodnot. Takže teoreticky by
byl spoják býhodnější.
Jenže u pole je to lineární čtení paměti, které díky cache je rychlejší než náhodné čtení spojáku.
Pole zabírá méně paměti než spoják, operace přesuň kus paměti se dá zapsat jako jedna, je to daleko lépe paralelizovatelné, můžeš využít vektorových (SIMD) instrukcí - takže ve výsledku to bude s dobrým kompilátorem rychlejší.

Matyáš



Matyáš

[Benjamin]

2 manasus: Pokud se trochu zamyslis, tak zjistis, jak ten svuj algoritmus vylepsit, abys nemusel v tom pomocnem poli vzdycky prerovnavat (prumerne) pulku prvku, a pokud se zamyslis jeste o neco vic, muzes ten vylepseny algoritmus vylepsit tak, ze nebudes potrebovat ani zadne pomocne pole.

[Drasha2]

@benjamin:
Hehe, mas pravdu. Konstantni reseni je chimera... Byl jsem trochu zmateny po ranu Lip nez linearne to samozrejme nepujde...
Co se tyce meho postupu, tak si sice koleduji o to, aby to nevyslo, ale na druhou stranu se mnou zadna random funkce nikdy takhle nevyjebala a vzdycky to bylo dost rychle... (I kdyz verim, ze nekteri profesori by mi za tenhle pristup upravili znamky za zkousek [zvlaste za tu slozitost])