Malá soutěž v programování - aktualizace

vložil Radek Červinka 15. července 2010 23:17

Zkusíme to jinak. Nechal jsem se inspirovat v zahraničí a uděláme takovou malou soutěž. Já navrhnu zadání (dostatečně lehké) a Vy zkusíte poslat implementaci části programu, která bude provádět zadání. Pro normálního programátora cca 1-2 hodiny práce. Doufám, že to zkusíte.

Cílem je porovnat různé řešení a hlavně začátečníkům ukázat jak to dělají jiní. Budou vyhlášeni dva vítězové:

  • nejrychlejší řešení (tj. program s nejvyšší rychlostí)
  • cena poroty (to jako já :-)) za eleganci nebo čistotu a tak podobně, inspirace začátečníkům

Druhá cena nemusí být vyhlášena (málo účastníků, autor už vyhrál první cenu …).

Uzávěrka je 29.7.2010 23:59. Řešení zasílejte přes kontaktní formulář.

Pravidla:

  • nesmí se měnit rozhraní uvedené v šabloně
  • výsledek bude kompilován na Delphi 2010, tj. můžete použít cokoliv co Delphi nabízí (v případě, že Váš kód nepůjde přeložit, lehce ho upravím - tedy pokud to dokáži - ale to snad nebude problém)
  • assembler není zakázán, ale takový kód nikdy nevyhraje cenu poroty
  • nesmí se používat globální proměnné kromě uvedených v šabloně
  • vlákna povolena (ale v tomto úkolu asi na nic), inline taky, optimalizace taky, prostě cokoliv
  • špatný výpočet (výsledná hodnota je tajná) nebo zacyklení program samozřejmě diskvalifikuje

Ceny:

  • autor vítězného kódu bude uveden spolu s jeho kódem
  • nemůžu nabídnout nic jiného než PDF verzi delphi.cz (prodává se za 150,-)
  • nově i hrneček

Zadání

Implementujte naznačenou funkci CountDigit tak, že převezme předaný text a provede na něm tyto operace:

  • 1) pokud je znakem číslo 0 - 9, tj. ASCII hodnoty čísla nikoliv bajty 0 - 9, připočte hodnotu čísla (tedy pro znak 5 připočte číslo 5)
  • 2) jiné znaky ignoruje
  • 3) pokud po popsaném sečtení všech znaků výsledné číslo více než jednociferné, tj. např. číslo 13 je proveden součet jeho číslic, tj. 1+3=4 (v podstatě bod 1). Toto se opakuje dokud nezůstane jednociferné číslo (např. 6). Tato hodnota se vrátí - tj. číslo 6 nikoliv znak '6'.

Příklad

Máme 456h7896 2. Tj. 4+5+6+7+8+9+6+2 = 47 -> 4+7 = 11 -> 1 + 1 = 2. Výsledek je číslo 2.

Nápověda

Pozor na předávané hodnoty, hodně se tak dá optimalizovat. Prohlédněte si vstupní data, můžete tak něco ušetřit (všechna data jsou na jednom řádku - jeden řádek textu a ten má rozumnou délku). TStringList je použit schválně.

Data

Stáhněte si soubor data.zip, po rozbalení vznikne data.txt. Tento soubor bude použit i pro výsledný test. Snad jsem na nic nezapomněl.

Aktualizace - demo projekt ke stažení projekt.zip

Šablona

    1program Project1;
    2{$APPTYPE CONSOLE}
    3{$RTTI EXPLICIT METHODS([]) PROPERTIES([]) FIELDS([])}
    4{$STRINGCHECKS OFF}
    5{$INLINE ON}
    6{$O+}
    7
    8uses
    9  Sysutils,
   10  windows,
   11  classes;
   12
   13function CountDigit(const lst: TStrings):Integer;
   14begin
   15//  Result je výsledek
   16end;
   17
   18var
   19  lst: TStringList;
   20  i:Integer;
   21  tick, tickend: Cardinal;
   22  iResult: Integer;
   23begin
   24  lst := TStringList.Create;
   25  try
   26    lst.LoadFromFile('data.txt');
   27    tick:= GetTickCount;
   28    iResult := 0;
   29    for i := 1 to 10000000 do
   30      Inc(iResult, CountDigit(lst));
   31    tickend := GetTickCount;
   32    writeln(Format('Result = [%d], Time = [%d]', [iResult, tickend - tick]));
   33  finally
   34    FreeAndNil(lst);
   35  end;
   36end.


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

