<< Nová prodejní akce Embarcadera | Exception dialog >>

Soutěž - výsledky

vložil Radek Červinka 29. července 2010 22:23

Naše malá soutěž je u konce, takže je na čase provést nějaké zhodnocení. Jsem rád, že se zúčastnilo celkem dost lidí a co je ještě lepší, že co člověk to algoritmus, přičemž některé opravdu překvapující. Rád bych všem poděkoval, bylo to velmi zajímavé.

Úplně na začátek malá anketa - snad bude blueboard fungovat.

BlueBoard.cz

Když jsem zadání vymýšlel, uvažoval jsem o třech optimalizacích:

získání řetězce ze string listu
součet dat z řetězce
součet cifer z výsledku

Omlouvám se, že v zadání nebylo, že se nesmí měnit vstupní data - čehož bylo využito ve třech případech, kdy si autoři pak použili stringlist jako cache. Takové řešení mne překvapilo, ale musel jsem je odmítnout. Ale má chyba - špatné zadání.

Ohledně metodiky měření: trošku jsem potunil šablonu (částečně díky jednomu z autorů) aby se mi to lépe hodnotilo, jelikož všechny řešení jsou v jednom souboru, kdy na začátku se nastavila priorita na RealTime a před testováním řešitele se zavolala FlushInstructionCache, což trošku stabilizovalo výsledky měření, i když podle mne rychlost výsledného kódu závisí i na okolních funkcích, což moc nechápu. Každopádně pořadí to nezmění (na předních místech určitě ne) - ale kdyby někdo věděl co s tím, tak napište do komentářů. Data byla lehce editována, takže funkce místo původní hodnoty 1 měla vrátit 3.

    1procedure mRunTest(const sResolver:string; lst:TStringList; p:TTestProc);
    2var
    3  i:Integer;
    4  tick, tickend: Cardinal;
    5  iResult: Integer;
    6  {KernelTime,} UserTime : Int64;
    7  CreationTime1,CreationTime2,ExitTime1,ExitTime2,KernelTime1,KernelTime2,UserTime1,UserTime2:_FILETIME;
    8  H:Cardinal;
    9begin
   10  writeln('Resitel:', sResolver);
   11  H:=GetCurrentProcess;
   12  FlushInstructionCache(h, nil, 0);
   13  tick:= GetTickCount;
   14  GetProcessTimes(H,CreationTime1,ExitTime1,KernelTime1,UserTime1);     // kernelovska funkce - mereni casu procesu
   15
   16  iResult := 0;
   17  for i := 1 to 10000000 do
   18    Inc(iResult, p(lst));
   19
   20  GetProcessTimes(H,CreationTime2,ExitTime2,KernelTime2,UserTime2);     // kernelovska funkce - mereni casu procesu
   21  tickend := GetTickCount;
   22  UserTime:=int64(UserTime2)-int64(UserTime1);
   23  writeln(Format('Result = [%d], Time = [%d], UserTime = [%5.3f]', [iResult, tickend - tick, UserTime/10000000]));
   24//  writeln(lst.Text); // kontrola
   25end;

Takže výsledný běh programu - řešitel "Best of řešení" je kombinací prakticky best of ze všech řešení:

Resitel:Best of řešení
Result = [30000000], Time = [968], UserTime = [0,969]
Resitel:Marek Jurica
Result = [30000000], Time = [1641], UserTime = [1,641]
Resitel:Dalibor Toman
Result = [30000000], Time = [1813], UserTime = [1,813]
Resitel:Tomáš Jantač
Result = [30000000], Time = [2609], UserTime = [2,594]
Resitel:Vladimír Bárta
Result = [30000000], Time = [3781], UserTime = [3,781]
Resitel:Jiri Koula
Result = [30000000], Time = [4672], UserTime = [4,656]
Resitel:Ota Milink
Result = [30000000], Time = [4750], UserTime = [4,734]
Resitel:Aleš Gregor
Result = [30000000], Time = [5266], UserTime = [5,234]
Resitel:David Lebeda
Result = [30000000], Time = [4937], UserTime = [4,953]
Resitel:Petr Kundrata
Result = [30000000], Time = [5094], UserTime = [5,063]
Resitel:Cerda
Result = [30000000], Time = [5437], UserTime = [5,438]
Resitel:Milan Medlik
Result = [30000000], Time = [5141], UserTime = [5,141]
Resitel:Milan Dvorak
Result = [30000000], Time = [5516], UserTime = [5,516]
Resitel:Josef Piskac
Result = [30000000], Time = [5718], UserTime = [5,719]
Resitel:CerdaAsm
Result = [30000000], Time = [6594], UserTime = [6,594]
Resitel:Radek Voltr
Result = [30000000], Time = [5953], UserTime = [5,953]
Resitel:Pavel Gratzer
Result = [30000000], Time = [5860], UserTime = [5,844]
Resitel:Pepak
Result = [30000000], Time = [6015], UserTime = [5,969]
Resitel:Reloader
Result = [30000000], Time = [5719], UserTime = [5,703]
Resitel:Miroslav Logaj
Result = [30000000], Time = [7594], UserTime = [7,563]
Resitel:Jaroslav Dakš
Result = [30000000], Time = [7484], UserTime = [7,484]
Resitel:Jakub Flaška 
Result = [30000000], Time = [8266], UserTime = [8,250]
Resitel:Čestmír Najzar
Result = [30000000], Time = [11219], UserTime = [11,219]
Hotovo!

