W dniu poniedziałek, 15 kwietnia 2013 01:14:17 UTC+2 użytkownik Edek napisał:

Zaraz zaczniemy się "kłócić" o to gdzie leży granica pomiędzy optymalizacją
algorytmiczną a implementacyjną :)


> Właśnie nie, dobrze napisany w C++ kod będzie odporny na działanie
> czasu. Jedynie trzeba założyć jakiś margines fluktuacji.
Zgodzę się że będzie, ale dodam, że nie ma cudów. Dobrze napisany
kod w C++ nawet będzie coraz lepszy, bo kompilatory się wciąż
rozwijają, a kto wie, może twórcy procesorów zaczną procesory robić
tak, aby szybciej wykonywały taki kod, jaki kompilator jest w stanie
wygenerować. Ale właśnie nie ma cudów. Kompilator sam nie zorientuje się,
że w takich szachach mamy 64 pola na planszy i docelowy procesor też ma
64 bity w rejestrze. Kompilator nie zmieni sam szachownica[64], na kilka
masek z long long.

Teraz pytanie: czy zmiana struktury danych z szachownica[64], na
bierki[12] jest optymalizacją implementacyjną czy algorytmiczną?
Na pewno bierki[12] nie jest dobrze napisanym programem w C++, bo
jak gdzieś long long nie będzie 64-bitowy, to może nie działać.


> Dochodzi też margines opłacalności - programista często kosztuje
> więcej niż sprzęt (heh, powiedziałem co wiedziałem ;).
Właśnie dlatego że eksperymentowanie jest bardzo drogie i czasochłonne,
chciałbym wiedzieć od razu jaka implementacja okaże się najlepsza :)


> Poza HPC i paroma niszami nikomu nie zależy na +-10% jeżeli jest
> to kosztem funkcjonalności. Jeszcze jeden wyjątek: kod działający na
> milionach maszyn.
Myślę że w szachach dzięki dobrej implementacji uzyskuje się
przyspieszenie 2-4 razy a nie 10%. Test ataku na reprezentacji
szachownica[64] to iterowanie po polach i cztery warunki do
sprawdzania czy nie przekroczyliśmy zakresu, a na reprezentacji bitowej
to kilka operacji logicznych i kilka odczytów masek z tablic.


> To jest sztuka. Nie jest sztuką próbować do skutku aż się znajdzie
> optymalny przy tych a nie innych opcjach i wersji, tylko napisać tak,
> żeby trzymał się w najlepszych 10%.
Właśnie to jest pytanie czy idzie o te 10% czy o 200-400%. Weźmy
naiwne mnożenie macierzy i zoptymalizowane. Jakie to są różnice?
Coś mi się przypomina że 500% - 1000%.

Pozdrawiam

do góry

Dnia Sun, 14 Apr 2013 21:10:46 -0700 po głębokim namyśle M.M. rzekł:

> W dniu poniedziałek, 15 kwietnia 2013 01:14:17 UTC+2 użytkownik Edek
> napisał:
>
> Zaraz zaczniemy się "kłócić" o to gdzie leży granica pomiędzy
> optymalizacją algorytmiczną a implementacyjną :)

Jedna często wymusza drugą.

>> Właśnie nie, dobrze napisany w C++ kod będzie odporny na działanie
>> czasu. Jedynie trzeba założyć jakiś margines fluktuacji.
> Zgodzę się że będzie, ale dodam, że nie ma cudów. Dobrze napisany kod w
> C++ nawet będzie coraz lepszy, bo kompilatory się wciąż rozwijają, a kto
> wie, może twórcy procesorów zaczną procesory robić tak, aby szybciej
> wykonywały taki kod, jaki kompilator jest w stanie wygenerować. Ale
> właśnie nie ma cudów. Kompilator sam nie zorientuje się, że w takich
> szachach mamy 64 pola na planszy i docelowy procesor też ma 64 bity w
> rejestrze. Kompilator nie zmieni sam szachownica[64], na kilka masek z
> long long.

Procesory tak się rozwijają. M.in. Haswell i wcześniejsze są znacznie
bardziej tolerancyjne dla kiepskiego kodu. Wykonują kod szybciej
nie dlatego, że mają nowe istrukcje - chociaż to też - tylko np.
lepiej sobie radzą z odczytem częściowych słów jak i maskowaniem
przy użyciu części słowa. To powoduje, że można czytać drugiego
shorta a odczyt pierwszego shorta będzie niezależny i branch prediction
pozwoli obie instrukcje wykonywać równocześnie - a wcześniej drugi
short maskował pierwszego i ten wzór wykonywał się wolniej ze względu
na fałszywą zależność danych. Jest mnóstwo takich drobnych różnic.