Tagy: , ,

soutez

Komentáře

16.7.2010 18:27:49 #

tw1ster

Ahojte,
len tak zo zvedavosti som si to vyskusal a moj cas sa pohybuje do 9500 :(
Optimalizacia nikdy nebola nikdy moja silna stranka... Ake casy sa Vam podarilo
dosiahnut?

tw1ster

16.7.2010 21:31:03 #

radekc

To je tajne, a hlavne je to zavisle na rychlosti procesoru. Takze to nelze takto rict.
Ale poslete svoje reseni.

radekc

23.7.2010 10:03:04 #

Radek V.

Na kolik to reseni musi byt univerzalni a pocitat se zmenou zadani ?

Protoze nejrychlejsi resenim pro fixne dane zadani je si to spocitat bokem a vracet pouze znamou hodnotu :-D

Radek V.

23.7.2010 10:15:08 #

radekc

Řešení musí být univerzální, jediné s čím se dá počítat je, že data budou na jednom řádku, a bude jich řádově stejné množství. V pravidlech je, že se nesmí používat globální proměnné, a to že by si to někdo spočetl na papíře mne ani nenapadlo :-D.

radekc

23.7.2010 10:54:47 #

Radek V.

co by clovek neudelal pro hrnek z davnych dob :-D Ksiltovka s logem Borland uz odesla do vecnych lovist a desnik Imprise taky pomalu doziva

Moje reseni mas v poste

Radek V.

23.7.2010 15:13:35 #

tjantac

Můžete prozradit na jaké HW konfiguraci a jakém OS se bude daný kód testovat?

Metodika testování není příliš ideální! GetTickCount je funkce vracející reálný čas, nikoliv čas strávený procesorem nad danou úlohou. Výsledek je tedy velmi ovlivněn aplikacemi bežícími na pozadí. Doporučoval bych raději použít funkci GetProcessTimes, která vrací skutečný čas procesoru strávený aplikací. Nicméně i tato funkce není v dnešní době příliš objektivní (turbo mody procesorů, nopy při přehřátí, atp...).

Schválně jsem testy prováděl několikrát na různých strojích v různých časech a vždy jsem se dobral k řádově jiným výsledkům. S GetTickCountem byla odchylka tak veliká že nebylo možné rozeznat rychlost různých verzí kódu. S GetProcessTimes jsem získával o několik řádů stabilnější informace, nicméně i na čistém PC Core2Quard 2,5GHz jsem dostal během 2 hodin rozdílné výsledky stejného kódu lišící se o cca 20%

Hledal jsem jak měřit skutečné cykly procesoru při vykonávaní dané metody ale bohužel jsem nic nenašel. Nevíte někdo jak na to?

tjantac

23.7.2010 15:28:10 #

radekc

Pro výsledný běh zkusím zabít co nejvíce procesů - já vím - GetTickCount není ideální, ale zatím nikdo nic lepšího nenadhodil.

Core2Duo, Win XP SP3, nastavené řízení spotřeby na Maximum Performance.
Rozdíly pak dělají max. cca 100 jednotek, možná bude problém s tím řízením spotřeby u tebe.

Zkoušel jsem i nastavit SetThreadPriority nebo SetProcessPriority a moc to nepomahalo.

Ještě můžeš zkusit profiler - je tu na něj odkaz někde mezi články.

radekc

23.7.2010 16:39:16 #

Radek V.

mam obavu ze jina metoda nez zprumerovani nekolika vysledku nebude rozumna

Pro detailnejsi analyzu by se dal na (Vista a vejs) pouzit napr. Windows Performance Toolkit . Kdyby se prevedly mapy na dbg tak by to podporovalo i stackwalker a tudiz by to bylo schopno ukazat info pouze o procedure (pokud ovsem nebude inline)

Ale myslim ze to opravdu nebude nutne, pro hruby vyber staci soucasna verze a pro zvyseni presnosti se pak muze udelat uprava ktera to zavola vickrat a zprumeruje

Radek V.

23.7.2010 16:45:59 #

Tomáš Jantač

Souhlasím, proto jsem také udělal ten test cca 10x i když je to to samé jako bych přidal jeden řád do testovací smyčky.

Jinak jak jsem již psal, určitě by pomohlo pouížvat funkci GetProcessTimes a to zvednutí priority bych také v případě testu provedl. Vše viz můj kód.

Windows Performance Toolkit? ups... tak na to se budu muset kouknout. :p

Tomáš Jantač

23.7.2010 16:49:09 #

Tomáš Jantač

ha, bude jen jeden řádek...
škoda měl jsem to optimalizované pro více řádků..
(takhle budu muset zakomentovat jednu smyčku a poslat funkci znovu, ale zase to bude -30ms)

Tomáš Jantač

23.7.2010 16:51:40 #

Tomáš Jantač

Návrh pro příště:

nebylo by na škodu dělat testy průběžně a zveřejňovat pořadí, myslím že by to účastníky pěkně vyhecovalo. :o)

