Soutěž 3 - výsledky

22.3.2012 2:23:27 #

Tak jsme si vsichni v tichosti odsoutezili... :-D  Ja jen... chtel bych podekovat Radkovi za genialni zadani, ktere provokovalo k optimalizacim. Snad jen priste dej kratsi termin od vyhlaseni souteze do ukonceni. Kdybys videl kolik nam to s Jirkou Jelinku sezralo casu :-D

NkD

22.3.2012 10:23:08 #

Dovolil bych si poznamenat, že vítězné řešení není ekvivalent původní předložené funkce, ale došlo ke změně parametrů funkce, konkrétně místo dlouhých stringů se používají krátké {$H-} {$P-}. Rozhodnutí co s tím nechám na porotě ;-)

Neuromancer

22.3.2012 11:08:18 #

Namitce od Neouromancera rozumim. A jestli ma Neuromancer takhle rychle reseni o pro "nekratky" String tak to smekam. Osobne to sice nevnimam jako poruseni pravidel, ale je pravda ze nase reseni na tom stoji a pada. Takze je to na posouzeni zadavatele a porotce v jedne osobe ;-)

NkD

22.3.2012 11:17:54 #

Take uznavam namitku, pokud musime dodrzet pouziti AnsiStringu, tak nase reseni neni samozrejme nejrychlejsi.

Jiri Jelinek

22.3.2012 11:25:35 #

Super soutěž, díky Radku.

To Neuromancer:

Ještě by mne zajímalo jetsli jste volal Setlength přímo z asm.

Díky

Zdeněk Vašků

22.3.2012 11:35:56 #

Už jsemto našel ClearStr + NewUnicodeString, je to rychlejší než UniqueStr a Setlength.

Cena Igoru Gottwaldovi je v pořádku. Nikdy by mne nenapadlo, že toto tak pomůže:

if length(s)<>delka then SetLength(s,delka);

Zdeněk Vašků

22.3.2012 11:37:56 #

Bohuzel ze zadani jsem presne neusoudil, ze nemohu vyuzit ShortStringu. Po uprave kodu a vypnuti prislusnych direktiv se celkovy cas prodlouzi vice jak 3-nasobne. Prosim Radka o vyrazeni meho reseni.

Jiri Jelinek

22.3.2012 11:50:25 #

Oba prvni programy jsou kosmicke a kod T. Koutneho asi taky pochazi za StarTreku. A to jde jen o hrnicek.

Z hlediska firemni politiky, se mi nejvice libi optimalizace Igora Gottwalda - inspirovana FastCode. Jeho kod totiz neni write-only; jen pred proceduru staci dat pouze souhrnny komentar. Ten kod je tak kristalove cisty, ze ho zdatny programator - kolega ve firme - pochopi velmi rychle.

To abracadabra je asi univerzalni kod Mossovy podprsenky :)

tomk

22.3.2012 12:16:09 #

procedure UnsignedDivMod10(const n:integer; var q:integer; var r:integer);
const
  remtable:array[0..15] of integer = (0, 1, 2, 2, 3, 3, 4, 5, 5, 6, 7, 7, 8, 8, 9, 0);

begin
    r := ($19999999*n + (n shr 1) + (n shr 3)) shr 28;
    r := remtable[r];
    q := ((n - r) shr 1)*$CCCCCCCD;
end;

V podstatě jde o převedení úlohy dělení 10 na úlohu dělení nejbližším vyšším číslem dělitelným 2, aby bylo možné použít bitový posun.

Máme převést n, pro které platí n=10*q+r. Abychom měli dvě rovnice o dvou neznámých, q = n div 10. Nejbližší vyšší číslo k 10, a zároveň je mocninou 2, je 16. Matematicky se pak dá použít následující trik:

(n*16/10) mod 16 = (r~*16/10) mod 16

kde r = remtable [r~]    

Aby trik platil i pro všech 32 bitů, tak jsou tam korekce shr 1 a shr 3. Takže by se dalo do výpočtu dodělat 2x if, aby to běželo ještě rychleji.

Je to ještě takový "486-trik", na kterém se mi líbí jeho nenáročnost a kompaktní kód (čím menší kód+data na bajty, tím větší šance, že v reálné aplikaci zůstane celý v cache procesoru).

Tomáš K.

22.3.2012 12:34:17 #

Ahoj všem, děkuij Radkovi i Tomkovi za pochvalu za pěkný kód a smekám před Neuromancerem... vážně to ale vypadá jako shluk náhodných čísel a písmen, které shodou okolností dávají pro všechny případy správné výsledky :-)
Obávám se, že takový kód (bez znalosti původní myšlenky) ani nemá cenu zkoušet pochopit, nebo alespoň já se dobrovolně přidávám k předpokládané většině, která to po chvíli marné snahy vzadala. Především MMX/SSE instrukce mi už nic neříkají a musel bych každou zvlášť studovat, co vlastně dělá... Navíc předpokládám, že ta změť čísel je už pořádně předchroupané něco, co bude potřebovat pořádný reverse engineering.
Výsledek je ale impozantní. Na mém počítači jsem musel snížit krok cyklu, aby se to dalo vůbec nějak rozumě měřit. Ze začátku jsem měl podezření, že se vůbec nespustila procedura RunTest :-)
Gratuluji vítězi a čest nám poraženým!

