WordSort
-
- Matfyz(ák|ačka) level III
- Příspěvky: 137
- Registrován: 1. 6. 2006 08:47
- Typ studia: Informatika Mgr.
- Bydliště: Praha 4
- Kontaktovat uživatele:
Re: WordSort
Mě už Wordsort také začíná zajímat, když jdu zítra na zkoušku Také mi to není úplně jasné, i když to bude nějaký primitivní algoritmus, leč úmyslně zašifrovaný tak, aby studentům přetížil mozek.
Až dointegruju, chci do sběru
- Tuetschek
- Supermatfyz(ák|ačka)
- Příspěvky: 651
- Registrován: 15. 6. 2005 13:54
- Typ studia: Nestuduji ale učím na MFF
- Login do SIS: duseo7af
- Kontaktovat uživatele:
Re: WordSort
No v podstate to neco takoveho je ... jde o normalni lexikograficke trideni, ktere ale na zmateni nepritele:
1. si slova nejdriv roztridi podle jejich delek
2. vytvori dvojice [poradi ve slove;pismeno] (napr. pro slovo ahoj vznikne [1,a], [2,h], [3,o], [4,j]) a ty setridi podle abecedy podle pismen
3. pak uz takto setrideny seznam jeste jednou setridi podle poradi (oboji je bucket-sortem, takze je to stabilni)
4. takto setridene dvojice rozdelim do mnozin (nazveme je Si) podle stejneho poradi pismene ve slove (napr. [1,a] a [1,d] jdou do stejne mnoziny, ale [2,a] do dalsi; de facto se jen odstrani duplicity)
5. zacne hlavni cyklus -- postupuju podle poradi pismenek ve slove, od konce (tj. kdyz nejdelsi tridene slovo ma delku 20, jdu od 20 k 1), kde v kazdem (i-tem) kroku:
I. rozdelim vsechna slova delky >= i do mnozin Tx podle i-teho pismena (tj. vsechna slova, ktera maji na i-tem miste stejne pismenko, padnou do stejne mnoziny), slova kratsi nez i pismen zatim neuvazuji
II. vyberu vsechny neprazdne mnoziny Tx (podle obsahu Si vim, ktere to jsou), a seradim je za sebe.
III. k vysledku pridam slova delky i-1 a jdu na dalsi krok (opet pouzivam k deleni podle i-teho pismena bucket-sort, takze je operace stabilni a zachovava poradi podle uz projitych kroku)
6. na konci vsechno setridim i podle prvniho pismene a dostanu spravne setridena slova
Takhle jsem to chapal ja, pred zkouskou koncem prosince ... tak ale nevim, jestli a jak moc to bylo spravne (k praktickemu overeni nedoslo ). Kdyztak to nekdo doplnte nebo opravte, urcite tu je spousta "proc", na ktery mozna nevim odpoved.
1. si slova nejdriv roztridi podle jejich delek
2. vytvori dvojice [poradi ve slove;pismeno] (napr. pro slovo ahoj vznikne [1,a], [2,h], [3,o], [4,j]) a ty setridi podle abecedy podle pismen
3. pak uz takto setrideny seznam jeste jednou setridi podle poradi (oboji je bucket-sortem, takze je to stabilni)
4. takto setridene dvojice rozdelim do mnozin (nazveme je Si) podle stejneho poradi pismene ve slove (napr. [1,a] a [1,d] jdou do stejne mnoziny, ale [2,a] do dalsi; de facto se jen odstrani duplicity)
5. zacne hlavni cyklus -- postupuju podle poradi pismenek ve slove, od konce (tj. kdyz nejdelsi tridene slovo ma delku 20, jdu od 20 k 1), kde v kazdem (i-tem) kroku:
I. rozdelim vsechna slova delky >= i do mnozin Tx podle i-teho pismena (tj. vsechna slova, ktera maji na i-tem miste stejne pismenko, padnou do stejne mnoziny), slova kratsi nez i pismen zatim neuvazuji
II. vyberu vsechny neprazdne mnoziny Tx (podle obsahu Si vim, ktere to jsou), a seradim je za sebe.
III. k vysledku pridam slova delky i-1 a jdu na dalsi krok (opet pouzivam k deleni podle i-teho pismena bucket-sort, takze je operace stabilni a zachovava poradi podle uz projitych kroku)
6. na konci vsechno setridim i podle prvniho pismene a dostanu spravne setridena slova
Takhle jsem to chapal ja, pred zkouskou koncem prosince ... tak ale nevim, jestli a jak moc to bylo spravne (k praktickemu overeni nedoslo ). Kdyztak to nekdo doplnte nebo opravte, urcite tu je spousta "proc", na ktery mozna nevim odpoved.
Plug 'n' Pray.
-
- Matfyz(ák|ačka) level II
- Příspěvky: 89
- Registrován: 4. 1. 2005 22:57
- Typ studia: Informatika Bc.
- Kontaktovat uživatele:
Re: WordSort
Delalo mi vazne velke potize to odkudkoliv pochopit, nakonec jsem cast vycetl z Knutha (kde primo tenhle algoritmus neni) a zbytek pak nakonec sam vymyslel a namatchoval na popsane. Zkusil jsem to vysvetlit lidsteji na:
http://wiki.matfyz.cz/wiki/TIN066_P%C5% ... #Word_sort
Snad to bude srozumitelnejsi. Prijde mi, ze popisem toho preprocessingu na zacatku se cela idea hrozne zamlzi, kdyz je to pritom jen optimalizacni trik.
http://wiki.matfyz.cz/wiki/TIN066_P%C5% ... #Word_sort
Snad to bude srozumitelnejsi. Prijde mi, ze popisem toho preprocessingu na zacatku se cela idea hrozne zamlzi, kdyz je to pritom jen optimalizacni trik.
Next lecture on time travel will be held on previous Monday.
-
- Matfyz(ák|ačka) level I
- Příspěvky: 7
- Registrován: 5. 6. 2008 20:43
- Typ studia: Informatika Mgr.
Re: WordSort
No sakra, to je radost!
Nestacilo by kratsi slova doplnit nejakym dummy znakem ktery budu brat jako nejmensi? a setridit to pak normalne kyblikovanim?
A jinak podle wiki se mi nedaripochopit jak potom ten preprocessing z (poradi pismenka ve slove, pismenko) vyuziju.. Vzdyt ty slova jsou tim uplne rozsypany. Uvazuji spravne, ze by se to ev. dalo napravit, tim, ze z toho udelam trojici (poradi pismenka ve slove, pismenko, cislo slova) a na konci linearnim pruchodem pres ruzne prihradky postavit vystupni slova? (na slozitosti by to asi nic nemenilo, ale - je to tak mysleno? nebo to muzu vyuzit nejak fikaneji a elegantneji? )
Krom toho mi neni u Hybrid sortu o chlup vyse jasne proc "Jedno přidání do přihrádky velikosti Xi je O(1 + Xi log Xi)"; nemelo by to byt spis jenom (1 + log Xi) = nalezeni prihradky + mozne probublani na vrchol haldy..
A jestli je tomu tak, nevite kde se potom v odhadu celkovy slozitosti E ( SUM (1+ Xi * log Xi)) bere ta 1cka? protoze jestli je to za nalezeni tech prihradek tak by misto ni melo byt spis Xi, ne?
Nestacilo by kratsi slova doplnit nejakym dummy znakem ktery budu brat jako nejmensi? a setridit to pak normalne kyblikovanim?
A jinak podle wiki se mi nedaripochopit jak potom ten preprocessing z (poradi pismenka ve slove, pismenko) vyuziju.. Vzdyt ty slova jsou tim uplne rozsypany. Uvazuji spravne, ze by se to ev. dalo napravit, tim, ze z toho udelam trojici (poradi pismenka ve slove, pismenko, cislo slova) a na konci linearnim pruchodem pres ruzne prihradky postavit vystupni slova? (na slozitosti by to asi nic nemenilo, ale - je to tak mysleno? nebo to muzu vyuzit nejak fikaneji a elegantneji? )
Krom toho mi neni u Hybrid sortu o chlup vyse jasne proc "Jedno přidání do přihrádky velikosti Xi je O(1 + Xi log Xi)"; nemelo by to byt spis jenom (1 + log Xi) = nalezeni prihradky + mozne probublani na vrchol haldy..
A jestli je tomu tak, nevite kde se potom v odhadu celkovy slozitosti E ( SUM (1+ Xi * log Xi)) bere ta 1cka? protoze jestli je to za nalezeni tech prihradek tak by misto ni melo byt spis Xi, ne?
-
- Matfyz(ák|ačka) level II
- Příspěvky: 89
- Registrován: 4. 1. 2005 22:57
- Typ studia: Informatika Bc.
- Kontaktovat uživatele:
Re: WordSort
To by dopadlo stejne, jako kdybys proste vynechal ten preprocessing. Musel bys prochazet zbytecne spoustu prihradek navic a mel horsi slozitost, krom toho treba u skutecneho slovniku kde vetsina slov je kratka, ale nektere fakt dlouhe, by to asi nebyl zdaleka jen teoreticky problem.hellboy píše:No sakra, to je radost!
Nestacilo by kratsi slova doplnit nejakym dummy znakem ktery budu brat jako nejmensi? a setridit to pak normalne kyblikovanim?
Pozor, vysledek toho preprocessingu neni neco, nad cim pak delas dal to trideni. Ten preprocessing ti jen vytvori pomocnou tabulku, kterou si das stranou, a pouze ji vyuzijes na rychle iterovani po existujicich pismenkach v dane hloubce, na nic jineho! Samotna data na trideni tim preprocessingem vubec nejsou ovlivnena. Presne tohle puvodne zmatlo i mne. Jestli uz je to jasnejsi, prosim uprav to v te wiki, aby to z toho pochopil i nekdo jiny nez ja.A jinak podle wiki se mi nedaripochopit jak potom ten preprocessing z (poradi pismenka ve slove, pismenko) vyuziju.. Vzdyt ty slova jsou tim uplne rozsypany. Uvazuji spravne, ze by se to ev. dalo napravit, tim, ze z toho udelam trojici (poradi pismenka ve slove, pismenko, cislo slova) a na konci linearnim pruchodem pres ruzne prihradky postavit vystupni slova? (na slozitosti by to asi nic nemenilo, ale - je to tak mysleno? nebo to muzu vyuzit nejak fikaneji a elegantneji? )
To je pekne zaludna otazka, priznam se, ze nevim, takhle je to v Koubkovi... Jestli na neco prijdes, bude to skvele.Krom toho mi neni u Hybrid sortu o chlup vyse jasne proc "Jedno přidání do přihrádky velikosti Xi je O(1 + Xi log Xi)"; nemelo by to byt spis jenom (1 + log Xi) = nalezeni prihradky + mozne probublani na vrchol haldy..
Jednu prihradku najdu v O(1), proste skocim na spravne misto pameti.A jestli je tomu tak, nevite kde se potom v odhadu celkovy slozitosti E ( SUM (1+ Xi * log Xi)) bere ta 1cka? protoze jestli je to za nalezeni tech prihradek tak by misto ni melo byt spis Xi, ne?
Next lecture on time travel will be held on previous Monday.
-
- Matfyz(ák|ačka) level II
- Příspěvky: 85
- Registrován: 12. 5. 2007 15:58
- Typ studia: Informatika Mgr.
- Login do SIS: dolej5am
- Kontaktovat uživatele:
Re: WordSort
možná někomu pomůže kratší popis v angličtině, který jsem našel před zkouškou. I když je to prakticky to samé, co tam má koubek
kde:
coalesce = nechej srust / srustej
concatenate = spoj
Kód: Vybrat vše
string sort(L)
{
make list of pairs (i,str[i])
bucket sort pairs by str[i]
bucket sort pairs by i (giving lists chars[i])
bucket sort strings by length
i = max length
L = empty
while (i > 0)
{
concatenate strings of length = i before start of L
distribute into buckets by chars in position i
coalesce by concatenating buckets in chars[i]
i--
}
concatenate list of empty strings at start of L
return L
}
coalesce = nechej srust / srustej
concatenate = spoj
-
- Matfyz(ák|ačka) level III
- Příspěvky: 151
- Registrován: 10. 12. 2006 19:26
Re: WordSort
Vsechno je super vysvetleny ale tady mas podle me chybu, melo by tam byt:Tuetschek píše:No v podstate to neco takoveho je ... jde o normalni lexikograficke trideni, ktere ale na zmateni nepritele:
1. si slova nejdriv roztridi podle jejich delek
2. vytvori dvojice [poradi ve slove;pismeno] (napr. pro slovo ahoj vznikne [1,a], [2,h], [3,o], [4,j]) a ty setridi podle abecedy podle pismen
3. pak uz takto setrideny seznam jeste jednou setridi podle poradi (oboji je bucket-sortem, takze je to stabilni)
4. takto setridene dvojice rozdelim do mnozin (nazveme je Si) podle stejneho poradi pismene ve slove (napr. [1,a] a [1,d] jdou do stejne mnoziny, ale [2,a] do dalsi; de facto se jen odstrani duplicity)
5. zacne hlavni cyklus -- postupuju podle poradi pismenek ve slove, od konce (tj. kdyz nejdelsi tridene slovo ma delku 20, jdu od 20 k 1), kde v kazdem (i-tem) kroku:
I. rozdelim vsechna slova delky >= i do mnozin Tx podle i-teho pismena (tj. vsechna slova, ktera maji na i-tem miste stejne pismenko, padnou do stejne mnoziny), slova kratsi nez i pismen zatim neuvazuji
II. vyberu vsechny neprazdne mnoziny Tx (podle obsahu Si vim, ktere to jsou), a seradim je za sebe.
III. k vysledku pridam slova delky i-1 a jdu na dalsi krok (opet pouzivam k deleni podle i-teho pismena bucket-sort, takze je operace stabilni a zachovava poradi podle uz projitych kroku)
6. na konci vsechno setridim i podle prvniho pismene a dostanu spravne setridena slova
Takhle jsem to chapal ja, pred zkouskou koncem prosince ... tak ale nevim, jestli a jak moc to bylo spravne (k praktickemu overeni nedoslo ). Kdyztak to nekdo doplnte nebo opravte, urcite tu je spousta "proc", na ktery mozna nevim odpoved.
II. Tx podle Si seradim je za sebe
jinak by tam bylo Si celkem k nicemu