Vítězem je Marek Juřica, cena poroty (tj. pěkné - elegantní - cool řešení) byl větší oříšek, rozhodovalo se mezi Vladimír Bárta, Jiří Koula, David Lebeda, ale na poslední chvilku to je Tomáš Jantač. Opravdu gratuluji. Tomáš Jantač měl 4 varianty (různě špinavé). Vítěz i vítěz ceny poroty dostávají hrneček a PDF serveru delphi.cz.

Další výrazně neobvyklé řešení: Pepák a brutální věc od Dalibora Tomana (principiálně stejná jako jedna z variant Tomáše Jantače - tu jsem vypustil).

Best of řešení

Je kombinací řešení, které napsal Marek Juřica (částečně shodné s řešením Dalibora Tomana a Tomáše Jantače), háčku na přístup k private polím (Marek Juřica, Vladimír Bárta) a nakonec Tomáše Jantače (podobně i Jiří Koula).

V první části se přes tabulku posčítají hodnoty z stringu, který se díky háčku získal přímo. Iterace se provádí přes PChar inkrementací ukazatele na řetězec. Tady upozorním, že zvyšování proměnné typu PChar v unicode Delphi (2009+) posune ukazatel o 2 byte (Char = 2byte), v starších Delphi o 1 byte (Char = 1byte). Tím pádem se řeší hodně věcí při migraci ze starších verzí.

No a nakonec fígl ohledně závislosti ciferného součtu a zbytku po dělení 9.

    1type
    2  THackList = class(TStrings)
    3  private
    4    FList: PStringItemList;
    5  end;
    6
    7/// absolutni reseni
    8function CountDigit_Absolute(const lst: TStrings):Integer;
    9const arr2 :array[0..255] of byte = (
   10   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   11   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   12   0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,9,0,0,
   13   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   14   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   15
   16   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   17   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   18   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   19   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   20   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   21
   22   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   23   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   24   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0);
   25var
   26  i, j: Integer;
   27  pC: PChar;
   28  pStr: ^String;
   29begin
   30  Result := -1;
   31  pStr := @THackList(lst).FList[0].FString;
   32  pC := PChar(Pointer(pStr^));
   33  for i := 0 to Length(pStr^) - 1 do
   34  begin
   35    Inc(Result, arr2[Ord(pC^)]);
   36    Inc(pC);
   37  end;
   38
   39   result:=(Result mod 9)+1;                            // abraka dabra :oD
   40end;

Některé řešení

Řešení David Lebeda, osobně se mi líbí.

    1function CountDigit_DLebeda(const lst: TStrings):Integer;
    2var
    3 pc: PChar;
    4begin
    5 result := 0;
    6 pc := PChar(@lst[0][1]);
    7 while pc^ <> #0 do
    8 begin
    9  if AnsiChar(pc^) in ['1'..'9'] then
   10  begin
   11   result := result + byte(pc^) - ord('0');
   12//   if result > 9 then
   13//    dec(result, 9);
   14   case result of
   15    10..18: dec(result, 9);
   16   end;
   17  end;
   18  inc(pc);
   19 end;
   20end;

Řešení Tomáše Jantače (varianta A1 - B1 - cena poroty). Jen bych upozornil, že A2 B1 by mohlo být i nejrychlejší - viz CPU, kdy pro P: TStringItem; se generuje kód pro práci se záznamem.

