Soutěž 3 - výsledky

vložil Radek Červinka 21. března 2012 20:28

Výsledky soutěže včetně zdrojových kódů.

aktualizováno:

  • 21.3.2012 - ukončeno
  • 27.3.2012 - Neuromancer přidal soubor s vysvětlením algoritmu stáhnout

Demo projekt:

originální implementace - čas: 18868

Pořadí

  • (diskvalifikováno pro použití krátkého stringu ) Jiří Jelínek & NkD (Delphi 7 - 3 pokus)- Jiří Jelínek (Pure Delphi) - čas: 425
  • Neuromancer (Delphi XE2), tabulková verze - Neuromancer (ASM) - čas: 470
  • Igor Gottwald (x pokus - mimo) (Delphi XE2)- Igor Gottwald (Pure Delphi) - čas: 918
  • Tomáš Koutný (Delphi 2006) - Tomáš Koutný (ASM) - čas: 1041
  • Jiří Jelínek (Delphi 7 - 2 pokus)- Jiří Jelínek (Pure Delphi) - čas: 1176
  • Zdeněk Vašků (x pokus - mimo) (Delphi XE2)- Zdeněk Vašků (Pure Delphi) - čas: 1271
  • Tomáš Kořínek (Delphi XE2)- Tomáš Kořínek (Pure Delphi) - čas: 1372
  • Vladimír Bárta (Delphi 2009)- Vladimír Bárta (Pure Delphi) - čas: 1669
  • Neuromancer (Delphi XE2), bez tabulková verze - Neuromancer (ASM) - čas: 2027
  • Kubidlo (2 verze) (Delphi XE2)- Kubidlo (Pure Delphi) - čas: 2048
  • Tomáš Koutný (Delphi 2006) - Tomáš Koutný (Pure Delphi) - čas: 2324
  • Igor Gottwald (3 pokus) (Delphi XE2)- Igor Gottwald (ASM) - čas: 2605
  • David Kovařík (Delphi 2010)- David Kovařík (Pure Delphi) - čas: 3347
  • Zdeněk Vašků (3 pokus) (Delphi XE2)- Zdeněk Vašků (ASM) - čas: 3378
  • Jiří Milička (Delphi XE2) - Jiří Milička (ASM) - čas: 3753
  • Radek Červinka (Delphi XE2) - Radek Červinka (Pure Delphi s kouskem ASM) - čas: 4112
  • Igor Gottwald (3 pokus) (Delphi XE2)- Igor Gottwald (Pure Delphi) - čas: 4428 (v Delphi XE2/64bit je to ještě kapánek lepší)
  • Radek Červinka (Delphi XE2) - Radek Červinka (Pure Delphi) - čas: 5837

No vítěz je znám. Cenu poroty získává Igor Gottwald nejen za elegantní kód, ale i za nápad provádět alokaci řetězce jen když je třeba (velikost se nezměnila), což je špinavý trik, ale v rámci povolených. Výherce budu kontaktovat.

Díky moc všem, a speciálně těm co kód komentují :-). Jste opravdu dobří. Nebyl jsem schopen procházet všechny kódy (nebo je pochopit - hlavně v případě Neuromancera jsem si připadal jako úplný blbec), ale i to co jsem viděl bylo zajímavé. Několik lidí mělo první verzi v ASM a pak zjistilo, že čistý PAS s tabulkami (hodně často inspirované optimalizovanou verzi _IntToStr32 z vyšších verzi Delphi - myslím, že pochází z projektu FastCode) byl prostě rychlejší.

Doufám, že si to zkusilo i pár běžných programátorů - i bez zaslání do soutěže. A doufám, že to byla změna a zábava.

Ještě pár lidí napsalo, že kód kompilovaný v D7 byl 2x - 5x pomalejší než D2010 nebo XE2. Určitě na to má vliv zarovnání, ale i mnohem lepší optimalizátor (a to prý XE3 bude ještě brutálnější).

Poznámka: Vysvětlí mi někdo co je zase tohle? To je zase nějaké abraka dabra jako minule? (Tomáš Koutný)