To prawda, że kompilator sam nie zamieni booleanów na rejestr
bitów, ale można by już sprawdzić czy bitset nie ma implementacji
takiej, że to zadziała automagicznie. Twórcy kompilatorów tylko
na to poświęcają mnóstwo swojego czasu, często więcej niż
pojedynczy programista jest w stanie poświęcić na swój kod.
Optymalne jest wykorzystanie włąsciwości kompilatora i dopisanie
ręcznie tego, czego kompilator nie załatwia. W zasadzie dopiero
rozumiejąc kompilator można faktycznie poznać procesor - ja
sam często odkrywam, że to co wygląda fatalnie na pierwszy
rzut oka jest celowym działaniem desantu intela w gcc i hula
jednak lepiej.

> Teraz pytanie: czy zmiana struktury danych z szachownica[64], na
> bierki[12] jest optymalizacją implementacyjną czy algorytmiczną?

Taką i taką, jeżeli zmiana użytych prymitywów wpływa na algorytm.
Jako praktyk powiem, że jak zwał tak zwał, ma działać :). Z teoretycznego
punktu widzenia już nie wystarczy uwzględniać złożoności algorytmicznej,
bo sprzęt ma bardzo skomplikowane właściwości.

W zasadzie zamiana bool[38] na bitset[38] to "implementacyjna"?

> Na pewno bierki[12] nie jest dobrze napisanym programem w C++, bo jak
> gdzieś long long nie będzie 64-bitowy, to może nie działać.

Stosuje się alternatywne implementacje fragmentów sprawiających kłopot.

>> Dochodzi też margines opłacalności - programista często kosztuje więcej
>> niż sprzęt (heh, powiedziałem co wiedziałem ;).
> Właśnie dlatego że eksperymentowanie jest bardzo drogie i czasochłonne,
> chciałbym wiedzieć od razu jaka implementacja okaże się najlepsza :)

I bardzo dobrze, zawsze lepiej pomyśleć przed a nie tylko po.

>> Poza HPC i paroma niszami nikomu nie zależy na +-10% jeżeli jest to
>> kosztem funkcjonalności. Jeszcze jeden wyjątek: kod działający na
>> milionach maszyn.
> Myślę że w szachach dzięki dobrej implementacji uzyskuje się
> przyspieszenie 2-4 razy a nie 10%. Test ataku na reprezentacji
> szachownica[64] to iterowanie po polach i cztery warunki do sprawdzania
> czy nie przekroczyliśmy zakresu, a na reprezentacji bitowej to kilka
> operacji logicznych i kilka odczytów masek z tablic.

Po pierwsze: cały program przyspieszył 2-4 razy czy fragment? Ja
mówiłem o całym. Po drugie szachy są niszą. Z tego co się orientuję
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ść.

>> To jest sztuka. Nie jest sztuką próbować do skutku aż się znajdzie
>> optymalny przy tych a nie innych opcjach i wersji, tylko napisać tak,
>> żeby trzymał się w najlepszych 10%.
> Właśnie to jest pytanie czy idzie o te 10% czy o 200-400%. Weźmy naiwne
> mnożenie macierzy i zoptymalizowane. Jakie to są różnice?
> Coś mi się przypomina że 500% - 1000%.

Dobry przykład na porażkę teoretycznej złożoności bez uwzględnienia
sprzętu, tutaj cache.

Chciałbym coś odróżnić. Jest jedna granica pomiędzy naiwnym lub zepsutym
kodem a takim, który jest napisany rozsądnie. Druga granica dopiero
jest pomiędzy rozsądnym a "optymalizowanym". W tej pierwszej
usuwałem babole na 30x szybciej, w tej drugiej już +-10% to bardzo dużo.
Zaraz ktoś rzuci przykład małego algorytmu z lepszym zyskiem,
ale mam na myśli setki tysięcy linii kodu.

--
Edek

do góry

W dniu poniedziałek, 15 kwietnia 2013 16:49:56 UTC+2 użytkownik Edek napisał:
> Procesory tak się rozwijają. M.in. Haswell i wcześniejsze są znacznie
> [...]
> na fałszywą zależność danych. Jest mnóstwo takich drobnych różnic.
No tak, jeśli dane są niezależne, to procesor (potencjalnie) może je
wykonać równolegle.