Pozn. Delphi.cz: Variantu B2 jsem vypustil - nebyla nejrychlejší a zabírala moc místa.

    1{
    2 varianta A1 - poctive / hezky kod
    3 varianta A2 - trosku hack RTL knihovny (vyzaduje jeji nezmenenou podobu!)
    4
    5 variante B1 - poctive / elegantni
    6
    7 A1 B1 - nejcistci kod
    8 A2 B1 - (hack do RTL)
    9
   10 pole 256 konstant "bArray" povazuji narozdil od pole pro variantu B2 za korektni,
   11 proto bych osobne uprednostnoval variantu A2 B1
   12}
   13
   14{.$DEFINE A1}
   15{$DEFINE A2}
   16{$DEFINE B1}
   17
   18function CountDigit_TJantac(const lst: TStrings):Integer;  
   19const
   20  bArray : array[$00..$FF] of integer =
   21   ( 0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,
   22     0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,1, 2,3,4,5,6,7,8,9,0,0,
   23     0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,
   24     0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,
   25     0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,
   26     0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,
   27     0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,
   28     0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,
   29     0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0
   30    );
   31var
   32  I: Integer;
   33{$IFDEF A1}
   34  S: String;
   35{$ENDIF}
   36{$IFDEF A2}
   37  P: TStringItem;
   38{$ENDIF}
   39begin
   40  Result:=-1;
   41
   42{$IFDEF A1}
   43    S:=lst.Strings[0];
   44    for I:=1 to Length(S)
   45     do Inc(result,bArray[Byte(S[I])]);
   46
   47{$ENDIF}
   48
   49{$IFDEF A2} // humus, závislé na verzi
   50   P:=PStringItemList(Pointer((Integer(lst)+$1C))^)^[0]; // v Delphi 5 $0C
   51
   52   for I:=1 to Length(P.FString)
   53    do Inc(result,bArray[Byte(P.FString[I])]);
   54{$ENDIF}
   55
   56{$IFDEF B1}
   57   result:=(Result mod 9)+1;    // abraka dabra :oD
   58{$ENDIF}
   59
   60end;

Řešení Jiří Koula.

    1function CountDigit_JKoula(const lst: TStrings):Integer;
    2var s:string;
    3    l:integer;
    4    b:integer;
    5    n:integer;
    6begin
    7  n:=0;
    8  s:=lst[0];
    9  for l:=length(s) downto 1 do
   10  begin
   11    b:=Ord(s[l]);
   12    if b in [49..57] then n:=n+(b xor 48);
   13  end;
   14  if n=0 then
   15    Result:=0
   16  else
   17  begin
   18    n:=n mod 9;
   19    if n=0 then Result:=9 else Result:=n;
   20  end;
   21end;

Řešení Vladimír Bárta:

    1function CountDigit_VBarta(const lst: TStrings):Integer;
    2var
    3   s: PWord;
    4begin
    5  Result := 0;
    6//bez kontroly!  if lst.Count = 0 then Exit;
    7// alternativa bez hacku: pWord(@lst[0][1]);
    8  s := pWord(TStringListHack(lst).FList[0].FString);
    9  while s^ <> 0 do begin
   10    if s^ - 48 in [0..9] then begin
   11      Inc(Result, s^ - 48);
   12      if (Result) >= 10 then
   13        Dec(Result, 9);        // - 10 + 1
   14    end;
   15    inc(s);
   16  end;
   17end;

Všechny řešení lze stáhnout zde (v jednom souboru). Vaše názory mne (a nejen mne) zajímají, klidně pište do komentářů.

Pro informaci: Výsledná aplikace kompilováná v Delphi 2010 pro porovnání.

BlueBoard.cz

e422556d-22d1-49ec-90d5-13196d816812|0|.0

Tagy: optimalizace

soutez

Související příspěvky

Výsledky 2. soutěže Optimalizační soutěž č.2 Soutěž o RAD Studio 2007 Architekt

Komentáře

30.7.2010 7:07:29 #

Pár poznámek:

1) Dodatečně jsem si říkal, že jsem mohl řetězec ze stringlistu vytáhnout přímo (hackem/háčkem) - dost mě při pohledu do CPU View zarazilo, že se kopíruje string a ne odkaz. Jenže v době, kdy jsem se rozhodl to zkusit, už jsem zdroják smazal a tak jsem to nechal být.

2) Na vítězném řešení mě VELICE překvapuje jedna věc - že je vyhledání v tabulce rychlejší než výpočet. Byl bych si myslel, že těch pár CPU instrukcí bude rychlejších než čekání na paměť (byť tou pamětí je cache).

3) Druhá věc, kterou nevím a zajímala bý mě: Ord(Char) vrací v Delphi 2009+ číslo typu Byte? Takhle odhadem se mi zdá, že "Best of" při načtení prvního Unicode znaku spadne buď na Range Error nebo na čtení z nealokované paměti, případně přečte a přičte náhodou hodnotu.

- Obdobný problém, i když ne tak kritický (nevede k pádu programu, jen k chybnému výsledku) mají i všechna řešení, která provádějí přetypování na PChar (např. Lebeda) - pracujeme s UTF16 a tam může naprosto klidně existovat znak $3100, který určitě není jednička, ale do výsledku se jako jednička započítá.

