WordSort

Přednáška navazuje na přednášky Algoritmy a datové struktury I a II a Programování I a II bakalářského studia. Bude věnována dvěma základním datovým strukturám, hašování a $(a,b)$-stromům (tato struktura se také nazývá $B$-stromy). Popisují se zde základní vlastnosti těchto struktur a jejich složitost. Na závěr přednášky se provede stručné zhodnocení třídicích algoritmů.

WordSort

Příspěvekod Ferooooo » 9. 2. 2008 20:36

Zdar

vedel by niekto ludsky, sedliacky, jednoducho vysvetlit wordsort? :) ten pseudokod mi hlavne v poslednej casti nedava zmysel a vobec to nevidim :/
Ferooooo
 

Re: WordSort

Příspěvekod ps » 13. 2. 2008 16:51

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
ps
Matfyz(ák|ačka) level III
 
Příspěvky: 137
Registrován: 1. 6. 2006 07:47
Bydliště: Praha 4
Typ studia: Informatika Mgr.

Re: WordSort

Příspěvekod Tuetschek » 14. 2. 2008 00:02

No v podstate to neco takoveho je :P ... 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 :-P). Kdyztak to nekdo doplnte nebo opravte, urcite tu je spousta "proc", na ktery mozna nevim odpoved.
Plug 'n' Pray.
Uživatelský avatar
Tuetschek
Supermatfyz(ák|ačka)
 
Příspěvky: 656
Registrován: 15. 6. 2005 12:54
Typ studia: Informatika Mgr.

Re: WordSort

Příspěvekod pasky » 15. 2. 2010 04:32

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.
Next lecture on time travel will be held on previous Monday.
pasky
Matfyz(ák|ačka) level II
 
Příspěvky: 89
Registrován: 4. 1. 2005 22:57

Re: WordSort

Příspěvekod hellboy » 15. 2. 2010 17:36

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?
hellboy
Matfyz(ák|ačka) level I
 
Příspěvky: 7
Registrován: 5. 6. 2008 19:43
Typ studia: Informatika Mgr.

Re: WordSort

Příspěvekod pasky » 15. 2. 2010 20:54

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?


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.

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? )


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. :)

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..


To je pekne zaludna otazka, priznam se, ze nevim, takhle je to v Koubkovi... Jestli na neco prijdes, bude to skvele.

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?


Jednu prihradku najdu v O(1), proste skocim na spravne misto pameti.
Next lecture on time travel will be held on previous Monday.
pasky
Matfyz(ák|ačka) level II
 
Příspěvky: 89
Registrován: 4. 1. 2005 22:57

Re: WordSort

Příspěvekod Jochanan » 16. 2. 2010 12:08

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
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
}

kde:
coalesce = nechej srust / srustej
concatenate = spoj
Jochanan
Matfyz(ák|ačka) level II
 
Příspěvky: 85
Registrován: 12. 5. 2007 14:58
Typ studia: Informatika Mgr.
Login do SIS: dolej5am

Re: WordSort

Příspěvekod peterblack » 3. 2. 2013 18:35

Tuetschek píše:No v podstate to neco takoveho je :P ... 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 :-P). Kdyztak to nekdo doplnte nebo opravte, urcite tu je spousta "proc", na ktery mozna nevim odpoved.

Vsechno je super vysvetleny ale tady mas podle me chybu, melo by tam byt:
II. Tx podle Si seradim je za sebe

jinak by tam bylo Si celkem k nicemu
peterblack
Matfyz(ák|ačka) level III
 
Příspěvky: 153
Registrován: 10. 12. 2006 19:26


Zpět na TIN066 Datové struktury I

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník

cron