Książka do Algorytmiki Opcje

[sztosz]

Kuleje jeśli chodzi o kwestie wynajdywania odpowiednich algorytmów żeby rozwiązać dany problem, czasem czytam o jakimś algorytm w necie i nie mam pojęcia jak go ugryźć.

Stąd moje pytanie: Czy jest jakaś książka z której dowiem się sprawnie tworzyć algorytmy, na czym to dokładnie polega? Ale tak od podstaw? W ogóle nie wiem czy w dobrym kierunku szukam, ale trochę błądzę po omacku. Nigdy nie kończyłem studiów informatycznych, ani matematycznych, więc mam w głowie tylko strzępki informacji na ten temat z liceum (IMG:style_emoticons/default/winksmiley.jpg)

[thek]

Zrównolegnianie to proces przekształcania kodu z sekwencyjnego na wieloprocesorowy. Jest to raczej mało używane określenie i mocno nieformalne, bo też czy ktokolwiek interesuje się tym poza bardzo ścisłym gronem znających się na tym? Ciekawe czy masz na to inną nazwę. Ja się nie spotkałem z innym określeniem technicznym, więc używam tego, jakie było powszechne u mnie na studiach wśród prowadzących (miałem jako przedmiot przetwarzanie współbieżne i równolegle ). Jak by to brzmiało po angielsku? Sequence to multiple processor recoding (code coversion?)? (IMG:style_emoticons/default/winksmiley.jpg)
To, że kod wookiego jest mniej optymalny od L0ud'a wynika z narzutu czasowego związanego z reindeksowaniem tablicy i czasem dostępu do zmiennych. Gdyby było to pomijalne to algorytm wookiego jest lepszy z prostej przyczyny - nie kasuje już nie istniejących indeksów. W przypadku C++ nie mógłbym sobie pozwolić na kasowanie tylko musiałbym nadpisywać wartości neutralnym elementem bo kasowanie szybko skończyło by się błędami ochrony pamięci. To, który z nich jest bardziej optymalny jest więc tak naprawdę zależne od implementacji pewnych rozwiązań w danym języku programowania. Gdyby reindeksacja była szybsza to możliwe, że oba byłyby porownywalne. Tablica wookiego za kazdym przejściem pętli jest bowiem "naprawiana" i nigdy w niej nie następuje działanie na nie istniejących indeksach. Tablica u L0uda, gdybyś sprawdzał zwroty funkcji unset co chwilę próbuje usuwać nie istniejące elementy, przez co robi wiele pustych przebiegów. Widać to choćby dla liczby 5, która co 2 cykl próbuje usunąć 10, 20, 30, a te już zostały przecież przez 2 w co 5 kroku usunięte (IMG:style_emoticons/default/winksmiley.jpg) Całościowo jednak algorytm jest szybszy, ponieważ mimo większej liczby operacji odwołanie się bezpośrednio do konkretnego indeksu tablicy jest szybsze niż sprawdzenie modulo określonego indeksu już na poziomie cykli procesora. Kto przerabiał architekturę komputerów ten wie o czym mówię. Algorytm pierwszy jest bardziej optymalny i logiczniejszy pod kątem algorytmicznym, ale drugi ma lepszą implementację w php. To jest jedyna różnica między nimi (IMG:style_emoticons/default/smile.gif) Oba są równie dobre. A jaki wpływ ma implementacja na szybkość? Wczoraj z wookiemb kodwookiego przerobiony został tak, by używał ArrayIterator i tym samym nie przejmował reindeksowaniem tablicy tylko używal next(). Wykonano 1000 razy szukanie dla liczb od 2 do 1000, przy czym algorytm L0ud'a by nieco inny, według mojej koncepcji (czyli sprawdzanie wartości elementu przy każdej iteracji FOR i skoki o wartość pola pod danym indeksem), by mógł startować od 2 a nie od 0.
Algorytm woobieb: 13 sekund
Algorytm wookieb z sqrt: 8 sekund
Algorytm L0ud'a: 1s z hakiem
Algorytm na ArrayIterator: ponad 4 minuty(!)
Jak widzicie implementacja gra rolę poważną. ArrayIterator ma poważne problemy gdy ostro kasujemy tablice do jakiej jest przypisany. Wersja z sqrt jest prawidłowa, ponieważ od elementu sqrt(długość_tablicy) pętla robi puste przebiegi, gdyż nie ma prawa już znaleźć swoich wielokrotności.
Mogę więc zaprezentować prosto różnice pomiędzy obydwoma:
Wookieb: tablica zawsze działa tylko na elementach jeszcze nie sprawdzonych,
L0ud: tablica jest skuteczna, gdyż nie sprawdza zawartości indeksów, polegając na równoważności indeksu z wartością pod nim przechowywaną. Zmiana miejsca startowego z 0 na dowolne inne wymusza jednokrotne sprawdzenie zawartości indeksu.