4) Poslední věc, která mě VELICE zaujala, je to nahrazení ciferného součtu zbytkem po dělení devíti. Dá se k tomu někde najít důkaz, že to funguje? Takhle z hlavy se mi totiž zdá, že nefunguje:

- Verze "Best of" ((Result mod 9)+1) - nefunguje pro nulu nebo 20

Obdobně některé další verze, např. Koula a Lebeda - z hlavy nemohu najít protipříklad, ale než si podobnou /pěknou) fintu troufnu použít ve svých programech, rád bych viděl formální důkaz.

Jinak se mi znovu potvrzuje už mnohokrát ověřená skutečnost, že ve většině "školních" příkladů přílišné přemýšlení škodí a nejlepší je napsat kód co nejjednodušeji - nějaké úvahy nad tím, že nejrychlejší čtení dat je po DWORDech (kterým se ubíralo moje řešení) nebo že řpesně na tento typ úloh se hodí MMX (kterým se ubíraly moje úvahy a zastavila je lenost), je úplně zbytečné, protože to stejně ve výsledku nijak zvlášť nepomůže.

Za největší přínos soutěže považuji právě ten trik pro ciferný součet, pokud se ho podaří dokázat.

pepak

30.7.2010 8:30:16 #

Když tak o tom uvažuju, výpočet "Lebeda" je v pořádku. Výpočtem "Koula" si stále nejsem jistý.

pepak

30.7.2010 9:15:37 #

Dobrá, zkusím nastínit formální důkaz.

Představme si, že vezmeme string, vyhodíme z něj vše, co není číslice, a prohlásíme to za jedno dlouhé číslo v desítkové soustavě. Toto číslo se dá zapsat jako

a_0 + 10 * a_1 + 10^2 * a_2 + ... + 10^n * a_n

Chceme sečíst cifry, tedy poo první iteraci máme místo našeho čísla

a_0 + a_1 + a_2 + ... + a_n.

Teď si uvědomíme, že každá mocnina desítky dává po dělení devíti zbytek 1, totiž

10^i = 1 + 99...99 = 1 + 9*(11...11), tudíž odpovídající si členy v obou výše uvedených součtech dávajií stejný zbytek po dělení devíti a též celé součty dávají stejný zbytek po dělení devíti.

Nyní tedy máme součet cifer původního čísla a opakujeme předchozí krok i úvahu. Iterací (pro puntičkáře jde o matematickou indukci) dospějeme nakonec k tomu, že výsledné jednociferné číslo má stejný zbytek po dělení devíti jako původní číslo.

Čísla 1 až 8 jsou sama těmi zbytky, číslo 9 dává zbytek 0, tam je proto třeba rozlišit, zda na vstupu byla nějaká číslice, potom vracíme 9 (není možné se postupným sčítáním kladných čísel dostat k nule), pokud na vstupu číslice nebyla, vracíme 0.

Snad se mi to podařilo aspoň trochu vysvětlit, nejasné kroky se rád pokusím osvětlit.

Jirka Koula

30.7.2010 9:39:07 #

"- Verze "Best of" ((Result mod 9)+1) - nefunguje pro nulu nebo 20"

Ale funguje, smekám před nápadem incializace Result:=-1 a přičtením jedničky ke zbytku na konci, tím se řeší to mé ifování v kódu i v nástinu důkazu.

Totiž, když nepřijde na vstupu žádná číslice, zůstane Result na -1, Delphi výraz -1 mod 9 vyhodnotí jako -1 (což mě tedy mírně zarazilo, jsem zvyklý na trochu jinou definici zbytku po dělení pro záporná čísla, ale uznávám, že ve světě programovacích jazyků je tato standardem) a přičtení jedničky vrátí potřebnou nulu.

Ve všech ostatních případech se vrátí číslo z intervalu 0..8 a skutečně jde o hodnotu o jedna menší než to, co chceme - číslo o jedna menší má i o jedna menší zbytek po dělení devíti, tedy až na to, že pokud je u původního 0, u o jedna menšího je 8 - a to se nám zatraceně hodí, protože přičtením jedničky se dostaneme na devítku místo na nulu jako u prostého zbytku.

Prostě geniální a tleskám autorovi.

Jirka Koula

30.7.2010 9:50:42 #

Vypadá to rozumně, díky.

pepak

30.7.2010 9:51:45 #

Tak ten Result := -1 jsem přehlédl (resp. vůbec jsem nepočítal s tím, že by tam mohlo být něco jiného než 0, tak jsem se na něj vůbec nedíval).

pepak

30.7.2010 9:59:58 #

