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)

[wookieb]

Zależy jakich algorytmów poszukujesz. W phpie nie wykorzystujesz ich tak dużo. Powiem więcej. Prawie wcale. Nie mówie tutaj o "sposobie pobierania danych z bazy" albo ich wyświetlania bo to nie jest algorytm z prawdziwego zdarzenia.

Dlatego dobrze by było gdybyś powiedział mniej więcej o jakie algorytmy ci chodzi.

Ja ostatnio kupiłem książkę "Algorytmy od podstaw" Simon Harris, James Ross - Helion (kosztuje 80zl ale w kolportecze była wyprzedaż i udało mi się wyrwać za połowę ceny (IMG:style_emoticons/default/smile.gif)
Bardzo fajna, nauczy cię także dobrego testowania kodu. Książka opisuje algorytmy za pomocą Javy

[blooregard]

@sztosz - jeśli byłbyś zainteresowany zakupem książki, o której wspomniał @wookieb, zapraszam:
http://allegro.pl/item719567175_algorytmy_od_podstaw.html

Ten post edytował blooregard 29.08.2009, 09:43:15

[sztosz]

Od razu mówię że PHP to mnie akurat mało interesuje (IMG:style_emoticons/default/winksmiley.jpg) bo zwyczajnie nie lubię tego języka, ale zupełnie nie w tym rzecz.

Mamy np. sito Eratosthenesa i czytam teorię i piszę sobie kod. Niby jest OK, a potem się okazuje że nie do końca zrozumiałem założenia (albo byłem zmęczony, bo po nocach piszę dla siebie kod (IMG:style_emoticons/default/winksmiley.jpg) )i nie wwalam wszystkich wielokrotności liczb pierwszych z możliwych kandydatów, ergo robi się brute force zamiast algorytmu.

Inny przykład: http://en.wikipedia.org/wiki/Sieve_of_Atkin Jest sobie sito Atkina, też do znajdywania liczb pierwszych i czytam pseudo kod i założenia i odechciewa mi się czytać dalej, bo zaczynam mieć problem z notacja, a jeśli tak prostego algoytmu nie pojmuję od razu to nie jest dobrze.

Albo sito Sundaram http://en.wikipedia.org/wiki/Sieve_of_Sundaram, to niby rozumiem ale nie umiem przepisać do edytora kodu źródłowego.

Kiedyś Matematyka była moim konikiem, potem różne moje decyzje odsunęły mnie daleko od matematyki a teraz chciałbym do niej wrócić. http://projecteuler.net/ to świetna strona z zadaniami, zadania wydają się trywialne, ale ja mam problem z wymyśleniem szybkiego i sprawnego algorytmu, metoda brute force to nie jest ładna metoda (IMG:style_emoticons/default/winksmiley.jpg) Stąd więc moje pytanie o jakieś podręczniki uczące algorytmiki, może ktoś pamięta jakiś dobry podręcznik ze studiów?

[wookieb]

Niestety ta książka akurat sit nie omawia.
Na stronie helionu możesz zobaczyć spis treści.
Natomiast w googlach łatwo znalazłem parę polskich wyjaśnień tych algorytmów. Nawet spoko wyjaśnione. Pomijając błędy w tekście i "rysunkach"


//EDIT

Z ciekawości ,algorytm sita Eratosthenesa o którym mówiłeś, udało mi się zaimplementować tak.

[PHP] pobierz, plaintext 
 
$min = 2;
$max = 1000;
 
$tab = range($min, $max);
 
// pozycja liczby z tablicy na której jesteśmy
$actualPos = 0;
while( $actualPos < count($tab) )
{
	// buforujemy sobie długość tabeli
	$tabLength = count($tab);
 
	// rozpoczynamy od nastepnego numeru od aktualnie badanego
	for($i = ($actualPos+1); $i<$tabLength; $i++)
	{
		// sprawdzenie podzielnosci
		if( ($tab[$i] % $tab[$actualPos]) === 0 )
		{
			unset($tab[$i]);
		}
	}
 
	// resetujemy klucze
	$tab = array_merge($tab);
 
	// przechodzimy do nastepnej liczby
	$actualPos++;
}
 
print_r($tab);
[PHP] pobierz, plaintext 

Ten post edytował wookieb 29.08.2009, 10:34:21

[thek]

Tak naprawdę to nie ma dobrej książki do algorytmiki. Można mieć jedynie książki z optymalnymi algorytmami do rozwiązania określonego popularnego zagadnienia. Algorytm to przecież w końcu tylko jedna z form zapisu jakiegoś działania. Sita są tutaj dobrym przykładem.

1. Idź do pierwszego elementu zbioru,
2. Wyrzuć z niej wszystkie będące za nim, a które są jego wielokrotnością, aż do osiągnięcia końca zbioru,
3. Przejdź do kolejnego elementu i powtórz krok 2
4. Jeśli osiągnąłeś ostatni element zbioru - zakończ.

Problemem w przypadku implementacji jest jedynie to, że musisz uważać na to, iż zbiór się cały czas zmniejsza a przechodzić zawsze musisz do kolejnego elementu. I to jest jedyna trudność (IMG:style_emoticons/default/smile.gif)
Ja dla przykładu jaki zrobił wookieb nie mam nic do zarzucenia. Jedyną optymalizacja jaką bym próbował zrobić to ewentualne przerobienie pętli FOR na WHILE, by uniknąć resetowania indeksów w tablicy. Poza tym nie można temu algorytmowi nic zarzucić.

Algorytmikę trzeba czuć. I to jest właśnie umiejętność cechująca dobrego programistę. Po spojrzeniu na zagadnienie widzi on bowiem schemat działania i na jego podstawie tworzy algorytm w kodzie. To prawie jak w filmie "Piękny umysł", gdy koleś patrzy na ciąg liczb i znajduje zależności go cechujące. Może właśnie dlatego dobry informatyk to w pewnym sensie schizofrenik? (IMG:style_emoticons/default/winksmiley.jpg)

Ten post edytował thek 29.08.2009, 19:43:57

[Shadowsword]

Kup "Wprowadzenie do algorytmów" Wydawnictwa Naukowo-Technicznego. Lepszej książki nie znajdziesz.

[sztosz]

No ładnie książka wszędzie kosztuje około 140 zł, a do tego myk jest taki że nigdzie nie ma jej w sprzedaży. Ale wszystkie opinie jakie przeczytałem na jej temat są co najmniej pozytywne, wszyscy zdają się pisać że to najlepsza książka w tej dziedzinie. Jest też na allegro za 150 zł. Może gdzieś w internecie znajdę jakiś rozdział do przeczytania i zobaczę czy warto wydać aż tyle pieniędzy.

[Shadowsword]

Naprawdę warto. Jest gruba, dokładnie opisuje naprawdę dużo algorytmów (w większości opisuje też jak zaimplementować). W wakacje byłem na obozie informatycznym i 3/4 osób miało tę książkę. Poszukaj starszego wydania na allegro - można trafić za 1/4 ceny.

[l0ud]

Poza tym nie można temu algorytmowi nic zarzucić.

Oprócz tego że jest kompletnie niewydajny i przekombinowany, a jak wiadomo algorytm niewydajny = spaprany (IMG:style_emoticons/default/tongue.gif)
Troszkę to uprościłem:

[PHP] pobierz, plaintext 
<?php
 
$max = 10000;
 
$tab = range(0, $max);
 
for ( $actualPos=2; $actualPos <= $max; $actualPos++) {
 
	// rozpoczynamy od następnego wystąpienia badanego numeru
	// o ile nie jest skreślony
	if (isset($tab[$actualPos]))
		for ($i = $actualPos*2; $i <= $max; $i += $actualPos)
			unset($tab[$i]);
}
 
//usuwamy pozostałe śmieci
unset($tab[0],$tab[1]);
 
print_r($tab);
 
?>
[PHP] pobierz, plaintext 

[wookieb]

Oprócz tego że jest kompletnie niewydajny i przekombinowany, a jak wiadomo algorytm niewydajny = spaprany (IMG:style_emoticons/default/tongue.gif)

Och mój Wielebny Panie i Władco. Nie godzien jestem zwracać się tu do ciebie. Lecz moja wrodzona chęć pomocy innym oraz wyprowadzania ich z błędu nakazuje mi tutaj poinformować Cię o pochopności twej opinii o Panie.
Na dowód tego załączam ten oto rękopis do zapoznania się przez Mistrza.

[PHP] pobierz, plaintext 
 
$nums = array();
 
function getmicrotime()
{ 
    list($usec, $sec) = explode(" ",microtime()); 
    return ((float)$usec + (float)$sec); 
}
 
function t1()
{
    $min = 2;
    $max = 100;
    global $nums;
    $nums[0]=0;
 
    $tab = range($min, $max);
 
    // pozycja liczby z tablicy na kt?rej jeste?my
    $actualPos = 0;
    while( $actualPos < count($tab) )
    {
        // buforujemy sobie d?ugo?? tabeli
        $tabLength = count($tab);
 
        // rozpoczynamy od nastepnego numeru od aktualnie badanego
        for($i = ($actualPos+1); $i<$tabLength; $i++)
        {
            $nums[0]++;
            // sprawdzenie podzielnosci
            if( ($tab[$i] % $tab[$actualPos]) === 0 )
            {
                unset($tab[$i]);
            }
        }
 
        // resetujemy klucze
        $tab = array_merge($tab);
 
        // przechodzimy do nastepnej liczby
        $actualPos++;
    }
 
    return $tab;
}
 
 
function t4()
{
    $max = 1000;
    $tab = range(0, $max);
    global $nums;
    $nums[1]=0;
 
    for ( $actualPos=2; $actualPos <= $max; $actualPos++) 
    {
 
        // rozpoczynamy od nast?pnego wyst?pienia badanego numeru
        // o ile nie jest skre?lony
        if (isset($tab[$actualPos]))
        {
            for ($i = $actualPos*2; $i <= $max; $i += $actualPos)
            {
                $nums[1]++;
                unset($tab[$i]);
            }
        }
 
    }
    unset($tab[0],$tab[1]);
 
    return $tab;
}
 
 
$start = getmicrotime();
for($i=0; $i<1000; $i++)
{
t1();
}
echo (getmicrotime()-$start).' - ';
 
 
$start = getmicrotime();
for($i=0; $i<1000; $i++)
{
t4();
}
echo (getmicrotime()-$start);
 
 
print_r($nums);
[PHP] pobierz, plaintext 

Ten post edytował wookieb 29.08.2009, 22:48:49

[sztosz]

@Shadowsword: ściągnąłem kilka rozdziałów, przeczytałem i to jest właśnie to czego szukam, a przynajmniej tak po przeczytaniu kawałka (+spis treści) mi się wydaje (IMG:style_emoticons/default/winksmiley.jpg)

A co do sita Eratosthenesa, to w którym miejscu z liczb kandydujących na "pierwsze" (czyli zmienna $tab) wyrzucacie wielokrotności już znalezionych liczb pierwszych?

[PHP] pobierz, plaintext 
for ($i = $actualPos*2; $i <= $max; $i += $actualPos)
unset($tab[$i]);
[PHP] pobierz, plaintext 

To powyżej jeśli się nie mylę tak? Ale u ~wookieb nie widzę czegoś podobnego, tylko raczej brute force, czyli sprawdzanie po kolei czy dana liczba ma tylko dwa dzielniki.

UPDATE Wynik mi wyszedł taki: 11.087609052658 - 0.76528286933899, czyli algorytm ~lOuda jest ponad 11 razy szybszy, do tego poprawnie zaimplentowany. Oczywiście p wyrównaniu szans, czyli zakładając że robimy tablicę dla 1000 elementów, a nie 100 w jednym skrypcie, a 1000 w drugim (IMG:style_emoticons/default/winksmiley.jpg)

Ten post edytował sztosz 29.08.2009, 22:43:35

[wookieb]

UPDATE Wynik mi wyszedł taki: 11.087609052658 - 0.76528286933899, czyli algorytm ~lOuda jest ponad 11 razy szybszy, do tego poprawnie zaimplentowany. Oczywiście p wyrównaniu szans, czyli zakładając że robimy tablicę dla 1000 elementów, a nie 100 w jednym skrypcie, a 1000 w drugim

A widzisz kurde racja. Nie zauwazyłem poważnego błędu. Kajam się i przepraszam Loud (IMG:style_emoticons/default/smile.gif)

Ten post edytował wookieb 29.08.2009, 22:53:05

[sztosz]

U mnie dzieje się to tutaj

[PHP] pobierz, plaintext 
for($i = ($actualPos+1); $i<$tabLength; $i++)
        {
            $nums[0]++;
            // sprawdzenie podzielnosci
            if( ($tab[$i] % $tab[$actualPos]) === 0 )
            {
                unset($tab[$i]);
            }
        }
[PHP] pobierz, plaintext 

@wookieb a mógłbyś dokładniej opisać co robisz bo mam mały problem ze zrozumieniem co się w tym kawałku kodu dzieje.

Ten post edytował sztosz 29.08.2009, 22:59:16

[wookieb]

Jeszcze mała uwaga Loud (IMG:style_emoticons/default/smile.gif) Ale tym razem słuszna (IMG:style_emoticons/default/tongue.gif)

[PHP] pobierz, plaintext 
$sqrt=sqrt($max);
    for ( $actualPos=2; $actualPos <= $sqrt; $actualPos++) 
[PHP] pobierz, plaintext 

Strasznie zagmatwałem swój algorytm (tudzież kompletnie źle zaimplementowałem algorytm), właśnie przez "brute force". Zamiast skreślać z góry określone prawidłowe liczby to bawiłem się na około. Chyba mój algorytm sprawdził by się tylko w wyszukiwaniu liczb pierwszych w ciągach nieuporządkowanych, dodatkowo z lukami.

Co się dzieje...
1) Wybieram pierwszą liczbę z tablica ($actualPos wskazuje na klucz tablicy, który będzie naszym dzielnikiem)
2) Lecę od następnego elementu do końca tablicy i sprawdzam, która liczba jest podzielna przez dzielnik (pętla którą zacytowałeś)
3) jeżeli jest podzielna to usuwam ją.
4) resetuje klucze tablicy tak aby pętla for miała mniej iteracji, oraz żeby łatwo wybrać następny dzielnik poprzez iterację $actualPos

