Výsledky 2. soutěže

1.3.2011 0:22:35 #

Dekuji Radkovi za zajimavou soutez. Zaroven blahopreji vitezi. Fakt je, ze kdybych dal na kolegu driv, ktery si myslel, ze i na procesoru kde jdou spustit jen dve vlakna zaroven, jde zaridit rozdeleni ulohy nejen na 2 casti, ale na 4 (coz v podstate vystihl i p. Sova jeho resenim), tak jsem mohl byt jeste i o kousek lepsi. Muj posledni kod (poslany jen na overeni rychlosti uz davno mimo limit a po terminu :-) ) dava na Radkove PC vysledek jeste o malinko lepsi.

HonzaK

1.3.2011 14:31:38 #

Trochu jsem pomahal s algoritmem Jirky Jelinka, to jen aby se vedelo kam patrim a trosku mi prijde nefer, ze lze pouzit ASM. Trosku proto, ze sam ho neumim a taky proto, ze tak nejak citim, ze by to melo byt o Delphi/Pascalu a algoritmizaci jako takove. Ten ASM do toho zanasi uplne jinej rozmer. V podstate se cela soutez degraduje na ASM, protoze v pascalu jsou proste limity, ktere ho oproti ASM znevyhodnuji. Mam radost, ze Jirka obsadil delene "prvni" misto v PUREPASCAL a taky zes rozhodnul o cene "poroty". Ale stejne me malicko ty assembleristi stvou ;-)

NkD

1.3.2011 16:30:40 #

to NkD: priste se nekdo ozve, ze je nefer, ze se pouziva rucne psany kod. Mel by se zakazat a pouzivat jen to, co se namysuje tahanim komponent :-)

Assembler je jen dalsi programovaci jazyk a na rozdil od high level jazyku je IMHO velmi jednoduchy. Zakladnich instrukci je jen par. Staci se naucit nekolik jmen instrukci a zpusob zapisu operaci s pameti. Jen zpusob premysleni a pristup k programovani je treba dost zmenit. Pokud se prestanes ASM bat, muzes ho vyuzit i jinde (jednocipy apod). Pravda, dnes pouziti ASM ve vetsine pripadu neni nutne (ci je i nezadouci - prenositelnost kodu). Vykon PC je vetsinou dostatecny.

Ber to taky tak, ze v ASM mas mnohem vetsi prostor k tomu, jak problem naprogramovat (ukazalo se, ze pro dnesni CPU to plati obzvlast), takze, ti kdo programovali v ASM, do toho pravdepodobne investovali vetsi mnozstvi casu, aby nasli tu optimalni variantu, cili si to umisteni v soutezi zaslouzi.

PS: IMHO reseni Jirky Jelinka ma jeste prostor ke zrychlovani i v cistem Pascalu

Dalibor Toman

1.3.2011 16:35:28 #

NkD: taky mne stvou lidi co jsou chytrejsi nez ja ;-) a protoze jsem uz vyrostl ze skolky (kde to slo resit nakladackou) beru to aspon jako impulz k dalsimu studiu :-) Pocit kdyz se pak "dilo" podari stoji za to.
... i kdyz ted naposled mi vydrzel asi 4s nez sem zjistil ze je i rychlejsi reseni (byt publikovane po uzaverce).
Takze abych si cenu aspon trosku zaslouzil (a aby z toho neco meli i assemblerem nedotceni) slibuji ze svuj kod radne okomentuji a vysvetlim ;-)

radomirs

1.3.2011 20:13:10 #

Blahozelam vsetkym zucastnenym.
Pekne, pekne.

Radim

1.3.2011 20:30:20 #

Vypíchnul bych dva momenty, které mě ve vítězných řešeních opravdu zaujaly:

1) Struktura tabulky délek a počtů - mít to jako jednu tabulku s recordem a ne dvě samostatné. Tím se vysvětluje, proč jsem musel pracně rozlišovat mezi koncovým a normálním tagem - při dvou samostatných tabulkách dostává těžce na frak cachování a tříbajtový "hash" je neskutečně pomalejší proti dvoubajtovému.

2) Geniální myšlenka rozdělit každý thread na dvě samostatné části a tím kapitalizovat na tom, jak funguje pipeline v procesorech. Ono je to svázané s tím prvním bodem (při dvou samostatných tabulkách se začne nedostávat registrů), ale proč nepřiznat, že mě to vůbec nenapadlo.

Na druhou stranu vůbec nechápu, jak to, že je to vítězné pascalské řešení tak rychlé. Fakt to tam nevidím. Podle mých pokusů bych pro tohle řešení čekal čas někde u 50-60 milisekund, rozhodně ne těsně nad 30.

pepak

2.3.2011 20:57:07 #

Pepo, on nakonec sel rozdelit kazdy thread do 3 casti, na mem PC to udelalo zmenu z 18ms na 15ms. U Radka a i na jinem me dostupnem PC to uz bylo bez rozdilu proti rozdeleni jen do dvou casti.

HonzaK