Igor Gottwald

22.3.2012 12:48:48 #

Ja bych se preci jen jeste ozval... byli jsme diskvalifikovani docela rychle ;-) az mi skoro prijde bez rozmyslu. Ja proti tomu nejak moc neprotestuju.. jen je mi to tak trochu lito, protoze v zadani toto omezeni nepadlo AFAIK. Z povahy prikladu je mnohem vyhodnejsi pracovat s kratkym stringem, zvlaste kdyz mame jistotu, ze prevod cisla na string vystaci s byte na znak. Zkratka ja to necitim jako prohresek proti pravidlum. Pravdou je, ze pokud by byl kratky string explicitne zakazan v zadani, nedokazali bychom se dostat takhle nizko s casem. Ale zadani primo vybizi pracovat s kratkym stringem.

Co se tyce naseho deleni  "i div 1000" prevedeno na bitshift, tak jsme cerpali tady a bude to asi lepsi vysvetleni nez kdybych se o to pokusil svymi slovy:

http://www.hackersdelight.org/divcMore.pdf

NkD

22.3.2012 13:02:57 #

To NkD: Z mého pohledu by to bylo diskutabilní řekněme u první verze Delphi, která zavedla WideString jako standardní typ pro řetězec. V dnešní době to ale pozbývá smyslu a naopak řešení ShortString nemá valný smysl, protože jakékoliv praktické využití řešení by v praxi znamenalo mnohonásobné zpomalení kvůli nutným konverzím. Předpokládám, že v roce 2012 už nikdo z nás nepíše programy používající AnsiChar a AnsiString, natož ShortString, vyjma speciálních případů.

Igor Gottwald

22.3.2012 13:32:41 #

2IG: vypichnul bych to: "vyjma specialnich pripadu". Tohle zadani si primo rika o vyreseni specialnim pripadem, protoze to pak muze byt rychle a mnozina moznych znaku je jasna...

NkD

22.3.2012 22:17:45 #

Radekc: Děkuji za uznání námitky. Navrhuji kompromis, hrnek věnuji JJ & NkD a sám se spokojím pouze s odměnou v morální rovině ;-)
Zdeněk Vašků: Volám UStrClr a NewUnicodeString, abych ušetřil vnitřní volání Move v případě Setlength.
Igor Gottwald: Není to tak těžké jak to vypadá, jsou použity obecně známé algoritmy, jenom jsem neměl čas na estetickou úpravu.

Protože mám pocit že je zájem o vysvětlení funkce, pokusím se to cca do týdne nějak zkulturnit a okomentovat.

Neuromancer

22.3.2012 22:42:39 #

To Neuromancer: To by bylo príma... rád se něco nového přiučím. Občas je šikovné mít někde vzadu v paměti po ruce takovou malou kouzelnou hůlčičku, kterou člověk vytáhne v ten správný okamžik a pak se dějí věci. Jako ve Vašem případě :-)

Igor Gottwald

23.3.2012 14:50:40 #

2Neuromancer: o vecne ceny zde vubec nejde... myslim, ze se prave snazim argumentovat a bojovat o normalni vitezstvi, o uznani... ale evidentne nase reseni vnimam jinak nez Ty a Radek a ostatni. Takze to nechme tak, ze nase reseni neni idealni pro pripadne pouziti v produkcnich kodech a i kdyz jsme nejrychlejsi tak jen diky prave teto diskutovane vlastnosti (ShortString). Rozhodne nikam zadne hrnecky neposilej a nic nikam nevenuj. O to tady fakt nejde.
Snad jeste explicitne napisu, ze se nezlobim. Jde proste jen o diskuzi a argumentaci. Nechci vyhrat soutez vztekanim a za kazdou cenu. Rozhodne nechci hrat nejakeho ublizeneho. Nejsem. tecka.

NkD

27.3.2012 2:36:09 #

Teď jsem odeslal verzi s vysvětlivkami a funkčním ekvivalentem v Delphi, snad to bude pochopitelnější.
Více než vlastní soutěž je IMHO zajímavější projekt Division, kde jsou dílčí kusy rychlého dělení.

Neuromancer

29.3.2012 18:54:46 #

2Neuromancer: mega, naprosto paradni. Diky.

NkD

12.4.2012 12:47:33 #

2Neuromancer: To je z tvojí hlavy, nebo vycházíš z nějaké jiné práce? Vypadá to opravdu famózně.

Igor Gottwald