Ten post edytował wookieb 29.08.2009, 23:12:17

[thek]

Kod l0ud'a jest szybszy tylko z jednego powodu... Ma on bowiem przypisanie do indeksu takiej samej wartości (IMG:style_emoticons/default/smile.gif) Czyli pod polem tablicy o indeksie 4 ma wartość 4. Dlatego może on usuwać konkretne indeksy BEZ sprawdzania ich zawartości. Dlatego właśnie musi indeksować tablicę zakresem od 0 do max. Indeksowanie od 1 lub od 2 posypało by mu cały algorytm. Rozmawiając z wookieb także ten algorytm mu opisałem, ale z racji startowania od 2 opisałem mu to, cytując za PW z godziny 21:42 wymienianymi między nami:
"Szukamy liczb podzielnych przez tą pod indeksem 10... załóżmy, że jest to 11. Dla tego konkretnego zadania wystarczyło by więc bym nie naprawiał tabeli i usunął wszystkie o indexach 10+11, 10+2*11, 10+3*11 itd. aż do największego, mniejszego niż 1000".
Naprawianie tabeli to oczywiście reindeksowanie (IMG:style_emoticons/default/smile.gif) Podałem jeszcze jeden algorytm dla którego nieistotne jest naprawianie tabeli, ale zdanie się na ArrayIterator i używanie next(), ale jak wiadomo zdawanie się na nie może wprowadzić opóźnienia. W przypadku zaś masowego kasowania elementów z tablicy (a tak było w tym wypadku) okazało się to mocno zmniejszajace skuteczność iteratora (IMG:style_emoticons/default/winksmiley.jpg)