> To prawda, że kompilator sam nie zamieni booleanów na rejestr
> bitów, ale można by już sprawdzić czy bitset nie ma implementacji
> takiej, że to zadziała automagicznie. Twórcy kompilatorów tylko
> na to poświęcają mnóstwo swojego czasu, często więcej niż
> pojedynczy programista jest w stanie poświęcić na swój kod.
> Optymalne jest wykorzystanie włąsciwości kompilatora i dopisanie
> ręcznie tego, czego kompilator nie załatwia. W zasadzie dopiero
> rozumiejąc kompilator można faktycznie poznać procesor - ja
> sam często odkrywam, że to co wygląda fatalnie na pierwszy
> rzut oka jest celowym działaniem desantu intela w gcc i hula
> jednak lepiej.
Może to mój błąd że nie zaglądam do kodu wygenerowanego przez kompilator.


[...]
> 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?
Otóż w reprezentacji intuicyjnej mamy planszę:
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;
}
}

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] )


Analogiczną różnicę mamy gdy chcemy zliczyć ilość bierek. Na reprezentacji
intuicyjnej iterujemy po 64 polach. Na reprezentacji bitowej
robimy popcount - zdaje się, że to jeden takt procesora. Oczywiście dla
reprezentacji intuicyjnej też można stosować pewne zabiegi przyspieszające,
nie trzeba zawsze wykonywać 64 pętli aby policzyć jakąś statystykę. Ale
i tak myślę że przyspieszenie na reprezentacji bitowej można oszacować
na 2-4 razy. Może jeszcze dodam, że zostały opracowane specjalne tablice
masek bitowych na różne okoliczności i specjalne algorytmy indeksowania w
tych tablicach. Kto dokładnie wie... może przyspieszenie jest nawet większe
niż 4 razy.


> 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 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?


> Dobry przykład na porażkę teoretycznej złożoności bez uwzględnienia
> sprzętu, tutaj cache.
> Chciałbym coś odróżnić. Jest jedna granica pomiędzy naiwnym lub zepsutym
> kodem a takim, który jest napisany rozsądnie. Druga granica dopiero
> jest pomiędzy rozsądnym a "optymalizowanym". W tej pierwszej
> usuwałem babole na 30x szybciej, w tej drugiej już +-10% to bardzo dużo.
> Zaraz ktoś rzuci przykład małego algorytmu z lepszym zyskiem,
> ale mam na myśli setki tysięcy linii kodu.

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.

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.

Pozdrawiam

do góry

gdyby w c bylo pare tych poprawek co trzeba
to uzytecznosc klepania w asmie pewnie by
sie jeszcze zmniejszyla (a jest to prawda
ze w c klepie sie funkcje latwiej niz w
asmie) - ja w kazdym razie nauke asma uwazam
za nauke języka i mam zamiar znac asma
i sporadycznie w nim poklepac)

do góry

Użytkownik "firr kenobi" <p...@g...com> napisał:

> i mam zamiar znac asma i sporadycznie w nim poklepac)

sporadycznie to se moze i poklep, ale asma nie dotykaj pozniej

do góry

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

do góry

Użytkownik "bartekltg" <b...@g...com> napisał:

> Oczywisćei zgadzam się, że przejście do wersji (prawie)
> zawsze prawie liniowej (z kwadratowej) dużo daje.

No przeciez mowie od poczatku roznicu miedzy zwykla
DFT a FFT (czyli algorytmem Cooleya_Tukeya).
Gdyby nie bylo FFT to kto wie czy pol automatyki/elektroiniki
itp by dzis "zostalo w sredniowieczu" (akurat tu szybkosc jest wazna:).
W kazdym razie dla mnie FFT jest jednym z przykladow
algorytmu ktory "zmienil dzieje".

AK

do góry

W dniu poniedziałek, 15 kwietnia 2013 23:23:50 UTC+2 użytkownik Edek napisał:
> Bo pokazałeś, że można gorzej?
Bo pokazałem rozsądną implementację :)

> A dlaczego ta ma być intuicjonistyczna? Kolejne słowo, które jednak
> jest dość subiektywne.
Właśnie mało ścisły temat, trudno powiedzieć co jest intuicyjne, co jest
zepsute, a już w ogóle nie wiadomo co jest optymalne. Za tym ze ta jest
intuicyjna przemawia fakt, że wielu programistów do problemu podeszło w
podobny sposób. Potem każdy z nich dodał jakieś usprawnienia. W dalszej
kolejności ktoś zebrał pomysły wielu ludzi i zaimplementował w jednym
programie. Dopiero w jeszcze dalszej były próby reprezentacji bitowej, a z
powodu znanych usprawnień do reprezentacji tablicowej, reprezentacja
bitowa wypadała gorzej, zwłaszcza na 32bitowych komputerach. Różne
sprytne usprawnienia do reprezentacji bitowej pojawiły się stosunkowo
niedawno, a już naprawdę świeża jest próba zebraniach wszystkich usprawnień w
jednym programie. Jeśli dla Ciebie, jako dla jednego programisty, jest
to intuicyjny proces, to oznacza, że jesteś lepszy od tych wszystkich
programistów razem wziętych, którzy przyczynili się do obecnego poziomu
reprezentacji bitowej.


