Dnia Mon, 15 Apr 2013 09:43:27 -0700 po głębokim namyśle M.M. rzekł:

> W dniu poniedziałek, 15 kwietnia 2013 16:49:56 UTC+2 użytkownik Edek
> napisał:

> [...]
>> Po pierwsze: cały program przyspieszył 2-4 razy czy fragment? Ja
>> mówiłem o całym.
> Myślę że cały. Jak jest dokładnie, to nie wiem. Nie widziałem żadnego
> bardzo zaawansowanego programu na reprezentacji intuicjonistycznej, więc
> nie mogę porównać. Jeśli nie mogę porównać, to dlaczego napisałem że 2-4
> razy?

Bo pokazałeś, że można gorzej?

> Otóż w reprezentacji intuicyjnej mamy planszę:

A dlaczego ta ma być intuicjonistyczna? Kolejne słowo, które jednak
jest dość subiektywne.

> Pole plansza[8][8];
>
> Chcemy sprawdzić czy pole (src_x,src_y) jest atakowane przez damę, więc
> musimy zrobić 8 pętli, każda w innym kierunku.
>
> W dużym przybliżeniu taki kod:
>
> for( i=0 ; i<8 ; i++ ) {
> dst_x = src_x + offset[i].x;
> dst_y = src_y + offset[i].y;
> while( dst_x >= 0 && dst_x < 8 && dst_y >= 0 && dst_y < 8 ) {
> czy_jest_dama( plansza , dst_x , dst_y );
> dst_x += offset[i].x;
> dst_y += offset[i].y;
> }
> }

Strasznie zakodowane... czy taki kod szachowy uwzględnia domyślną
liczbę bierek czy też głównym nurtem idą różne nieco egzotyczne
sytuacje typu - powiedzmy - trzy wieże po jednej stronie?

> Na reprezentacji bitowej mamy:
> Maski bierki[12];
>
> Więc jedna instrukcja warunkowa daje podobny efekt jak cały kod powyżej:
> if( bierki[DAMA] & maski_atakow[x][y] )

Nie wiem ile grasz w szachy, ale to właśnie jest intuicjonistyczne.
Patrząc na szchownicę widzi się właśnie całe formy ruchów a nie
kombinuje które pole jest które i czy wieża z damą się bronią
nawzajem, czy tylko król wraz z damą obstawia wieżę, ta pierwsza
po przekątnej. Podobnie z wymianami.
[...]

>> Po drugie szachy są niszą. Z tego co się orientuję
> Tak, szachy są niszą. Ale też są przykładem aplikacji gdzie w jakość
> implementacji i w jakość mini-algorytmów wielu zdolnych ludzi włożyło
> dużo pracy. Na przykładzie szachów widać efekt, widać co można uzyskać
> dzięki dobrej implementacji i dzięki wielu minimalnym ulepszeniom
> algorytmów. Więc może w innych aplikacjach, w których niejednemu
> programiście wydaje się, że implementacja jest prawie optymalna, też by
> się okazało, że można wydajność poprawić o 2-4 razy?

W mojej pracy nawet gdyby się okazało, że da się coś zrobić 10x szybciej
ale trzeba spędzić na kodem tyle czasu to po prostu to się _zazwyczaj_
nie opyla.

>> w innych analizach danych część ludzi wyciska każdy %, a część używa
>> Javy. Oba podejścia mają sens, ja preferuję "najpierw wygoda a potem
>> przepisujemy krytyczne algorytmy". Rozsądnie napisany kod nie jest 2x
>> wolniejszy od optymalnego, najczęściej jest w granicach 10-20%
>> max i 5-6% jako całość.
> Kiedyś porównywałem szybkość wyśrubowanej (ale i tak jeszcze
> nieoptymalnej) implementacji z implementacją zwykłą/rozsądną.
> Wyśrubowana była w proceduralnym C++, rozsądna/wygodna była w Javie. Oba
> programy miały za zadanie policzenie ilości węzłów w drzewie gry na
> ograniczoną z góry głębokość. No i ta wyśrubowana była kilka razy
> szybsza na procesorze intel atom N270, od tej w Javie na jakimś
> procesorze 64bitowym. Na tym samym procesorze różnica była pewnie
> niecałe 10 razy.
>
> Napiszę jeszcze raz to samo, może programistom często się tylko wydaje
> że są w okolicach tych 10% od optimum?

Może Tobie się wydaje, że każdy kod można przyspieszyć 2-4x?

> Ok, dzielmy na trzy: implementacje rozsądne, optymalne i zepsute.
> Zastanawiamy się czy w sytuacji gdy mamy do czynienia z implementacją
> rozsądną, to jest ona gorsza o 10% od optymalnej czy o 75% (o 75% czyli
> 4 razy). Nawiązuję do szachów, bo to była sytuacja w które myślałem że
> mam rozsądną implementację i wielu mi podobnych myślało podobnie, a
> okazało się, że w ogóle nie zdawaliśmy sobie sprawy z możliwości.
> Otworzyły się nam oczy jak zobaczyliśmy źródła najlepszych programów.

Cieszę się Twoim szczęściem, ale skąd pomysł, że wszyscy mają wciąż oczy
zamknięte? Używanie masek bitowych robię "z zamkniętymi oczami".

> Szachy nie mają setek tysięcy linii kodu. Zwykle mają kilka, kilkanaście
> tysięcy, rzadko 30tys. Jednak szachy to taki specyficzny program, w
> który prawie cały kod jest gorącym punktem. Nawet interfejs
> komunikacyjny implementuje się wydanie, ponieważ gdy się rozgrywa
> turnieje na ultra-krótki czas (np. 5s na całą grę) to zepsuta
> komunikacja pomiędzy programami, czy zepsuty zapis logów do plików
> tekstowych, zajmuje stosunkowo duży procent mocy obliczeniowej.

Heh, rozumiem że to takie testowe turnieje. Grałem gdy miałem z 11
lat w zarówno w pełne jak i 3-4 minutówki, ale 5s to tylko maszyny.
Swoją drogą przestałem grać gdy mnie ograł 9-latek i zrozumiałem,
że tak na poważnie w lidze szachowej to ja nie mam szans.

--
Edek