Teď jsem podíval na variantu "Lebeda" a docela mě zarazilo, že jste ji shledal v pořádku dříve než mou. Totiž, rozmyslet si, že můžu výsledný součet počítat "cestou", tedy že algoritmy
a) ze zadání - posčítat vše, když je to větší než deset, tak iterovat
b) postupné přičítání a odečítání (devítky!) když to přeleze desítku
dělají totéž, bych bez opory v dělitelnosti asi nedal, docela by mě zajímal směr Vašich úvah.

Jirka Koula

30.7.2010 10:16:28 #

A nedá mi to a nedá, když už je tu ta anketa a teď mi to došlo, tak si postěžuju. Na základní škole, když se bere dělení, se učí kritéria pro dělitelnost - dvěma, když je poslední číslice dělitelná dvěma, pro čtyřku to jsou dvě poslední číslice, pro pětku že končí na nulu nebo pětku.

A pro devítku (a trojku) se učí poučka - číslo je dělitelné devíti (třemi), právě když jeho ciferný součet je dělitelný devíti (třemi).

A má stížnost a z toho plynoucí výzva - někdy v té době se určitě bere i zbytek po dělení, ale který učitel poznamená "a kritérium pro dělitenost devíti je jen speciální variantou tvrzení, že každé číslo má zbytek po dělení devíti stejný jako ho má jeho ciferný součet"? Správně, prakticky žádný. A tak apelujte na všechny učitele matematiky na základních školách, které kde potkáte, aby tuhle nenápadnou větičku zařadili do svého výkladu. :)

Jirka Koula

30.7.2010 10:21:19 #

Je dost možné, že v té "potvrzující" úvaze byla další chyba (byť třeba úvaha dává správné řešení, dochází k němu špatnou cestou). Už ani pořádně nevím, jak jsem k tomu vlastně došel.

Snad už se k tomu radši nebudu vracet, abych nesekal další chyby. Důležité pro mě je, že jde použít ten trik s modulo 9, to se určitě bude hodit.

pepak

30.7.2010 11:30:25 #

Když jsem četl předchozí mezivýsledky, tak jsem usoudil že pan Koula zřejmě používá nějaký přímý přístup k datům. Konec konců přesně toto dělá vyhrávající řešení, které je téměř stejné jako moje varianta A2. Nicméně uznávám že vyhrávající řešení je čisté a správné, za svou variantu A2 se stydím. O správný odkaz do paměti se zde postará kompilátor, na rozdíl od slepého přičtení odpozorované konstanty. Hodně jsem rozmýšlel jestli varianty A2 a B2 vůbec posílat, nicméně zadáním bylo vytvořit co nejrychleší algoritmus a tak sem si chtěl dokázat že to jde. Teď vidím že to jde a také že to jde i elegantně. No a teď abych snad chodil kanálama. :oD

Soutěž se mi líbila, neboť mne donutila uvědomit si které operace jsou časově náročné a stojí za optimalizaci.

K výslednému řešení:
Nebylo by efektivnější přistupovat k datům jako k poli znaků přímo, místo inkrementování pointeru?

type
  THackList = class(TStrings)
  private
    FList: PStringItemList;
  end;

function CountDigit(const lst: TStrings):Integer;  // "const" neuskodi ale na vykon nema v tomto pripade vliv - jen omezuje pristup k promenne (pointeru na objekt), nikoliv k vlastnostem objektu
const
  bArray : array[$00..$FF] of integer =
   ( 0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,
     0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,1, 2,3,4,5,6,7,8,9,0,0,
     0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,
     0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,
     0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,
     0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,
     0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,
     0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,
     0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0
    );
var
  I: Integer;
begin
  Result:=-1;

   for I:=1 to Length(THackList(lst).FList[0].FString)
    do Inc(result,bArray[Byte(THackList(lst).FList[0].FString[I])]);

   result:=(Result mod 9)+1;                            // abraka dabra :oD
end;

ps. koukám že výraz "abraka dabra" je mezi programátory oblíben... ;o)

Tomáš Jantač

30.7.2010 11:43:30 #

ad 3) Máte pravdu, správně by mělo být

Inc(Result, arr2[Byte(Ord(pC^))]);
protože Ord vrací SmallInt. Takže teoreticky by opravdu mohlo dojít k problému, s tím Byte se to dostane v případě "špatného znaku" jen do kategorie špatných výsledků. Na rychlost to má vliv minimálně.

radekc

30.7.2010 11:52:23 #

Ne - 1670, což je o dost horší než prezentované řešení.

radekc

30.7.2010 12:23:07 #

Nevím, nakolik je výraz abraka dabra oblíben, jeho použití v best of řešení tuším vzniklo zkopírováním celého řádku z Vašeho řešení. :)

A také Vám za sebe gratuluju k celkově nejrychlejšímu řešení, totiž:

