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ší>
označené
neoznačené
rozsah
makak
1.11.2006 11:15
597
razeni vs. trideni
Nechci 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 :-)
1.11.2006 09:41
596
QuicksortFirstK Jak je důležité, míti pivota
Tak 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
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
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.
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.
31.10.2006 20:24
591
http://en.wikipedia.org/wiki/Counting_sort
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
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
31.10.2006 19:34
588
Bucketsort je to, co popsal Bredy, ne?
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?
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
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.
31.10.2006 16:03
584
Kdokoliv 671
To 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)
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
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ší>
označené
neoznačené
rozsah
(c) 2001-2011 Lopuch.cz
Kontakt