const
  remtable:array[0..15] of integer = (0, 1, 2, 2, 3, 3, 4, 5, 5, 6, 7, 7, 8, 8, 9, 0);
…
  r := ($19999999*i + (i shr 1) + (i shr 3)) shr 28;
  r := remtable[r];
  i := ((i - r) shr 1)*$CCCCCCCD;


Nabízíme Delphi školení na různá témata, primárně ve Vaší firmě.

Tagy:

soutez

Komentáře

22.3.2012 2:23:27 #

NkD

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 9:38:51 #

Radekc

Já jsem tě zapomněl uvést jako spoluautora u hlavního řešení - opraveno.

Mimochodem když jsem říkal první návrh zadání kolegovi tak se mne zeptal co na tom chci optimalizovat a to si myslím, že je velmi schopný programátor.

Radekc

22.3.2012 10:23:08 #

Neuromancer

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:05:44 #

Radekc

Podle všeho máš pravdu, nevšiml jsem si - počkáme co na to autor.

Radekc

22.3.2012 11:08:18 #

NkD

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 #

Jiri Jelinek

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

Jiri Jelinek

22.3.2012 11:25:35 #

Zdeněk Vašků

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:32:28 #

Radekc

Takže jestli už nikdo nemá další námitky tak vítězem je Neuromancer se svým voodoo kódem. Zkusím ho kontaktovat o adresu pro zaslání ceny.

Radekc

22.3.2012 11:35:56 #

Zdeněk Vašků

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 #

Jiri Jelinek

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 #

tomk

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 #

Tomáš K.

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 #

Igor Gottwald

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 #

NkD

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 #

Igor Gottwald

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 #

NkD

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 13:38:12 #

Radekc

2 NkD: To ano, ale
a) nejde to pak férově porovnávat
b) v reálné aplikaci Vaše řešení by bylo zatíženo konverzemi při volání
c) i tak si myslím, že není špatné a opravdu by mne zajímalo jak by si vedlo s dlouhymi řetězci. Jirka napsal 3x pomalejší, ale i tak by mu patřilo místo někde v čele, což je moc pěkný výsledek - nechcete mi ho poslat? Bych ho tam zařadil.

Radekc

22.3.2012 22:17:45 #

Neuromancer

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 #

Igor Gottwald

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

22.3.2012 22:47:49 #

Radekc

To by bylo opravdu zajímavé - už se těším a rád to uveřejním, ale než hůlčičku mi to připomíná kalašnikov.

Radekc

23.3.2012 14:50:40 #

NkD

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 #

Neuromancer

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

27.3.2012 22:13:02 #

Radekc

Odkaz na soubor jsem přidal do článku - díky.

Radekc

29.3.2012 18:54:46 #

NkD

2Neuromancer: mega, naprosto paradni. Diky.

NkD

12.4.2012 12:47:33 #

Igor Gottwald

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

Igor Gottwald

Komentování ukončeno

Naše nabídka

Partial English version.

MVP
Ing. Radek Červinka - Embarcadero MVP
profil na linkedin, Twitter:@delphicz

Nabízím placené poradenství a konzultace v oblasti programování a vývoje SW.
Dále nabízíme i vývoj speciálního software na zakázku.

Neváhejte nás kontaktovat (i ohledně reklamy nebo burzy práce).

Pokud chcete podpořit tento server libovolnou částkou, můžete použít PayPal. Moc děkuji.

Delphi Certified Developer

O Delphi.cz

Delphi je jediný moderní RAD nástroj podporující tvorbu nativních aplikací pro platformu Win32, Win64 , Mac OSX a na iPhone a Android (s výhledem na další platformy díky FireMonkey) na současném trhu (včetně Windows 8.1).

V současnosti je světová komunita přes dva miliónů vývojářů.

Delphi.cz je nezávislý portál pro uživatele Delphi. Portál není koncipován pro úplné začátečníky, i když i ti se zde nebudou nudit, ale spíše na programátory, kteří již něco znají a chtějí své znalosti dále rozvíjet a sledovat novinky.

Anketa

Poslední komentáře

Comment RSS