Tomáš Jantač

23.7.2010 16:54:48 #

Radek V.

to nezni spatne ale pak by Radek musel omezit prijem novych verzi :-D Jinak nebude delat nic jineho

Radek V.

23.7.2010 16:59:42 #

Tomáš Jantač

No některé věci jdou i trošku zautomatizovat. A jinak bych to viděl, maximálně 1 verze denně nebo i za pár dnů, to by bohatě stačilo. Akorát by musel pořád zabíjet nějaké aplikace.

Tomáš Jantač

23.7.2010 22:19:46 #

Jirka Koula

Odfiltrování okolních vlivů by se snad dalo docílit "baťákem", co by pouštěl řešení jedno po druhém, když se to udělá ve smyčce třeba desetkrát a zprůměrují¨výsledky per uživatele, musela by být docela smůla, aby se něčí řešení oproti jiným výrazně častěji trefovalo do chvil, kdy procesor zrovna dělá i něco jiného náročného.

A kdyby nestačilo desetkrát, tak klidně stokrát, když už to bude jednou napsané, počet smyček i soutěžících programů se dá regulovat prakticky zadarmo (a příslušný vyhodnocovací program by se dal použít i při dalších soutěžích :)).

Jirka Koula

24.7.2010 10:03:44 #

NoName

neviem čo riešite keď sa jedná o algoritmus a chcete odfiltrovať vplyv tak si to skompilujte vo free pascale pre dos a spustiť v dose ... a hotovo .

NoName

25.7.2010 22:45:18 #

Milan395

1. Přiznám se, direktivy překladače moc nenastavuji (možná chyba), ale na mém D5Prof ty tři prostřední předepsané nefungují (=při kompilaci se vrátí chyba "Invalid compiler directive") - tak jsem je prostě zapoznámkoval. Nic jiného než D5Prof prostě nemám.

2. V jednom z předchozích příspěvků padlo, že ostrý soubor data.txt bude mít pouze jeden řádek. Řekl bych podstatná informace, která měla asi zaznít už v zadání. Já s ní tedy ale ve svém kódu počítám. I tak mi jde hlavně o to, abych se jen porovnal s profíky, protože se považuji za amatéra.

3. Poprvé jsem použil kontaktní formulář (na odeslání svého řešení), jsem ale nějak na rozpacích - netuším, jestli se moje řešení podařilo odeslat - po zmáčknutí "Poslat" zůstal obsah formuláře nezměněn, jen se vymazalo pole s přiloženým souborem? Pokud moje řešení (podle mého emailu) nedošlo, prosím o radu jak tak učinit, aby doputovalo na místo určení.

Milan395

25.7.2010 23:42:01 #

radekc

je to divné, ale lze použít i mail radekc zav delphi.cz.

radekc

25.7.2010 23:43:32 #

radekc

Byl přidán článek s průběžným pořadím.

radekc

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