Vzal jsem projekt tak jak je ke stažení, otevřel své D6, zakomentoval tři direktivy z novějších verzí a pustil opakovaně Vaše řešení proti řešení Marka Juřicy, pouštěl jsem jen tato dvě řešení, pětkrát šlo Vaše jako první, pětkrát jako druhé.

A co jsem naměřil? Vaše řešení (varianta A1, varianta A2 mi vyhodila výjimku) ve všech deseti bězích dalo tomu "vítěznému" na zadel průměrně o 300ms (při absolutních časech kolem 6300 a 6600).

Navíc, když jsem pouštěl všechna řešení, tak mi řešení Dalibora Tomana, Aleše Gregora, Vladimíra Bárty a CerdaAsm vracela špatné výsledky (80000000, 0, 60000000, 10000000).

Z toho mi plyne, že soutěž nebyla obecně o optimalizaci algoritmu, ale o optimaliaci pro D2010. Což je velice zajímavá informace a asi u se konečně rozhoupu k nákupu nových Delphi, zvláště v kombinaci s aktuální akcí Embacadero. :)

Jirka Koula

30.7.2010 12:28:17 #

Zkusil jsem otestovat Váš návrh na zlepšení oproti best of řešení a Váš návrh u mě výrazně zaostává (5000 vs. 6400). Ovšem na základě předchozího příspěvku si netroufám odhadnout, jak to dopadne na konfiguraci použité pro hodnocení. :)

Jirka Koula

30.7.2010 12:52:29 #

Po bitvě je každý generál ;-)

Upravené řešení je o kapánek rychlejší než od Marka, ale pořád pomalejší než nastíněné Best OF

Best OF - cca 1000
Tomáš Jantač s úpravou - cca 1600
Marek Juřica původní - cca 1680

Ad optimalizace: Delphi 2006+ provádějí lepší optimalizace (viz článek cca týden zpátky), a pokud používáte věci z RTL (což všichni), tak tam jsou tam navíc výrazně optimalizované kódy např. na kopírování nebo matematiku (nejen z FastCode) a integrace FastMM taktéž pomohla výrazně (hlavně pokud vytváříte hodně objektů nebo řetězců).

Takže se může stát, že proti Delphi 5-7 může být některá část i 2x tak rychlá (ale pokud čekáte na uživatele tak je to jedno). Nejrychlejší je podle mne kód z Delphi 2007, pak 2010 (dočasná kompatibilita s C++Builderm), 2009 a pak 7, 6, 5. 2005 a 2006 jsem netestoval, ale podle mne díky popsaným změnám budou rychlejší než 7, ale tam je spíše problémem IDE.

Každopádně instalace FastMM a FastCode (psal jsem i zde) situaci trochu zlepší i u starších verzí.

Většina optimalizací se projevila na všech verzí, jen někdy se počítalo jen s unicode.

radekc

30.7.2010 12:54:03 #

prezentované BEST OF

radekc

30.7.2010 13:29:32 #

ano vím je po bitvě, jen mě překvapilo že je rychlejší pracovat s jedním pointerem navíc

teď když se o tom tak bavíme tak mi začíná docházet proč asi,
ještě se na to někdy zkusím podívat do výsledného ASM

každopádně díky za test, měl jsem si to nejdřív odzkoušet...

Tomáš Jantač

30.7.2010 13:38:16 #

Ach jo, to se nám to zamotává ještě více, stáhl jsem si Delphi2010.exe a (orientační průměr přes pět běhů):

best of - 5400 (pomalejší než když si ho zkompiluju v D6 - 5000)
Marek Juřica - 8350 (čímž se dostávám mezi sedm až osm soutěžících (u Cerdy je to jak kdy), jejichž řešení je na mém stroji průkazně rychlejší než vítězné)
Dalibor Toman - 5300 (rychlejší než best of)
Tomáš Jantač - 6400 (obě varianty se liší v jednotlivých bězích o pár desítek ms a někdy je rychlejší to a někdy ono)

Testováno na Toshiba NB100, 2GB RAM, WinXP Pro. Co s tím? Možná by stálo za zvážení pro příští soutěž rozposlat výsledné Delphi2010.exe mezi všechny soutěžící a zprůměrovat jimi naměřené hodnoty, takto to nejen že byla optimalizace pro D2010, ale navíc optimalizace pro běh výsledného exe na Vašem stroji. :)

Ale neberte to jako výtku, nechci si hrát po bitvě na generála, sám bych ta řešení rozhodně nechtěl testovat, jen mě překvapilo, jak kluzká mrcha testování rychlosti algoritmu je (navíc vzhledem ke srovnání všeho uvedeného začínám pochybovat, zda je otázka "který algoritmus je nejrychlejší" vůbec správně položena, když odpověď (dost výrazně) závisí na kombinaci kompilátor - cílové prostředí).

Jirka Koula

