Registrace nového uživatele     Návod     Kluby     Archív  Lopuchu     Lopuch.cz  

Náš Lopuch Vám
vytře zrak

Lopuch.cz

Jméno:
Heslo:
Podpora LCD:
 
Klub Programování [ŽP: neomezená] (kategorie Programování) moderuje tvx.
Archiv
  Nastavení klubu     Nastavení práv     Homepage     Anketa     Přítomní     Oblíbené     Lopuch     Kategorie  
autor: 
text: 
vyplnit a 
Help
 Titulek, text příspěvku  
Opište pozpátku následující text bez prostředního znaku: cztdkhy
[ 857 ] <Novější  <<<Nejnovější  Nejstarší>>>  Starší>  
makak makak 1.11.2006 11:15  597
razeni vs. trideniNechci tady rozpoutavat ponekud off-topic tema k pouziti slov "trideni" (deleni prvku do trid) a "razeni" (vytvoreni posloupnosti prvku - rady). Jiste, na razeni jde pohlizet jako na specialni pripad trideni. Ale... Priklady ze zivota: Do fronty na pivo se lide "radi" ci "tridi"? Ci jaky to povel pro utvar zname? "Seradte se!" ci "Setridte se!"? Takze jen takove male zamysleni nad aktualnim tematem :-)
decide 1.11.2006 09:41  596
QuicksortFirstK Jak je důležité, míti pivotaTak jsem včera hledal pivota. Ten program napřed připraví hodnoty a vybírá nejlepší. Měřím zatím bohužel jen celkový čas, takže nemám absolutní hodnoty časů třídění, ale i tak je vidět, že u pivota na velikosti záleží. Posuďtě sami.
Vyrobil jsem čtyři verze stejného programu. Program připraví 400 hodnot a pak z nich vybírá. Proběhlo několik set tisíc měření, hodnoty jsou pokaždé jiné, nebo se alespoň často mění.
První Prg_mx pouze jednoduše vyhledal jeden nejlepší prvek pole. Slouží pro odhad, QSFK nedosažitelného minimálního, času
Další používaly quicksorFirstK k nalezení nejlepších 20 prvků.
Volba pivotů:
Prg_P1 - nejlepší z náhodně vybraných pěti prvků
Prg_P2 - druhý nejlepší z náhodně vybraných pěti prvků
Prg_Stupid - pivot je střed právě tříděného intervalu
časy uvádím v mikrosekundách
Prg_mx 282
Prg_P1 467
Prg_P2 346
Prg_Stupid 755
Kingu: Takže tvůj odhad byl dost dobrý
norfin Norfin 1.11.2006 09:24  594
No, pokud si dobre vzpominam, tak nas bucketsort fungoval tak, jak popisuje Bredy. Tedy slo se od posledniho znaku a v kazdem kroku se pouzilo trideni do prihradek. Bylo to rychle, protoze jsem dopredu vedel, ktere krabicky budou v jakem kroku pouzity. A dokonce, jestli se nemylim, i vsechny krabicky, ktere budou v danem kroku neprazdne. Ale jak rika Gumysh, stejne je to vsechno na jedno brdo.
kdokoliv Kdokoliv Nevidím důvod dělat cokoliv bezdůvodně. - http://kkl2401.wz.cz 1.11.2006 09:18  593
Praveze si taky myslim, ze nam to cpali pod pojmem bucket sort. A hlavne se mi furt nezda ten counting sort, ne, ze bych chtel wikipedii obvinovat ze lzi, toho jsem dalek, ale proste pokud jsme tomu nejak rikali (coz je taky mozny, ze ne), tak urcite jinak.
gumysh 1.11.2006 08:18  592
Norfin:
Ano, na datovkach - pokud jsme videli ty same ;o) - se bral bucketsort na retezcich. Neni problem ho udelat stejne na cislech.

King:
Radixsort nebo bucketsort - zakladni princip je stejne ten samy. Mas nejake kbeliky, do kterych neco rozhazujes.
bredy 31.10.2006 20:24  591
http://en.wikipedia.org/wiki/Counting_sort
norfin Norfin 31.10.2006 20:24  590
King [589]: ano, dekuji za podnetnou a prinosnou informaci. Chyba byla pouze v neadresaci a spatne formulaci, takze to zkusim jeste jednou.

Kdokoliv, Gumysh: nebrali jsme nahodou to, co popisuje Bredy na cislech, jako Bucketsort na retezcich? Vsadil bych na to vlastni botu, ze ten referat na datovkach byl nadepsany takto. Uz si to ale nepamatuju (je to pet let zpatky).
king King Born to be king - ... 31.10.2006 20:12  589
http://en.wikipedia.org/wiki/Bucket_sort
http://en.wikipedia.org/wiki/Radix_sort
a doma stokrat opsat:
naucim se hledat na webu nez budu publikovat do fora...
norfin Norfin 31.10.2006 19:34  588
Bucketsort je to, co popsal Bredy, ne?
king King Born to be king - ... 31.10.2006 18:49  587
decide: to byl jen odhad - mozna zkus ten nejvetsi...
jde o to, aby pivot byl dostatecne velky, aby si nevybral prilis male cislo, to by ti bylo nanic... tim ze ho vyberes z vice cisel zmensis pravdepodobnost ze se tohle stane...

kdokoliv: BucketSort zni povedome?
decide 31.10.2006 17:26  586
pivot?Kingu, ještě ke quicksortu. Říkals, že mám vybrat náhodně 5 pivotů a pak zvolit druhý. Chápu to správně takto?:
1)vyberu pět náhodných prvků aktuálně tříděné části pole
2)z nich vezmu druhý (nejlepš)největší
Vysvětli, prosím, proč to mám dělat zrovna takhle, dík.
kdokoliv Kdokoliv Nevidím důvod dělat cokoliv bezdůvodně. - http://kkl2401.wz.cz 31.10.2006 16:19  585
Aha, tak to pardon, popletly se mi pojmy. Ale urcite jsme tomu rikali jeste jinak nez counting sort, kdybych si ale vybavil jak.
bredy 31.10.2006 16:03  584
Kdokoliv 671To co jsi popsal je Counting Sort.

Radix sort se u integeru dela tak, ze cisla seradim nejprve podle prvni cifry (nejnizsi vpravo), potrebuju tedy 10 hromadek a podle cifry plnim hromadky. Pak to sesbiram a seradim to podle dalsi cifry a nakonec to seradim podle posledni cifry. Pokud jsem hromadky vzdy sbiral ve stejnem poradi, dostanu serazenou posloupnost.

(Uz jste nekdy radili 500 faktur podle cisla? myslim rucne)
decide 31.10.2006 14:14  582
Máš pravdu. Existují sice extrémní příklady, kdy to budu muset projít pětkrát celé, ale nebudou asi v reálu nastávat. Až uvidím rozložení hodnot, ještě o tom pouvažuju, ale řekl bych, že ten radix nakonec alespoň teoreticky prohraje. Jestli se dokopu k jeho implementaci a praktickému srovnání, dám vědět, jak to dopadlo. Ještě jednou dík.
king King Born to be king - ... 31.10.2006 12:33  581
ten radix ale nemusi delat cely!
staci ti jen setridit to podle PRVNICH x cifer, respektive napred podle poctu mist, pak staci setridit jen ten pocet kde je k-ty prvek, a ten musis tridit jen do te doby, kdy nebudou vsechna cisla stejna...

ale uznavam, ze quicksortFirstK se asi bude psat lepe... ;)

[ 857 ] <Novější  <<<Nejnovější  Nejstarší>>>  Starší>  

(c) 2001-2011 Lopuch.cz   
Kontakt