Programování - diskusní klub na Lopuchu

Registrace nového uživatele

Návod

Kluby

Archív Lopuchu

Lopuch.cz

Já Vánoce juchuchu
oslavím na Lopuchu!

Lopuch.cz

	Klub Programování [ŽP: neomezená] (kategorie Programování) moderuje tvx.
	Archiv

Nastavení klubu

Nastavení práv

Homepage

Anketa

[ 857 ]

<Novější <<<Nejnovější Nejstarší>>> Starší>


	31.10.2006 12:17	578
	Možná bych se úplně nejdřív zamyslel nad otázkou, jestli budeš vybírat z dat už existujících v paměti, nebo jestli je budeš teprve dostávat odněkud. Pak by totiž stálo za úvahu to dělat průběžně při příjmu dalšího prvku.


	King Born to be king - ... 31.10.2006 11:04	577
	O(7*N) je kapku raritka, konstanty se vetsinou nepocitaji.. ;) jinak ty to nepotrebujes tridit cele, pokud si muzes vsadit na to, ze vsech 20 nejvyssich hodnot bude mezi 100100 a 101000, tak si klidne udelej pole 900 prvku a nahazej to tam, a mas to linearne, primo... pak jedine musis osetrit nejhorsi pripad kdy se ti to tam netrefi a jeste budes muset dohledavat zbyle prvky...


	31.10.2006 10:49	576
	mluvím o verzi radixu, který se dělá postupně pro jednotlivé cifry


	31.10.2006 10:47	575
	oprava1 000 000 .. 1 000 100


	31.10.2006 10:46	574
	Ohledně radixu, hodnoty budou zhruba 0..10000 poměrně hustě a pak něco jako 100000..100100 všechny: Takže pokud řekneme, že to mudou max sedmimístná čísla, radix by to měl za O(7*N) setříděno celé?


	Kdokoliv Nevidím důvod dělat cokoliv bezdůvodně. - http://kkl2401.wz.cz 31.10.2006 09:48	573
	Gumysh [572]: Zdravicko, tak Tebe bych tu vazne necekal. :-) Co prehlizim za problem s tim radixem? Mne totiz prijde, ze ten se neda napsat ani efektivne, ani neefektivne, ze proste zalezi na tom, jak moc toho vis o datech - jestli vis aspon tolik, ze si to vubec troufnes pouzit, nebo nevis. Jinac linearnimu pruchodu pres vstup se nevyhnes nikdy, to je celkem jasny :-), a zaverecnemu pruchodu od minima do maxima (ktera si muzes snadno pamatovat) taky ne, takze jde jenom o to zvazit, jestli Ti to za to stoji. A naopak mi teda prijde, ze implementace radixu je pomerne trivialni a primocara, tu haldu (pokud teda na to neni nejaka knihovna) kdybych si implementoval sam v poli, tak bych si prinejmensim musel na kousek papiru nakreslit takovy ty prepocty, na kterych pozicich hledat syny/otce prvku. :-)


	31.10.2006 09:20	572
	Ta halda je asi vazne nejlepsi moznost - zvlast pokud planujes to delat nejak casto a opakovane, tak asi nic moc lepsiho nevymyslis. Ten radix sort ma sanci byt asymptoticky lepsi, ale efektivni implementace neni v porovnani s haldou vubec jednoducha (a tak trochu pochybuju, ze v praxi - pokud data nebudou zvlast obludna - by vubec stala za to).


	Kdokoliv Nevidím důvod dělat cokoliv bezdůvodně. - http://kkl2401.wz.cz 31.10.2006 08:13	571
	Jeste by se dalo uvazovat, kdyz to jsou ty integery, o variante radix sortu, tedy za predpokladu, ze ty hodnoty nejsou z prilis rozsahleho intervalu. (Pro upresneni, co je radix sort - chceme-li setridit hodnoty 15, 7, 2000, 7, 4 a 31, udelame to tak, ze si vyrobime pole od nuly do tri tisic (treba, proste podle predem znamych hranic) a vsude zapisem nulu. Pak postupne na polickach 15, 7, 2000, 7, 4 inkrementujeme hodnotu - to je linearni vzhledem velikosti vstupu. Na zaver jednoduse projdeme pole zleva a koukame se, kde je cislo ruzne od nuly - tam pozname, ze byl nejaky ze vstupnich prvku (pripadne ze jich takovych bylo vic). Tahle faze je linearni vzhledem k rozdilu mezi maximem a minimem.)


	31.10.2006 08:03	570
	Dobře hledá! Díky.


	King Born to be king - ... 31.10.2006 01:46	569
	kdo hleda, najde http://en.wikipedia.org/wiki/Selection_algorithm#Selecting_k_smallest_or_largest_elements


	King Born to be king - ... 31.10.2006 01:44	568
	ad 1) postavis haldu - N, odebrani vrcholu - okamzite, reorganizace haldy - logN, tedy neni to MN ale N + MlogN ad 2) quicksort v kazde fazi rozdeli pole na dve casti - menis nez pivot a vetsi nez pivot, kdyz vetsich nez pivotu bude alespon 20, nemusis se vbec zabyvat tou druhou skupinou ad 3) NM neni dobra slozitost, linearne jde najit i prostredni prvek, myslim ze by slo ten algoritmus upravit tak, aby nehledal prostredni, ale K-ty (tedy 20), vsech top 20 pak dostanes rovnou v prubehu algoritmu


	31.10.2006 01:31	567
	Výběr nejlepších prvkůdiky za takovou rychlou reakci. 1) Nemám to teď přesně srovnané postavením haldy dostanu nejlepší prvek do kořene, odeberu ho a co dál? Totéž znovu M-krát? čiže náročnost asi O(M*N) 2) Tomu moc nerozumím, jak poznám ty, co mě nezajímají? 3) hmm tomu zatím taky nerozumím, uvidíme co najdeš, ještě bych rozuměl lineárnímu hledání maxima to je O(N) a mohu to provést M-krát To co jsem psal já by mělo mít náročnost do O(N lg2(M)), ale je v tom posuvání těch p-M-2 prvků nějakým memcpy či čím, což není úplně levné, ale zas tak hrozné to pro malé M asi není, nedokážu to posoudit


	King Born to be king - ... 31.10.2006 01:12	566
	moznostico me ted jen napadlo: 1) postav si z toho haldu a odeber 20x vrchol - da se O(N) 2) modifikuj quicksort tak, aby se nesnazil setridit ty zaznamy co te nezajimaji (tady je dulezity vyber pivota - kdyz jich vemes 5 nahodne a vyberes druhy, mohlo by to vypadat slusne) - tady si netroufam na slozitost 3) pouzij neco jako je linearni algoritmus na hledani medianu (zkusim jeste najit)


	31.10.2006 00:39	565
	Výběr nejlepších prvkůAhoj. Mám pole A o N(=400) prvcích různých hodnot(struktura s položkou VALUE typu integer), resp. pointerů na ně. Chci vybrat M (20) nejlepších (podle VALUE) a uložit do cílového pole B. Potřebuju co nejefektivnější algoritmus, protože to budu dělat velmi často. Zatím nejlepší, co mě napadlo je. Napadá vás něco efektivnějšího: 1. Vezmu prvních M prvků pole A a vložím je do B 2. Setřídím B a zapamatuju si hodnotu nejmenšího prvku Vmin 3. Pro ostatní prvky A, tj. i=M..N-1 dělej if a[i].Value>Vmin { půlením intervalu najdi pozici p v poli B, kam prvek patří posuň prvky p..M-1 o jeden doprava na pozici p dej a[i] nastav Vmin=B[M-1] }


	King Born to be king - ... 29.10.2006 18:08	564
	tady hrozne zalezi na tom jakej mas problem, jinak na backtracking existuje spoustu figlu na vylepseni (backjumping, backmarking apod)... holt se musis trochu rozepsat - je jedno v cem to pises, ale neni jedno o jaky problem jde...

[ 857 ]

<Novější <<<Nejnovější Nejstarší>>> Starší>


(c) 2001-2011 Lopuch.cz Kontakt