> Strasznie zakodowane...
Rozumiem że "strasznie" używasz w znaczeniu "implementacja zepsuta". Wiele
osób taką reprezentację podało jako pierwszy pomysł. Po zastanowieniu podali
różne usprawnienia. A po próbach z reprezentacją bitową program działał
wolniej...


> 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?
Trzy wieże po jednej stronie to akurat nie egzotyczna sytuacja - ale to
mało ważne w naszej dyskusji. To jest po prostu kod rozsądny, jaki
zaproponuje na początku wielu programistów. Niektórzy dodadzą jakieś
usprawnienie, niektórzy kilka usprawnień, jedna osoba raczej nie dojdzie
sama do wszystkich znanych technik.



> > 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.
Ale to jest malutki przykładzik. Z reprezentacją bitową są inne problemy i
jest tych problemów znacznie więcej niż z reprezentacją tablicową. Naiwne
zakodowanie na reprezentacji bitowej z powodu innych problemów działa
gorzej niż wyśrubowana implementacja na tablicy pól/bierek.


> 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.
Taki sam efekt daje zarówno iterowanie w jakimś kierunku szachownicy
jaki i test maskami bitowymi. Chodzi o to, która implementacja jest szybsza.



> 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.
Z tym się nie sprzeczam że to drogi proces.


> > 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?
Nie chodzi o to co mi się wydaje, tylko o to co widziałem. A widziałem jak
wielu programistów podeszło do problemu. Ich podejście było na oko
2-4 razy gorsze niż optymalne.



> 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".
To nie pomysł, to obserwacja. I nie na wszystkich, ale na pewnej
próbie :) Każdy może wziąć jakieś zadanie programistyczne, napisać
swoją implementację, a dopiero potem porównać z najlepszą znaną
implementacją na świecie. Jaki odsetek programistów będzie w 10% od
najlepszej znanej ( 10% od najlepszej znanej, to niekoniecznie 10% od
optymalnej ).



> Heh, rozumiem że to takie testowe turnieje.
Tak, jak się nie ma prywatnego klastra, to można jedynie testować
implementacje/algorytmy na ultra-krótki czas.


> 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.
U mnie trening działał. Gdy regularnie grywałem, to z miesiąca na miesiąc
grałem lepiej. Gdy odstawiałem szachy na dłuższy czas, to znowu grałem
słabo. Potem interesowałem się tylko szachami komputerowymi.


Pozdrawiam

do góry

W dniu 2013-04-16 08:39, AK pisze:
> Użytkownik "bartekltg" <b...@g...com> napisał:
>
>> Oczywisćei zgadzam się, że przejście do wersji (prawie)
>> zawsze prawie liniowej (z kwadratowej) dużo daje.
>
> No przeciez mowie od poczatku roznicu miedzy zwykla
> DFT a FFT (czyli algorytmem Cooleya_Tukeya).

I Twierdzisz, że:

>>> Przed Cooleyem-Tukeyem roslo wykladniczo, a potem liniowo.

Nie, nigdy nie rodło wykładniczo;>


> Gdyby nie bylo FFT to kto wie czy pol automatyki/elektroiniki
> itp by dzis "zostalo w sredniowieczu" (akurat tu szybkosc jest wazna:).
> W kazdym razie dla mnie FFT jest jednym z przykladow
> algorytmu ktory "zmienil dzieje".

To prawda. Ale nigdy nie był on wykładniczy, więc
myślałem, ze masz na myśli jeszcze co innego.

pzdr
bartekltg

do góry

AK <n...@n...com> wrote:
> Użytkownik "bartekltg" <b...@g...com> napisał:
>
>> Oczywisćei zgadzam się, że przejście do wersji (prawie)
>> zawsze prawie liniowej (z kwadratowej) dużo daje.
>
> No przeciez mowie od poczatku roznicu miedzy zwykla
> DFT a FFT (czyli algorytmem Cooleya_Tukeya).
> Gdyby nie bylo FFT to kto wie czy pol automatyki/elektroiniki
> itp by dzis "zostalo w sredniowieczu" (akurat tu szybkosc jest wazna:).
> W kazdym razie dla mnie FFT jest jednym z przykladow
> algorytmu ktory "zmienil dzieje".

Ale długo to trwało, bo Cooley&Tukey nie byli piewszymi, którzy wynaleźli FFT
;)

do góry