WordSort

Odeslat odpověď

Smajlíci
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:

BBCode je zapnutý
[img] je zapnutý
[flash] je vypnutý
[url] je zapnuté
Smajlíci jsou zapnutí

Přehled tématu
   

Rozšířit náhled Přehled tématu: WordSort

Re: WordSort

od 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

Re: WordSort

od 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

Re: WordSort

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

Re: WordSort

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

Re: WordSort

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

Re: WordSort

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

Re: WordSort

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

WordSort

od 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 :/

Nahoru