| Autor | Zpráva | ||
|---|---|---|---|
| Niorko Profil |
Máme jednoduchú implementáciu Quick sortu:
function qs(l,r){
var l=l; var r=r; var l2=l; var r2=r;
var pivot=values[l];
while (l!=r) {
if (l>r) { return 0 }
while (values[l]<pivot) { l=l+1; }
while (values[r]>pivot) { r=r-1; }
var temp = values[l];
values[l] = values[r];
values[r] = temp;
}
var piv=l;
qs(l2,piv-1);
qs(piv+1,r2);
} qs(0,9);Plánujem to animovať, tak mi nestačí vnorená hotová implementácia, napísal som si script sám... Avšak v 4 zo 10 pokusov mi stránka zamrzne. Ako vyriešiť prípadné zacyklenie a zachovať pri tom takúto formu? Neviem si vysvetliť prečo sa mi to zacyklí, v Lue mi tento istý skript funguje za každým pokusom. Ďakujem za pomoc =) |
||
| _es Profil |
#2 · Zasláno: 5. 9. 2012, 19:16:06
Niorko:
„var l=l; var r=r;“ ? l a r sú už automaticky premenné - sú to argumenty funkcie.
Čo je v premennej(?) values?
„v Lue mi tento istý skript funguje za každým pokusom.“ Čo je to to „Lue“? |
||
| Joker Profil |
#3 · Zasláno: 5. 9. 2012, 20:34:00
Niorko:
var l=l; var r=r; Jinak bych řekl, že se to opravdu může zacyklit. Na řídku 14 je piv = 1 a následně na 15 a 16 je piv-1 a piv+1. Čili řádek 15 a 16 je pokaždé qs(l2, 0) a qs(2, r2). Řádek 15 je tak úplně k ničemu, protože pro l2>=0 nakonec vždycky povede k return 0 na řádku 6 aniž by se v poli values něco změnilo. Ani řádek 7 nic neudělá, protože do pivot se předtím přiřadí values[l], takže v prvním cyklu se vlastně testuje values[l]<values[l], což nikdy nemůže platit. Zacyklí se to podle mě za těchto podmínek: 1. Pole není už na začátku seřazené, takže qs(0,9) dojde až k ř. 16 a volání qs(2,9). Jak píšu výš, ř. 15 a qs(0,0) nebude mít žádný vliv. 2. Ani v qs(2,9) není pole setříděné, takže znovu dojde na ř. 16 a znovu se zavolá qs(2,9) 3. Při některém volání qs(2,9) dojde k tomu, že na indexu 2 se ocitne nejnižší hodnota dané části pole (indexy 2-9) a zároveň pole ještě nebude úplně setříděné Tím při každém volání nastane situace, že l==r, neplatí l>r a tedy se pokračuje, hodnota se prohodí sama se sebou a znovu se zavolá qs(2,9) |
||
| Niorko Profil |
_es:
> Čo je v premennej(?) values?> > > „v Lue mi tento istý skript funguje za každým pokusom.“ > Čo je to to „Lue“? Premenná Values je pole 10tich čísiel a Lua je skriptovací jazyk. Mám to na iPade, tak preto som to využil. Lua - Wiki
Joker: > var l=l; var r=r; > Co má probůh tohle znamenat? Odstránil som to hneď po tom, ako som postol otázku, neviem odkiaľ mám tento zvyk. „Na řídku 14 je piv = 1 a následně na 15 a 16 je piv-1 a piv+1.“ nie je to piv = 1, ale piv=l (čítam El - L ako Left), čiže podmienka je v pohode, podla mňa. „Řádek 15 je tak úplně k ničemu, protože pro l2>=0 nakonec vždycky povede k return 0 na řádku 6 aniž by se v poli values něco změnilo.“ return false tam je preto, aby sa cykli stále neopakovali, ak by tam return false nebolo, stále by sa kontrolovali podmienky, takto to keď podmienka vyhovuje leavne celý sort.
Prikladám skript, ktorý som si písal na iPade a ktorý bol funkčný, len som ho prepisoval do JS, kvôli projektu. http://pastebin.com/ZT1pUAvM |
||
| Joker Profil |
#5 · Zasláno: 5. 9. 2012, 23:01:17
Niorko:
„nie je to piv = 1, ale piv=l (čítam El - L ako Left)“ Jo tak. To už mě nejdřív zmátlo na řádku 2, když jsem myslel, že tam je var l=1. Není úplně šťastné pojmenovávat proměnné jedním písmenem, zejména O a l. Tak pak nejjednodušší řešení bude vzít nějaké pole pro které se to zacyklí a běh toho programu si trasovat. |
||
| _es Profil |
#6 · Zasláno: 6. 9. 2012, 09:23:45
Niorko:
Možno bude problém v podmienkach na 7. a 8. riadku. JS umožňuje získať aj nedefinované prvky poľa, tie majú hodnotu undefined a vtedy je výsledkom porovnania false. Teda musíš overovať hranice poľa.
|
||
| Joker Profil |
_es:
Taky mám hlavní podezření na undefined, ale nemohl jsem najít situaci, kdy by se to zacyklilo. A přitom teď to jsem to uviděl skoro hned. Zacyklí se to v případě, že libovolná hodnota pole bude buď undefined, nebo rovna nějaké jiné hodnotě pole. V takovém případě není splněna ani podmínka na ř. 7, ani podmínka na ř. 8 (pokud jsou ty hodnoty stejné, je to zřejmé, a porovnání undefined s čímkoliv vrátí false), l a r se nezmění, hodnoty v poli se prohodí spolu navzájem a v dalším běhu se porovnají zase proti sobě a vznikne úplně stejná situace. Dodatek: Neporovnají se ty hodnoty proti sobě, ale pivot se porovnává zase s úplně stejnými hodnotami |
||
| peta Profil |
#8 · Zasláno: 6. 9. 2012, 12:41:26
Kdyz se mi neco zacykluje, tak si krok za krokem alertuji hodnoty nebo zapisuji do textarea, abych mohl sledovat, co se deje.
Co se stane v pripade, ze l=1 a r=1? Co se stane v pripade, ze l=10 a r=-10? // dostanes se mimo oblast pole a nevidim tam zadnou podminku, kterou bys to hlidal. za l++ a r-- se obvykle pouziva %min nebo %max (ale tim bys zustal treba na predchozi hodnote a cyklil by dal) nebo if l>max, r<max ... return. |
||
| Joker Profil |
#9 · Zasláno: 6. 9. 2012, 13:48:56
peta:
„Kdyz se mi neco zacykluje, tak si krok za krokem alertuji hodnoty nebo zapisuji do textarea, abych mohl sledovat, co se deje.“ Eh, no to je zase rada, vložit logování do nekonečného cyklu :-) A v dnešní době tohle je trochu archaická metoda, ne? Pustím si v prohlížeči vývojářské nástroje, do skriptu si na vhodné místo dám breakpoint a sleduji, co se děje. „dostanes se mimo oblast pole a nevidim tam zadnou podminku, kterou bys to hlidal.“ Ale je to ohlídané. Jednak konstrukcí těch podmínek (buď l>=r a cyklus skončí, nebo mezi aktuální položkou a koncem pole je hodnota, na které se ty cykly l++/r-- zarazí v příštím běhu), jednak nejmenší možné hodnoty jsou l=0, r=-1, přičemž r=-1 musí skončit return 0, a jednak se ty cykly l++/r-- mohou dostat maximálně na první index mimo pole, protože jeho hodnota bude undefined a nebude splněna podmínka cyklu. |
||
| peta Profil |
Joker:
Omyl. while (values[r]>pivot) { r=r-1; } |
||
|
Časová prodleva: 3 dny
|
|||
| Niorko Profil |
function qs(left,right){
var left2=left; var right2=right;
var pivot=val[left];
while (left!=right) {
if (left>right) { return false; }
while (val[left]<pivot) { ++left; }
while (val[right]>pivot) { --right; }
temp = val[left];
val[left] = val[right];
val[right] = temp;
}
piv=left;
qs(left2,piv-1);
qs(piv+1,right2);
} qs(0,9);Pre prehľadnosť ešte raz postnuté. Okúsil som všetky možné hodnoty a keďže v reťazci val[] sú akceptované iba hodnoty od 1 do 99 vyšlo mi, že cyklí sa to iba v prípade, ak sa tam nachádza ten istý prvok viac krát. Nejak sa mi však stále nedarí to opraviť...
|
||
| _es Profil |
#12 · Zasláno: 10. 9. 2012, 08:12:36
Niorko:
Znovu: Musíš overovať hranice poľa. Počet prvkov poľa p je p.length.
|
||
|
Časová prodleva: 7 dní
|
|||
| Niorko Profil |
#13 · Zasláno: 17. 9. 2012, 16:49:29
_es:
Ak overím hranice poľa, zostane mi pole porozhadzované. Stále tam je ten problém, že ak je v poli ten istý prvok, vyskytne sa chyba. Nie a nie prísť na to, ako to ošetriť. |
||
| _es Profil |
Niorko:
„Ak overím hranice poľa, zostane mi pole porozhadzované.“ Čo znamená „porozhadzované“? Máš snáď n prvkov poľa s indexami od 0 po n-1, či nie? A teda nie je problém ich v cykle všetky prejsť.
„Máme jednoduchú implementáciu Quick sortu:“ Veľa už hotových implementácií v JS sa dá určite nájsť vyhľadávačmi. |
||
|
Časová prodleva: 14 let
|
|||
0