| Autor | Zpráva | ||
|---|---|---|---|
| peta Profil |
_es: Tva kontrola je chybna, neodpovida zadani. Ukol byl promichat to tak, aby uzivatel nabyl dojmu, ze to je promichane. Coz tvuj kontrolni algoritmus nesplnuje.
shuffle0: 353096, 695272 a pomer je 1.969 shuffle1: 360390, 700878 a pomer je 1.944 shuffle2: 360245, 700094 a pomer je 1.943 sort random 0.5: 434811, 685592 a pomer je 1.576 sort random 0.6: 360969, 683118 a pomer je 1.892 <script>
function myemunerate(arr,v,vysl)
{
for (var i=0; i<v; i++) {if (arr[i]>=1 && arr[i]<=v) {vysl[0]++; vysl[1]+=Math.abs((arr[i]-1)-i);}}; return vysl;
}
function myshow(name,vysl)
{
return "\n"+name+': ' + vysl[0] + ', ' + vysl[1] + ' a pomer je '+ Math.floor(vysl[1]/vysl[0]*1000)/1000;
}
function shuffle0(a) {
var i = a.length - 1, j, temp;
while(i) {
temp = a[i];
a[i] = a[(j = Math.round(i-- * Math.random()))];
a[j] = temp;
}
return a;
};
function shuffle1(p) {
var i = p.length, j, temp;
while(i) {
j = Math.floor(i-- * Math.random());
temp = p[i];
p[i] = p[j];
p[j] = temp;
}
return p;
}
function shuffle2(p) {
var x = [p.length], i = p.length;
while(i) x[i - 1] = p.splice(Math.floor(Math.random() * i--), 1)[0];
return x;
}
function shuffle3(a) {
return a.sort(function(){return Math.random() - 0.5;});
}
function shuffle4(a) {
return a.sort(function(){return 0.66 - Math.random();});
}
function mytest()
{
var a,v,t,i,j;
t = '';
v = 6;
b = ['shuffle0','shuffle1','shuffle2','sort random 0.5','sort random 0.6']
for (j in b)
{
vysl = [0,0];
for (i=0;i<100000;i++)
{
a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
a = window['shuffle'+j](a);
myemunerate(a,v,vysl);
}
t+= myshow(b[j],vysl);
}
alert(t+"\
\nPrvni cislo je pocet opakovani v intervalu 0-6 pozice, ktery by mel byt co nejmensi.\
\nDruhe cislo je soucet vzdalenosti od vychozi pozice, ktery by mel byt co nejvetsi, aby uzivatel nabyl dojmu, ze je to promichano lepe.\
");
}
mytest();
</script>_es: Jo a over si to v praxi, nejdriv, ktery z tech randomu se ti zda, ze dava lepsi nahodne promichani. Cisla jsou jedna vec, ale chybna uvaha druha. jak uz jsem psal, ja to provozuji pres rok a uz jednou jsem to spravoval prave na reklamaci kolegy, ktery rikal, ze to malo promichava. |
||
| _es Profil |
#2 · Zasláno: 16. 9. 2011, 13:50:41
peta:
„shuffle0: 353096, 695272 a pomer je 1.969“ Pomer čoho? Čo je to za pofidérne matematické výpočty? Po zvláštnej Petovej konštante ešte aj zvláštna Petova štatistická veličina, nazvaná trebárs „Petov pomer“? |
||
| peta Profil |
#3 · Zasláno: 16. 9. 2011, 13:56:29 · Upravil/a: peta
_es: Zkousel jsi ten muj kod spustit? Precetl jsi si alert? Vysvetluje vse, nac se prave ptas.
Zvlastni, ze Petova statisticka velicina vase pridane shuffle algoritmy vyzdvihuje, ale pouze ten random 0.5 shazuje. :) A algoritmus je pritom porad stejny. |
||
| _es Profil |
#4 · Zasláno: 16. 9. 2011, 14:15:21 · Upravil/a: _es
peta:
No dobre, tak ten „Petov pomer“ má byť čo najvyšší, alebo čo najnižší? Lebo nie je ani jedno, Alebo sa má rovnať nejakej ďalšej inej optimálnej Petovej konštante? Obávam sa, že nerozumieš pojmu náhodné rozmiestnenie prvkov, náhodné znamená to, že to od ničoho (v ideálnom prípade) nezávisí. Ak to závisí od predchádzajúceho rozmiestnenia, tak to už náhodné nie je. „Prvni cislo je pocet opakovani v intervalu 0-6 pozice, ktery by mel byt co nejmensi.“ Prečo? Na základe čoho si k takejto požiadavke prišiel? „Druhe cislo je soucet vzdalenosti od vychozi pozice, ktery by mel byt co nejvetsi, aby uzivatel nabyl dojmu, ze je to promichano lepe.“ Čiže ak pole [0,1,2,3,4,5,6,7,8,9] zamiešam na [9,8,7,6,5,4,3,2,1,0] a potom zase na [0,1,2,3,4,5,6,7,8,9] a tak stále dokola, tak vznikne vynikajúci dojem náhodného miešania - aké jednoduché. |
||
| peta Profil |
_es: Jasne, ja netvrdim, ze random s 0.66 je dokonaly. Nebo, ze to idealne rozmisti. To idealni rozmisteni dokazuje tvuj algoritmus testu. Ale tvrdim, ze random s 0.5 da horsi vysledek v prpade, ze pouzijes vestavenou js funkci sort.
"Čiže ak pole [0,1,2,3,4,5,6,7,8,9] zamiešam na [9,8,7,6,5,4,3,2,1,0] a potom zase na [0,1,2,3,4,5,6,7,8,9] a tak stále dokola, tak vznikne vynikajúci dojem náhodného miešania - aké jednoduché. " Pozor, to presne dokazuje tvuj algoritmus testu. On secte cisla ve sloupcich a podeli konstantou prumeru. suma(sloupec) / 4.5 = 1 suma(0+9) / 4.5 = 1 Cili, kdyz takova data das do tveho algoritmu, tak vyjde 1 (nebo v tvem pripade 10, protoze jsi konstantu podelil 10). Proto rikam, ze tvuj algoritmus je chybny. Muj algoritmus testu neni o moc lepsi, ale myslim si, ze vic odpovida tomu, co se ocekava. Jak uz jsem rikal, vubec jsi ho neprostudoval a uz jsi ho zpochybnil :) algoritmus hleda cisla 1-6, ktera byli umistene ve sloupcich 0-5. Pokud je tam najde, tak pripocte sloupci +1. A navic zjisti vzdalenost od puvodniho mista ulozeni. Zajima me prave pozice 0-5, protoze to je tech 6 fotek z 10, ktere uzivatel uvidi. On serazovaci algoritmus neni cyklus while a nedela shuffle do nekonecna nebo doby, kdyz se mu podari naplnit podminku whilu. Vymena prvku probiha tehdy, pokud vysledek funkce je kladny. A navic probiha jen nad omezenym poctem prvku, ktery nejhornim moznem pripade vypada takto: 10, 9, 8 ..., celkove neco kolem 66, presneji (n+1) * n/2 = 11*5, cili 55. Pokud k shuffle dojde pouze v 50 pripadech ze 100, tak z toho cisla je to 25x. Tuto pravdepodobnost jsem tedy zvysil tim, ze jsem prinutil algoritmus k castejsi zamene poli. Ano, kdyz tam das 1, tak se to seradi 10,9,8... Ale, to jsem nechtel. To reseni s 0.5 jsem nasel pred rokem na google, ale prakticky mi to kolega reklamoval a musel jsem to bud vymenit za jiny algoritmus nebo upravit. Uprava na 0.66 plne postacovala. Ano, michani pomoci sortu neni dobry zpusob nahodneho zamichani, protoze pocet kombinaci pro pravdepodobnost zameny 50:50 a pro 55 cyklu je silne omezen. A to i pro 0.66. takze jsem pro, pouzit spis nektery z vasich dalsich algoritmu. Ps. Nemam VS vzdelani v oboru IT. V tomto oboru je SS. Jen me to zajima, programovani a algoritmy. |
||
| Joker Profil |
_es:
„Čiže ak pole [0,1,2,3,4,5,6,7,8,9] zamiešam na [9,8,7,6,5,4,3,2,1,0] a potom zase na [0,1,2,3,4,5,6,7,8,9] a tak stále dokola, tak vznikne vynikajúci dojem náhodného miešania - aké jednoduché.“ Co jsem pochopil, tak zhruba tak to peta myslel, jen do toho zakomponoval trochu náhodnosti. Čili ta funkce má být náhodné třídění zatížené směrem k obracení pole. |
||
| _es Profil |
peta:
> Pozor, to presne dokazuje tvuj algoritmus testu. On secte cisla ve sloupcich a podeli konstantou prumeru. > suma(sloupec) / 4.5 = 1 > suma(0+9) / 4.5 = 1 > Cili, kdyz takova data das do tveho algoritmu, tak vyjde 1 (nebo v tvem pripade 10, protoze jsi konstantu podelil 10). Proto rikam, ze tvuj algoritmus je chybny. To je nezmyselné odvodzovanie. Podmienka, aby sa pri zvyšovaní počtu opakovaní rôzne čísla toho testu blížili tej istej hodnote je podmienka nutná, nie dostačujúca. Dajú sa vytvoriť iné testy na iné aspekty algoritmov zamiešania či generovania pseudonáhodných čísel. Až neskôr mi došlo, že tá Witikova funkcia robí algoritmicky to isté, než moja, len ušetrí trochu pamäte, moja zase ušetrí počet operácii priradenia do poľa. Chamurappi: Mohlo by sa z tohoto vlákna a z niektorých príspevkov toho súvisiaceho vytvoriť vlákno nové - teoretickejšie a v pôvodnom naň dať odkaz. Prípadne to dať aj do vlákna Časté potíže, zajímavosti a poučné debaty - dotaz na náhodné zoradenie sa objavuje dosť často. Moderátor Chamurappi: Hotovo.
|
||
| peta Profil |
#8 · Zasláno: 16. 9. 2011, 21:54:59
_es: Nerozumim, co jsi chtel tim ztucnenim rici. respektive, jestli to jeste ma dokazovat, ze tvuj test algoritmus je tedy lepcejsi?
|
||
|
Časová prodleva: 3 dny
|
|||
| _es Profil |
#9 · Zasláno: 19. 9. 2011, 12:20:09
peta:
„jestli to jeste ma dokazovat, ze tvuj test algoritmus je tedy lepcejsi?“ Že sa tým testom dá ukázať, že daný algoritmu náhodného zoradenia je zlý, nie je že správny. Teda ukazuje, že metóda sort je na ten účel zlá a funkcie shuffle1 a shuffle2 môžu byť správne. |
||
|
Časová prodleva: 8 dní
|
|||
| Witiko Profil |
_es:
„sort je na ten účel zlá“ To jsme snad stanovili už na začátku. Funkce sort je určena k použití s třídící funkcí, která navrací konzistentní výsledky. V opačném případě je chování zcela závislé na implementaci. Proč to peta nechce chápat a stále tu pomýleně podbízí své řešení právě s funkcí sort, kdy návratnost správných výsledků je asi tak zaručená, jako doručení balíku českou poštou?
|
||
| Chamurappi Profil |
#11 · Zasláno: 29. 9. 2011, 01:42:52
Reaguji na Witika:
„Funkce sort je určena k použití s třídící funkcí, která navrací konzistentní výsledky.“ Třeba v takovém C# provádí (tuším) kompiler kontrolu, zda předávaná třídicí funkce pracuje konzistentně. Dokáže pak zahlásit děsivě užvaněnou chybu :-) (teď se mi zrovna nedaří ji dohledat, ale je výmluvná) |
||
| Joker Profil |
#12 · Zasláno: 29. 9. 2011, 12:03:48
Když už to tu je tak pěkně shrnuté, pár poznámek:
peta: „Pokud das na pas vedle sebe 6 fotek a pouzijes serazeni random 1:1 (50:50), tak dojde k tomu, ze ti pulku nepromicha.“ Tohle je samozřejmě blbost. Jestli jsem dobře počítal, při naprosto náhodném novém pořadí bude pravděpodobnost že alespoň tři fotky budou na stejných místech jako předtím asi 31%. Dál je pro případné další řešitele dobré si uvědomit, že funkce kterou peta navrhl pole promíchá méně náhodně než ta původní. Motivací nejspíš bylo tu funkci zatížit směrem k otáčení pole, tzn. pokud původní pole je [1,2,3,4,5,6], aby se zvýšila pravděpodobnost, že 5 a 6 po promíchání budou někde na začátku, zatímco 1 a 2 na konci. Zároveň ale je důležité poznamenat, že vzhledem k problému diskutovanému v tomhle vláknu (že různé prohlížeče tu třídicí funkci volají několikrát a zároveň mohou nastat nekonzistentní výsledky) to nebude fungovat podle očekávání. Dál se mi zdá, že Witiko při zkoušení těch funkcí udělal jednu chybu, že to pole třídil opakovaně, tj. výstup předchozího cyklu je zároveň vstup do následujícího. Pro přesnější výsledky je myslím lepší vždycky míchat to samé pole. Pro zajímavost, vyzkoušel jsem v 10000x zamíchat pole [1,2,3,4,5,6] funkcí co psal peta a vyšlo mi: (poznámka, čistě náhodné rozmístění by mělo mít četnost na všech místech kolem 1/6 ~ 16,7%) - Výsledky se hodně liší v závislosti na použitém prohlížeči (zjevně je pravda, že různé prohlížeče používají různé algoritmy) - Někdy ten algoritmus selhává úplně, hlavně v Opeře, která nejčastěji nechává první jedničku (v 32,2% případů) a čtvrtou čtyřku (28,1%), přičemž má tendenci nechávat i dvojku na druhém místě (18,3%, častěji tam dává jen trojku- 23,7%) a pětku na pátém (21,6%, častěji tam je jen šestka- 23,3%). Ale i v IE8 byla nejčastější hodnota na druhém místě dvojka (20,2%) - Všechny zkoušené prohlížeče měly na některých místech relativně vysoké anebo naopak nízké četnosti některých hodnot, celkem bez souvislosti s cílem algoritmu co nejvíc „promíchat“ pole. Tady byl extrém Firefox a jeho nechuť míchat na čtvrtou pozici hodnoty 5 a 6 (7% resp. 4,5%, přičemž hodnota 4 má četnost 20,4%), ale i jinde to je podobné, například IE8 na šesté pozici velmi preferuje hodnotu 1 (34,7%) a naopak tam prakticky nedává hodnoty 3 a 5 (7,8% a 9,5%) Závěr: Ten algoritmus není pro daný účel vhodný. |
||
| Witiko Profil |
#13 · Zasláno: 29. 9. 2011, 18:55:10 · Upravil/a: Witiko
Joker:
„Dál se mi zdá, že Witiko při zkoušení těch funkcí udělal jednu chybu, že to pole třídil opakovaně, tj. výstup předchozího cyklu je zároveň vstup do následujícího“ Je tomu tak, došli jsme k tomu s _es v příspěvku #23 a vhodné řešení spolu s výsledky testování, které nebylo zatížené touto chybou ani mým přehmatem při zaokrouhlování, je uvedeno v příspěvku #28. Považoval bych toto řešení za konečné a skutečně tak náhodné, jako je funkce Math.random().
|
||
|
Časová prodleva: 13 let
|
|||
0