[sztosz]

Ale cała szybkość nie polega na tym że do danego indeksu ma przypisaną jakąś wartość. Tylko na tym że nie sprawdza po kolei czy dana liczba ma dokładnie dwa dzielniki i jest pierwszą. Pierwsze liczby wyskakują mu od tak po prostu, cała sztuka polega na tym żeby usunąć wielokrotności już znalezionych, reszta to są pierwsze. I na tym polega zasada działania sita Eratosthenesa. I właśnie dlatego potrzebuję książki do algorytmiki, aby wyuczyć się pewnych schematów. A także przede wszystkim po to, by mając dany algorytm nie kombinować na siłę, tylko zrozumieć ten algorytm i go zakodować w danym języku programowani (a kiedy już działa, można myśleć o optymalizacji)

A o różnych algorytmach znajdowania liczb pierwszych można poczytać tu: http://krenzel.info/?p=83

Ten post edytował sztosz 30.08.2009, 02:09:57

[thek]

A popatrz sobie na wyjaśnienie moje oraz chłopaków. My nie sprawdzamy czy ma dokładnie tylko 2 dzielniki (IMG:style_emoticons/default/winksmiley.jpg) Bierzemy sobie jakąś liczbę i lecimy w pętlach usuwając jej kolejne wielokrotności (algorytm L0uda) lub sprawdzając czy liczba dzieli się przez tę, która wybraliśmy (algorytm wookieb). Różnica pomiędzy tymi dwoma polega na tym, że w przypadku pierwszego ważne jest to, czy dane są ustawione jako ciąg kolejnych liczb naturalnych. Jeśli tak nie będzie to algorytm jest bezużyteczny. Wystarczy, że liczby będą nieco przemieszane i będzie klops, bo przez to usunąć można liczby pierwsze z wyników. Algorytm drugi na mieszanie jest odporniejszy, ale też nie bez wad. W wyniku przemieszania pokaże nie tylko liczby pierwsze. Największym spowalniaczem kodu drugiego jest ciągłe robienie modulo i jego sprawdzanie. Tymczasem algorytm pierwszy ma to kompletnie gdzieś (IMG:style_emoticons/default/winksmiley.jpg) Po prostu kasuje hurtem bez sprawdzania zawartości. Dlatego jest taki szybki (IMG:style_emoticons/default/smile.gif) Gdyby jednak zaczynał nie od 0 ale 1 lub 2, to trzeba by go zmodyfikować tak jak opisałem w moim poście wyżej: pobrać wartość znajdującą się w elemencie tablicy o danym indeksie i o tyle indeksów przeskakiwać. Algorytm ten ma jeszcze jedną zaletę. Jest bardzo podatny na zrównolegnianie. Od około 21 do północy wymieniałem z wookiemb PW i część z nich poświęciłem na prezentację działania tego algorytmu na 5 procesorach (IMG:style_emoticons/default/winksmiley.jpg) By było to ładnie widoczne zrobiłem niezwykle uproszczony przykład szukania liczb pierwszych od 2 do 25. Hipotetycznie wszystkie liczby dla algorytmu wookiego były znalezione po 15 operacjach, algorytm pierwszy puszczony na 5 prockach zrobiłby to w 11 operacjach. Zapewne na 4 by to zrobił w 11, ale wprowadziłem bardzo wiele uproszczeń, które i tak działały na korzyść algorytmu wookiego (wszystkie operacje niemalże pomijane i tylko kasowanie uwzględniałem), czyli całość operacji sprawdzania, modulo, kasowania była równa temu samemu co samego kasowania, co jest jawnym naciąganiem, gdyż zajmuje to różne ilości czasu procesora, ale nie chciałem utrudniać odbioru idei. Przebiegi czasowe wykonywane jednocześnie dla kilku procesorów to dla wielu abstrakcja i konieczne są uproszczenia.