30.7.2010 13:42:52 #

ne, máte pravdu, neodzkoušel jsem si to a neuvědomil jsem si že to kompilátor dobře zoptimalizuje
prostě jsem si vždy myslel že přístup do stringu je tímto způsobem nejrychlejší...

Tomáš Jantač

30.7.2010 14:32:14 #

Jen pro zajímavost procesor?

U nás to bylo testováno na několika strojích, a výsledky jsou zhruba stejné s tím co jsem prezentoval. Většinou pravda Core2Duo, tj. 64bit procesor, ale i Pentium M.

Už jsem zjistil, kde je problém: zkoušel jsem tu variantu s
Inc(Result, arr2[Byte(Ord(pC^))]); a nechal jsem to tam, kdy v puvodni variante bylo
Inc(Result, arr2[(Ord(pC^))]); a pri prekladu jsem to tam nechal.

http://delphi.cz/img/soutez/Delphi2010_or.zip - puvodni varianta

Prostě si z toho vezmu ponaučení :-O

radekc

30.7.2010 14:54:49 #

DD,

1) hack s primym pristupem na pamet retezce s obsahem radku je skvely.Vynechani tak volani metody tridy pro ziskani retezce je vysoce ucinne zrychleni zpracovani dat. Klobouk dolu pred temi, kdo to pouzili (ja uz v Delphi delsi dobu skoro neprogramuju a tyhle veci mi unikaji)
2) je videt, ze kazde reseni, ktere v hlavnim cyklu pouzilo cokoliv navic bylo pomale. V teto nejexponovanejsi casti je treba napsat kod ktery udela co nejvic prace v nejmensim poctu CPU cyklu.
3) finalni jednoradkova uprava souctu pomoci modulo 9 je pekna a elegantni (ac na prvni pohled nefunguje :-) ). Ale problem je ten, ze instrukce IDIV CPU pro celociselne deleni je hodne pomala (desitky cyklu CPU). Preklad pomoci tabulky (viz moje) reseni ackoliv vypada podivne (kvuli delce tabulky) - je rychlejsi (prestoze u techto veci lze snadno narazit na problemy s cache CPU). Po pouziti Markova hacku na zpristupneni pameti radku v Lst se moje reseni vyrazne zrychlilo (na mem stroji puvodne cca 2400ms po uprave mene nez 1000ms = na testovacim PC RadkaC by to melo byt jeste rychlejsi).
Cili pokud je CountDigit_Absolute kompilatem toho nejlepsiho z ostatnich reseni, vyhozenim modulo 9 a nahrazenim prekladem tabulkou se pekne urychli.

To jen pro dokresleni toho, co vsechno je treba brat v uvahu, pokud jde skutecne o optimalizaci na rychlost.

Zdravi
Dalibor Toman

Dalibor Toman

30.7.2010 15:17:12 #

>Navíc, když jsem pouštěl všechna řešení, tak mi řešení Dalibora Tomana, Aleše Gregora, >Vladimíra Bárty a CerdaAsm vracela špatné výsledky (80000000, 0, 60000000, 10000000).

to je jasne - vsechna tato reseni predpokladaji, ze stringo s daty je Unicode (2 bajty na char) = posunuji se v pameti po 2 bajtech. Takze pri prelozeni v non-unicode verzi Delphi se polovina znaku ze vstupu preskoci.
V zadani bylo, ze cilova platforma je D2010.

Dalibor Toman

30.7.2010 15:53:53 #

Procesor je standardní netbookový Intel Atom N270 na 1.6 GHz.

Po spuštění testu z Delphi2010_or.zip problém přetrvává, pan Juřica se sice zlepšil (při zachování času ostatních řešení) z 8350 na 7350, stále je to ale aspoň o čtvrtinu více, než by se na vítěze slušelo. :)

Jirka Koula

30.7.2010 15:54:34 #

Aha, to dává smysl, děkuju za nakopnutí (tedy vysvětlení). :)

Jirka Koula

30.7.2010 16:26:16 #

Máte pravdu, na mém netbooku jste porazil best of řešení i bez HackListu. A vaše vypořádání se s potenciálním nekonečnem vs. konečnou tabulkou je elegantní, k úplné dokonalosti už zbývá jen odstranit nepotřebné násobení deseti (pravda, které je ve větvi, kam se výpočet při hodnocení nedostal).

Jirka Koula

30.7.2010 16:51:33 #

Ha, chyba a já na ni skočil. :)

Totiž, v té else větvi součet z trháte na x a y, přičemž z=x + 65536*y. No a Vy následně místo ciferného součtu z hledáte vlastně ciferný součet čísla x+y. Jenže zbytek po dělení devíti čísla 65536 je 7, potřebujete tedy ciferný součet čísla x+7*y. Takže správné řešení by bylo např. Result shr 16 vynásobit sedmi, případně se dá sedmi vynásobit SumArr[Result shr 16]. Takže místo "10*" tam vlastně má být "7*". :)