Co do algorytmów i ich pisania to sie już wypowiedziałem jak sądzę. Trzeba zrozumieć istotę problemu, złapać zależności występujące i układać to w bloczki. Nieraz w trakcie się okazuje, że o czymś zresztą zapomnieliśmy, czegoś nie uwzględniliśmy. Zresztą podczas pisania dowolnej aplikacji szybko się o tym programiści przekonują. Zwłaszcza Ci, którzy siedzą w obiektówce (IMG:style_emoticons/default/smile.gif)

[sztosz]

OK, może ten algorytm jest lepszy przy "zrównolegnianiu" (co to w ogóle za słowo? w słowniku nie znalazłem, google pomocne też nie jest), może jest odporne na coś tam, ale ~wokieb chciał zaimplentować sito Eratosthenesa, a mu się do tej pory nie udało.

Poza tym co to za argument że liczby będą przemieszane? Jeśli znajdujemy szukać czy liczby ze zbioru są pierwsze czy nie, to implentujemy jakiś szybki algorytm z rodziny "Primality test", jeśli robimy generator liczb pierwszych to nie będziemy mieć "przemieszanych liczb".

Nie twierdzę że algorytm jest zły, ale są lepsze i tyle.

lub sprawdzając czy liczba dzieli się przez tę, która wybraliśmy

W nocy naprawdę wolniej myślę, teraz jak popatrzyłem na kod to wreszcie zauważyłem co naprawdę się dzieje (IMG:style_emoticons/default/smile.gif) (i znów się przekonałem jaką PHP ma nieczytelną składnie (IMG:style_emoticons/default/tongue.gif) )

[rzymek01]

również polecam "Wprowadzenie do algorytmów", ale ostrzegam, że książka jest na wysokim poziomie i przed przystapieniem do jej przeczytania zalecam zapoznanie się chociażby z grafami, czy przeczytanie książki "Algorytmy" M.Sysło w celu wprowadzenia się w temat (IMG:style_emoticons/default/tongue.gif)

po lekturze "Wprowadzenie do algorytmów" polecam jeszcze Kombinatorykę dla programistów (choć sam nie czytałem, bo uważam, że jeszcze za mały człowieczek ze mnie (IMG:style_emoticons/default/haha.gif) )