Jirka Koula

30.7.2010 22:44:12 #

Zdravim,

jen nekolik poznamek. Optimalizace podobnych algoritmu byla vzdy zabavna disciplina :-) Aby to hodnoceni vysledku bylo objektivni, bylo by dobre uvadet za jakych podminek se testovalo. Tedy minimalne architekturu CPU, ktera v tomto pripade neni nepodstatna. Vzhledem k tomu, ze kompilator zrejme produkuje jen 32 bitovy kod, je pripadny beh na 64 bit systemu v rezimu WOW64 emulace ne prilis reprezentatvni. Stejne tak by bylo zajimave videt jak vypadal nativni kod na urovni asm instrukci.

GetProcessTimes nedava zcela presne hodnoty, stale lepsi je QueryPerformanceCounter.

"i když podle mne rychlost výsledného kódu závisí i na okolních funkcích, což moc nechápu" - Nevim do jake miry je dovedena optimalizace soucasneho kompilatoru, ale podstatnou veci je alignment. A to nejen datovych struktur (to uz by dnes mela byt u vsech nastroju emitujicich nativni kod samozrejmost), ale i kodu. Popsane je to treba zde:

http://quotenil.com/Code-alignment-on-x86.html
http://stackoverflow.com/questions/1852218/how-to-ensure-16byte-code-alignment-of-delphi-routines
https://forums.embarcadero.com/thread.jspa?messageID=222229

V pripade ze kompilator podobne optimalizace neumoznuje to muze vysvetlit tu zavislost.

P.S. mozna by se sluselo uvadet, ze tenhle blog je (velmi pravdepodobne) zalozen na open source projektu BlogEngine.NET

Petr Vones

31.7.2010 0:09:18 #

Ahoj Petře,

a) No WOW64 je jen na 64bit oknech, já mám 32 XP. Takže to bylo mimo.
b) I kdyby to byl 64bit okna, tak x86-64 nemá na WOW64 prakticky žádnou režii (žádná emulace - jen při přepnutí tasku režie) a Itanium už oficiálně není podporováno ani MS (VS 2010 je poslední verzí VS - http://www.diit.cz/clanek/microsoft-konci-s-podporou-procesoru-intel-itanium/35962/)
c) s tím zarovnáním máš asi pravdu, nenapadlo mne, že to bude mít takový vliv na tuto úlohu. Aktuálně je zarovnávání na DWORD (http://qc.embarcadero.com/wc/qcmain.aspx?d=7560). Každopádně díky za odkazy
d) QueryPerformanceCounter - máš pravdu, chtěl jsem původně použít StopWatch z Delphi 2010 (http://delphi.cz/post/Delphi-2010-StopWatch.aspx z Delphi 2010), který to zapouzdřuje, ale pak jsem to z ohleduplnosti (a lenosti) na starsi Delphi bohuzel nechal tak jak jsem to nechal, ale nemyslím, že by to mělo v tomto případě význam
e) ad BlogEngine.NET - ano je to na něm založené (ale ne archiv konference), s tím, že je předěláno generování článků (zdrojová data jsou ve formátu podobném Wiki) a administrace a design. Licence podle mne nenutí k publikovani informaci o BlogEngine.NET (http://blogengine.codeplex.com/license?ProjectName=blogengine).

Naopak podle mne čím více informací zveřejníš, tím je větší šance napadení a vůbec.

Jestli narážíš na to, že na Delphi.cz používám ASP.NET, tak jsem to nikdy neschovával - pro každou věc používám správný nástroj. A ASP.NET není špatné, i když postupem doby už z něj tak nadšen nejsem jak na začátku.

A když už o tom BlogEngine.NET: tak nic moc kód, navíc je celkem citlivý na hosting - co já si s ním užil na původním hostingu (podobně jako x lidi na jeho fóru). Navíc některá rozšíření jsou fiasko. Tobě ale podle všeho běží OK.

Každopádně moc díky za tvé poznámky

Radek

radekc

Přidat komentář

Jméno*
E-mail*
WWW

Komentář
Náhled

Upozornit na nové komentáře

Soutěž - výsledky

Best of řešení

Některé řešení

Naše nabídka

O Delphi.cz

Anketa

Twitter

Seznam stránek

Poslední komentáře

Dle měsíců

Soutěž - výsledky

Best of řešení

Některé řešení

Naše nabídka

O Delphi.cz

Anketa

Twitter

Seznam stránek

Poslední komentáře

Tagy

Dle měsíců

Blogroll

Seznam kategorií