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

[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.

[sztosz]

Parallel computing (Obliczenia równoległe), tak się to chyba nazywa i domyślałem się że to o to może Ci chodzić.

Algorytm pierwszy jest bardziej optymalny i logiczniejszy pod kątem algorytmicznym, ale drugi ma lepszą implementację w php.

A mi właśnie o to chodzi aby pisać sobie "optymalne i logiczniejsze pod kątem algorytmicznym programy". Poszukuję książki która mnie poprowadzi do tego jak znajdować dobre algorytmy i tyle.

A PHP jest pochromolone i tyle w temacie PHP (IMG:style_emoticons/default/winksmiley.jpg)

Ten post edytował sztosz 30.08.2009, 20:09:15

[l0ud]

Algorytm pierwszy jest bardziej optymalny i logiczniejszy pod kątem algorytmicznym

A ja się spytam, w którym miejscu? (IMG:style_emoticons/default/tongue.gif) Sam kod testujący podany przez wookieb, wyraźnie wskazuje że ilość iteracji drugiej pętli w przedziale 2-1000 w jego algorytmie jest 10x większa (IMG:style_emoticons/default/tongue.gif) Do lepszej implementacji w c++ też się nie mogę zgodzić: w moim przypadku wystarczy zainicjować tablicę o ilości elementów max+1, wypełnić ją boolami o jednakowej wartości (np. true) - chociażby memsetem, następnie robić dokładnie to samo co w PHP, zastępując unseta ustawieniem boola na false, a isseta sprawdzeniem, czy bool == true. Później wykorzystać indeksy tych elementów, które są równe true.
A teraz znajdź mi sposób wydajnego przeorganizowania indeksów tablicy w C++ (niemożliwe jest przecież usunięcie jej elementu), oraz wyjaśnij jak dziesięciokrotnie więcej operacji modulo może być równie wydajne od ustawienia boola na false, które to jest operacją atomową (niepodzielną, a więc pewnie krótką) (IMG:style_emoticons/default/smile.gif)

Natomiast uwaga wookieb odnośnie pierwiastka, jest jak najbardziej słuszna (IMG:style_emoticons/default/winksmiley.jpg)

Ten post edytował l0ud 30.08.2009, 22:14:21

[thek]

Wczoraj źle zrozumiałem algorytm (IMG:style_emoticons/default/smile.gif) Patrzyłem na niego jako:
1.Weź element z tablicy
2. Kolejny element sprawdź czy jest wielokrotnością wybranego elementu,
3. Jeśli tak to usuń, jeśli nie nie rób nic,
4. Powtarzaj 2 i 3 aż do końca tablicy,
5. Wtedy weź następny wolny i powtarzaj od kroku 2 aż osiągniesz ostatni element tablicy
Dlatego uważałem, że kod wookiegob jest zgodniejszy z algorytmem niż Twój. Dopiero gdy trochę zmęczenie mi opadło ( wczoraj moja mała córeczka dała mi trochę popalić i dopiero dziś na to na spokojnie późnym popołudniem zerknąłem ) przyjrzałem sie lepiej samemu opisowi algorytmu (wolę przeczytać zawsze jak on działa niż implementować pseudokod). No i muszę przyznać, że się myliłem co do implementacji algorytmu. Twój jest niemal kropka w kropkę dokładnie tym, jak go opisano.
Co do implementacji w c++ to nie można usuwać elementów tablicy, jak sam napisałeś, bo inaczej byłyby jaja i sypały by się błędy ochrony pamięci, a sam program działałby niepoprawnie. Podany przez Ciebie sposób implementacji w C++ jest IMHO bardzo dobry i szybki.
Co do algorytmu wookiegob, to jego implementacja nie byłaby trudna, tyle że konieczna byłaby funkcja napisana samemu do reindeksacji. No chyba, że zdalibyśmy się na STL (IMG:style_emoticons/default/smile.gif) Dla tej wersji myślę że list, slist lub sequence byłyby odpowiednie. Odpadło by nam wtedy martwienie o reindeksowanie (te typy mają to wbudowane). Myślę l0ud, że słyszałeś o STL (Standard Template Library). Bardzo fajna biblioteka, implementująca ciekawe rozwiązania, w tym iteratory znane także w PHP. Tyle że bezpośrednie odwołania do indeksów tablicowych i tak będą o wiele szybsze. Niezależnie od tego jakiego języka byśmy używali.
To z pierwiastkiem to pewien "hack" w algorytmach by obniżyć ilość pustych przebiegów. Też mi o tym na algorytmach podczas studiów powiedziano na zajęciach.

Co do "parallel computing" to jest to nazwa dla "przetwarzanie równoległe", ale jaki byłby angielski i polski odpowiednik na: "działania mające na celu przetworzenie kodu sekwencyjnego do postaci równoległej"? A to właśnie nazywaliśmy "zrównolegnianiem" (IMG:style_emoticons/default/winksmiley.jpg)

[rzymek01]

[PHP] pobierz, plaintext 
<?php
 
/* wykorzystane założenia:
- rozważamy liczby tylko nieparzyste
- przy eliminacji wielokrotości liczby p, eliminujemy tylko liczby nieparzyste,
	więc postaci: p^2, p(p+2), p(p+4), ...
	i jeszcze dlatego, że liczby k*p zostały przesiane wcześniej
 
- wykorzystałem wskazówki i pseukod z książki "Algorytmy", bo komu się chce na nowo koło odkrywać (IMG:style_emoticons/default/tongue.gif) 
 
*/
 
function getmicrotime() // z postu @wookieweb
{ 
    list($usec, $sec) = explode(" ",microtime()); 
    return ((float)$usec + (float)$sec); 
}
 
function Sito($N) {
/* Sito
 * Wejście: parzysta liczba naturalna N
 * Wyjście: tablica liczb pierwszych z zakresu liczb naturalnych <2, N+1>
*/
 
	// inicjalizacja zmiennych
	$M = $N / 2;
	$aSito = array_fill(1, $M, true);
 
	$i = 1;
	$p = 3;
	$q = 4;
 
	while (true) {
		if ($aSito[$i]) {
			$j = $q;
 
			while ($j <= $M) {
				$aSito[$j] = false;
				$j += $p;
			}
		}
 
		++$i;
		$p += 2;
		$q += 2*$p - 2;
 
		if ($q > $M)
			break;
 
	}
 
	$aPierwsze = array();
	for ($i = 1; $i <= $M; ++$i) {
		if (!$aSito[$i])
			continue;
 
		$aPierwsze[] = 2*$i + 1;
	}
 
	return $aPierwsze;
}
 
$start = getmicrotime();
Sito(385000);
$end = (getmicrotime()-$start).'<br/>';
 
echo $end;
 
?>
[PHP] pobierz, plaintext 

oczywiście ten algorytm jest pamięciożerny, bo potrzebuje zarezerwować tablicę int [N/2];
ale w miarę szybki, bo jak widać w kodzie u siebie na kompie bez problemów wykonuje się sprawdzenie dla prawie N = 400 000 w nie wiem jakim czasie, ale na pewno mniejszy niż 1s (IMG:style_emoticons/default/tongue.gif)
dla większych danych przekraczam 16MB
przy zamianie na bool i zrezygnowaniu z array_fill, skrypt nadal potrzebuje bool [N/2] pamięci, ale o wiele wiele mniej niż w poprzednim rozwiązaniu (z obliczeń wychodziło, że przy array_fill jedna komórka zajmowała ~35B o_O )
added: ktoś wie dlaczego tablica bool [400 000] przekrecza 16MB, jeśli powinna zajmowac ~0,4MB?

PS. zaraz policzę czas
średni czas przy 1000 pomiarach wyniósł 0.150357570168s (N=385000)

EDIT:
cofam info o array_fill - mój błąd
o dziwo bez array_fill,- użycie for, czas spadł do 0.03382396698s (N=385000)
oraz rozmiar lokowanej tablicy stał się "normalny"

i teraz w czasie: 0.882550001144s, mogę wykonać algorytm dla danych N=10 000 000
przy prostej operacji dodawania/usuwania zer przy N, można zobaczyć, że algorytm działa w czasie liniowym:

added: @sztos, teraz już wszystko powinno być ok, wkradł się błąd...
tylko zmiejsz N na ~400 000, bo nie wiem czemu ta tablica tak dużo zajmuje,
zaraz napiszę program w C i zobaczymy czasy (IMG:style_emoticons/default/biggrin.gif)

Ten post edytował rzymek01 31.08.2009, 16:16:40

[sztosz]

W Pythonie

[PYTHON] pobierz, plaintext 
from time import time
 
def primes2(maximum):
    primesList = [True]*(maximum+1)
    primesList[0] = False
    primesList[1] = False
    i = 2
    while i < ((maximum/i)+1):
        if primesList[i] == True:
            for j in xrange(i, (len(primesList)/i)+1):
                try: primesList[j*i] = False
                except: pass
        i += 1
    for i in xrange(len(primesList)):
        if primesList[i] == True:
            print i
 
def test3():
    t = time()
    primes2(100000000)
    print time()-t
 
test3()
[PYTHON] pobierz, plaintext 

Przy wypisywaniu każdej liczby pierwszej w nowej linijce:

Kod

maximum=10000:       0.0209999084473
maximum=100000:      0.198999881744
maximum=1000000:     2.31999993324
maximum=10000000:   21.8559999466
maximum=100000000: 208.60800004

Ale teraz musimy wziąć pod uwagę że funkcja print w Pythonie i pętla wypisująca te liczby zabiera naprawdę dużo czasu, bo:


Tak więc zamiast wypisywać wyniki policzymy tylko sam czas znajdowania liczb:

Kod

maximum=10000:      0.00599980354309
maximum=100000:     0.0450000762939
maximum=1000000:    0.534999847412
maximum=10000000:   5.61600017548
maximum=100000000: 58.6970000267

I jeszcze jedno pytanie @rzymek01: Jak wyświetlić w twoim skrypcie te liczby pierwsze? Bo ze mnie naprawdę jest noga w PHP (IMG:style_emoticons/default/winksmiley.jpg)

[PHP] pobierz, plaintext 
$start = getmicrotime();
echo var_dump(Sito(100000000));
$end = (getmicrotime()-$start).'<br/>';
[PHP] pobierz, plaintext 

Daje mi coś takiego: array(0) { } 14.386470079422 :/

Wynik mi wyszedł taki: 11.087609052658 - 0.76528286933899, czyli algorytm ~lOuda jest ponad 11 razy szybszy[...]

Mój algorytm, dla 1000 liczb, 1000 razy powtórzony: 0.315999984741, ale w Pythonie, nie wiem jak w PHP by wyglądał czas.

Ten post edytował sztosz 31.08.2009, 19:30:52

[l0ud]

added: ktoś wie dlaczego tablica bool [400 000] przekrecza 16MB, jeśli powinna zajmowac ~0,4MB?

Bo nie odnosisz się do pamięci bezpośrednio, a wszystkie zmienne w PHP są obarczone pewnym narzutem, w tym przypadku zmienna zajmuje ponad 400% tego, co w C++. Witaj w świecie nieekonomicznego programowania w językach wysokiego poziomu (IMG:style_emoticons/default/tongue.gif)

[thek]

Zabrzmiało to jakby C++ sam nie był językiem wysokiego poziomu (IMG:style_emoticons/default/winksmiley.jpg)

[sztosz]

Nadal jest błąd: [32680]=> int(385001) to jest ostatni element tablicy a nie powinno go być (IMG:style_emoticons/default/winksmiley.jpg) Ps. Przy tych wartościach u mnie cały proces pythona zajmuje 3.5 MB z tablica i resztą.

Twój algorytm na moje maszynie wraz z "echo var_dump(Sito(385000));" to około 0.9 s mój to około 1s. Jak pominiemy w obu wyświetlanie wyników, twój około 0.27s, mój około 0.2s

Co powiesz na przepisanie mojego algorytmu do PHP i sprawdzenie wyników? Ja jak znajdę dzisiaj więcej czasu to spróbuje z twoim w Pythonie.

PS. A największe jaja są takie, że nie jestem pewien czy założenia w moim algorytmie są poprawne, po jakimś czasie przestałem je rozumieć, a mimo to podaje poprawne liczby (IMG:style_emoticons/default/winksmiley.jpg) I dlatego potrzebuje czegoś o algorytmach, żeby nauczyć się odpowiednio myśleć (IMG:style_emoticons/default/tongue.gif)

Ten post edytował sztosz 31.08.2009, 16:59:35

[l0ud]

Zabrzmiało to jakby C++ sam nie był językiem wysokiego poziomu (IMG:style_emoticons/default/winksmiley.jpg)

No cóż, asembler to nie jest (zwłaszcza używając stl'a), ale i tak całość stoi duużo niżej niż wszystkie te języki interpretowane (IMG:style_emoticons/default/winksmiley.jpg)

Tak właściwie to możemy zebrać tutaj propozycje realizacji tego sita, a następnie zaimplementować je w PHP i C++ - porównując wydajność samego algorytmu jak i języka(/kompilatora) (IMG:style_emoticons/default/smile.gif)

[sztosz]

A przede mną naprawdę dużo nauki, prosta rekurencja = brak pustych przebiegów pętli:

[PYTHON] pobierz, plaintext 
def erat(l):
    if not l or l[0]**2 > l[-1]:
        return l
    else:
        return [l[0]] + erat([i for i in l if i%l[0]])
 
erat(range(2,1000))
[PYTHON] pobierz, plaintext 

A jednak nie, przy porównaniu przy maximum dla 100000 mój algorytm nawet się trzyma (IMG:style_emoticons/default/winksmiley.jpg) mój: 0.540700006485 rekurencja: 7.29569997787 (IMG:style_emoticons/default/winksmiley.jpg)

Pamięć:
mój 3.5 MB
rekurencja: 15.7 MB (IMG:style_emoticons/default/winksmiley.jpg)


Ten post edytował sztosz 31.08.2009, 17:41:20

[rzymek01]

@sztosz, wiadomo, że rekurencja jest wolniejsza i zżera więcej pamięci, bo musi pamiętać poprzednie wywołania funkcji

dobra, to teraz c++ (kompilator gcc 3.4.2, windows x86)

żeby zrobić z tego c, wystarczy:
rezerwowac pamięć funkcją calloc,
ctime na time.h
uzywać zamiast iostream, scanf i printf

[CPP] pobierz, plaintext 
/* wykorzystane założenia:
- rozważamy liczby tylko nieparzyste
- przy eliminacji wielokrotości liczby p, eliminujemy tylko liczby nieparzyste,
	więc postaci: p^2, p(p+2), p(p+4), ...
	i jeszcze dlatego, że liczby k*p zostały przesiane wcześniej
 
- wykorzystałem wskazówki i pseukod z książki "Algorytmy", bo komu się chce na nowo koło odkrywać (IMG:style_emoticons/default/tongue.gif) 
 
*/
 
// tutaj mozna dać stałą chudego windowsa ;)
#include <windows.h>
#include <ctime>
#include <iostream>
#include <vector>
 
using namespace std;
 
// Sito - bez wyświetlania danych
//       w celu wyświetlania danych nalezy odkomentować linijki na końcu funkcji
void Sito(int N) {
/* Sito
 * Wejście: parzysta liczba naturalna N
 * Wyjście: tablica liczb pierwszych z zakresu liczb naturalnych <2, N+1>
*/
 
    // inicjalizacja zmiennych
    int M = N / 2;
    bool* aSito = new bool[M + 1];
    for (int i = 1; i < M + 1; aSito[i++] = true);
 
	int i = 1,
        p = 3,
        q = 4,
        j;
 
/*
kod identyczny jak w moim poście wyżej z tym, że usuwamy wszystkie $
*/
 
	vector<int> aPierwsze;
        aPierwsze.push_back(2);
	for (i = 1; i <= M; ++i) {
            if (!aSito[i])
                continue;
 
            aPierwsze.push_back(2*i + 1);
	}
 
    // wyświetlenie wyników
//    vector<int>::iterator it = aPierwsze.begin();
//
//     for ( ; it < aPierwsze.end(); ++it )
//         cout << *it << "\n";
//     cout << endl;
}
 
int main() {
    int n,
        iPomiarow;
    cout << "Podaj liczbe: ";
    cin >> n;
    cout << "\nPodaj liczbe pomiarow: ";
    cin >> iPomiarow;
    cout << endl;
 
    LARGE_INTEGER start, stop, freq;
    unsigned __int64 istart, istop, ifreq;
    // ilość taktów cpu na sek
    QueryPerformanceFrequency(&freq);
    ifreq = freq.QuadPart;
 
    // kalibrujemy czas operacji pomiaru czasu
    QueryPerformanceCounter(&start);
    QueryPerformanceCounter(&stop);
    unsigned __int64 kalibracja = start.QuadPart - stop.QuadPart;
 
    // wykonujemy pomiar czasu
    QueryPerformanceCounter(&start);
 
    // mierzymy
    for(int i = 0; i < iPomiarow; ++i) {
        Sito(n);
    }
 
    // kończymy
    QueryPerformanceCounter(&stop);
 
    istart = start.QuadPart;
    istop  = stop.QuadPart;
    float t = (istop - istart - kalibracja) / (float)(ifreq * iPomiarow); // czas w sekundach
 
    cout << t;
 
    getchar(); // żeby nie zamknęła się konsola (IMG:style_emoticons/default/biggrin.gif) 
 
    return 0;    
}
[CPP] pobierz, plaintext 

najtrudniej było z dobrym liczeniem czasu, ale się udało.. uff (IMG:style_emoticons/default/smile.gif)

Kod

N = 100 000, czas: 0.000765121, pomiarów 10 000
N = 1 000 000, czas: 0,00850865s., pomiarów: 1000
N = 10 000 000, czas: 0,256164s, pomiarów 100
N = 100 000 000, czas: 3,43068s, pomiarów 10
N = 1 000 000 000, czas: 42.1552s, pomiarów 10

ale co by się nie oszukiwać, jesli gdzieś potrzeba liczby pierwsze to stosuje się preprocessing (IMG:style_emoticons/default/tongue.gif)
na jedne konkurs informatyczny trzeba było podać n-tą liczbę pierwszą z ograniczeniem do 100 000, to w necie znalazłem te liczby, wpadkowałem w tablicę i czas programu O(1) (IMG:style_emoticons/default/tongue.gif)

Ten post edytował rzymek01 31.08.2009, 19:23:07

[thek]

OK... czas na mnie (IMG:style_emoticons/default/winksmiley.jpg)

Kod

#include <cstdlib>
#include <iostream>
#include <ctime>
#include <cmath>
#include <windows.h>

using namespace std;

void test(int zakres) {
    bool dane[zakres+1];
    int limit = (int)(sqrt(zakres));
    int limit2 = zakres+1;
    memset(dane, true, (zakres+1)*sizeof(bool) );
    memset(dane, false, 2*sizeof(bool) );
    for(register int i=2; i <= limit; i++) {
        if( dane[i] == false ) {
           continue;
        }
        for(register int j = 2*i; j <= zakres; j += i) {
            dane[j] = false;
        }
    }
}

void test2(int zakres) {
    int _zakres = (int)(zakres+1)/2;
    bool dane[_zakres];
    int limit = (int)sqrt(_zakres);
    memset(dane, true, (_zakres)*sizeof(bool) );
    memset(dane, false, sizeof(bool) );
    for(register int i=1; i < limit; i++) {
        for(register int j=3*i+1; j<_zakres; j += 2*i+1) {
            dane[j] = false;
        }
    }
}

int main(int argc, char *argv[]) {
    int prob, zakres;
    cout << "Szukaj liczb pierwszych od 2 do: ";
    cin >> zakres;
    cout << " i powtorz razy: ";
    cin >> prob;
    cout << "\n";
    clock_t start = clock();
    for(register int r=0; r<prob; r++)
        test(zakres);
    cout << (double)(clock()-start)/CLOCKS_PER_SEC << " sekund dla test ze srednia:" << ((double)(clock()-start)/CLOCKS_PER_SEC)/prob << "\n";
    system("pause");
    clock_t start2 = clock();
    for(register int r=0; r<prob; r++)
        test2(zakres);
    cout << (double)(clock()-start2)/CLOCKS_PER_SEC << " sekund dla test 2 ze srednia:" << ((double)(clock()-start2)/CLOCKS_PER_SEC)/prob << "\n";
    system("pause");
    return 0;
}

Nie bawiłem się w wyświetlanie... Funkcje mają liczyć ;P Są pamięciożerne, ale na moim kompie proces Core 2 Duo T5500 (laptop) miały niezłe czasy (IMG:style_emoticons/default/smile.gif) Pierwsza (test) to klasyczna implementacją sitka. Drugi (test2) to malutka wariacja, gdzie lecę tylko i wyłącznie po liczbach nieparzystych. Wykonuje się wolniej, gdyż ma więcej operacji mnożenia po drodze w porównaniu do test, ale też może większy zakres objąć. C++ ma ograniczenie ilości pamięci dostępnej i z tego co mi system do niego przydzielił, pierwszy przeszukał w tym limicie jakieś 2.080.000 liczb, zaś drugi mniej więcej 2 razy tyle. Na pewno drugi liczy do 4.165.000 zanim się wysypie na braku pamięci (IMG:style_emoticons/default/winksmiley.jpg)
Dziwne jest jednak, że i tak w porównaniu do innych algorytmów liczy Ci o kilka rzędów wielkości lepiej. Albo masz sumer mega wypaśną maszynę, albo coś jest nie tak (IMG:style_emoticons/default/smile.gif)
Ja swój kod sprawdziłem na procku Core 2 Duo Centrino Duo T5500 (2 rdzenie po 1.83GHz) i pokazało mi w wyniku:

Szukaj liczb pierwszych od 2 do: 1000000
i powtórz razy: 1000
11.937 sekund dla test ze srednia:0.011937
14.125 sekund dla test 2 ze srednia:0.014125

i po prostu zastanawiam się jakim cudem mogłeś 0.00850865 wykręcić, czyli niemal 2 razy lepszy. Jakby co to weź mój kod i przetestuj na swojej i podaj wyniki bym miał jakieś porównanie.

EDIT: Przetestowałem na swoim także Twój kod i pokazał on dla tych samych danych:
7.297 sekundy ze średnią 0.007297 na przebieg, więc chyba w moim będę musiał nieco się wziąć za ograniczenie mnożeń. Zwłaszcza że potem zmieniłem z memset na for jakie Ty masz i tylko mi się wyniki obliczeń pogorszyły. Zwłaszcza dla test, który musi używać 2 razy większej tablicy (IMG:style_emoticons/default/winksmiley.jpg) Po daniu wszystkim równych szans z memsetem Twój zszedł nawet do 0.0049, ale zauważyłem, ze mój komp dziwnie chodził i była zastanawiająca różnica na niekorzyść algorytmu 2... test 0.011, a test2 0.015... Więc chyba jeszcze trzeba pooptymalizować (IMG:style_emoticons/default/winksmiley.jpg)

EDIT2: Trochę optymalizacji i test2 spadł do 0.0075, przy Twoim 0.0049 (IMG:style_emoticons/default/smile.gif)

EDIT3: Trochę więcej optymalizacji... Średni czas zszedł do 0.0050 i różnice sa już na poziomie raczej spowolnienia samych pętli (IMG:style_emoticons/default/winksmiley.jpg)

Kod

void test2(int zakres) {
    register int _zakres = (int)zakres/2;
    bool dane[_zakres];
    register int limit = (int)sqrt(_zakres), i=1, j, p=1, q;
    memset(dane, true, (_zakres)*sizeof(bool) );
    memset(dane, false, sizeof(bool) );
    for(;i < limit; i++) {
        p += 2;
        q = p+i;
        if(dane[i]) {
            for(j=q; j<_zakres; j += p) {
                dane[j] = false;
            }
        }
    }
}

Ten post edytował thek 1.09.2009, 04:01:55

[rzymek01]

no tak, memset jest znacznie szybszy (IMG:style_emoticons/default/smile.gif)

jak ci się chce to zrezygnuj z memseta i daj calloc, tylko nie wiem czy z bool zadziała, ale na 99% powinien
wtedy wykręcisz jeszcze lepsze czasy (IMG:style_emoticons/default/tongue.gif)

PS. nie rób czegoś takiego:

Kod

bool dane[zakres+1];

bo ci się stos przepełni
twórz tablicę poprzez new lub szybsze funkcje z c: malloc i calloc (<- ta od razu zeruje)


Pozdrawiam

[thek]

Można robić przez new... Tylko że przy wywoływaniu tego co chwilę w pętli miałbym problem (IMG:style_emoticons/default/winksmiley.jpg) Jak mam skasować wartość ewentualną skoro jednocześnie jest ona daną zwracaną przez return? Mam liczyć na to, że system sam potem skasuje miejsce przydzielone operatorem new? Skoro jest new, to musi być także delete. W tym wypadku mogę sobie pozwolić na ewentualne jego użycie.... ale gdybym miał zwrócić wynik to byłaby kaplica bo muiałbym wywołać delete PO return. A taka możliwość nie istnieje. Musiałbym kod przerobić na klasę, która miałaby zdefiniowany konstruktor i destruktor. Bo w sposób jaki opisujesz to ciągle deklaruję zajęcie pamięci przez new, ale nigdzie jej nie zwalniam delete. A to dyskwalifikuje w moim odczuciu kod jako powodujący przecieki pamięci. Chyba więc rozumiesz już czemu zadeklarowałem tablicę statycznie, nie zaś dynamicznie. Nie mam zamiaru oglądać co chwilkę "segmentation fault" (IMG:style_emoticons/default/winksmiley.jpg)

Ten post edytował thek 1.09.2009, 22:18:35

[l0ud]

ale gdybym miał zwrócić wynik to byłaby kaplica bo muiałbym wywołać delete PO return. A taka możliwość nie istnieje

Niby dlaczego? (IMG:style_emoticons/default/tongue.gif) To właśnie użycie stosu w tym wypadku utrudnia (uniemożliwia?) przekazanie wyniku (tablicy) poza funkcję. A tak można w ładny sposób zwrócić wskaźnik do tablicy elementów bool, gdzie ilość tych elementów będzie równa zakres/zakres+1 (IMG:style_emoticons/default/tongue.gif) A później sobie ją zwyczajnie zwolnić.

Ten post edytował l0ud 1.09.2009, 20:40:01

[rzymek01]

1. program po zakończeniu swojej pracy zwalnia przydzieloną mu pamięć, a więc jeśli to jest tylko program który wykonuje algorytm, a potem wyświetla wyniki i się zamyka - nie ma żadnych wycieków pamięci (IMG:style_emoticons/default/smile.gif)
2. możesz wyświetlać wyniki na bieżąco na wyjście/do pliku i przed returnem zwolnisz pamięć
3. możesz użyć tzw. inteligentnych wskaźników
4. preferuję: jeśli funkcja ma zwracać tablicę wyników, można zrobić tak:

Kod

bool *wyniki;
WykonajFunkcje(wyniki, arg...); // w środku funkcji przydzielana jest pamięć
//wyświetlasz wyniki odczytując tablicę `wyniki`
delete wyniki; // zwalniasz pamięć

(IMG:style_emoticons/default/smile.gif)

[l0ud]

rzymek01, jak już to delete[] wyniki; (IMG:style_emoticons/default/winksmiley.jpg) A to, że system zwalnia całą pamięć po programie mimo wszystko nie powinno usprawiedliwiać do pozostawiania wycieków.

[thek]

@loud: gdyby rezerwacja i kasowanie pamięci były wewnątrz funkcji to nie miałbym obiekcji. Jednak ta funkcja jest wykonywana dajmy na to z 100.000 razy i za każdym razem nie zwracam przydzielonej pamięci. System powinien przy zakończeniu zwolnić całą pamięć programu, ale jako programista "starej szkoły" nie pozwalam na to. Nie idę jednak w przesadę (typy predefiniowane też można przecież potraktować delete ). Tyle że napisany raz kod z reguły jest gdzieś dostępny w nece późnej (choćby cache google). Na linuxie zrobienie tego manewru z brakiem delete zakończyłoby się błędem ochrony pamięci. To nie windows, gdzie można robić bardzo wiele. Jeśli już więc piszę w C++ to tak, by każdy mógł sprawdzić poprawność. To tak samo jak w php problemy między wersjami 4 i 5.Jeden od pójdzie w jednej z wersji, ale w innej już nie. Jeśli już więc piszemy, to piszmy według standardów i nie róbmy tego niechlujnie. Stąd właśnie zaproponowałem, że lepiej przerobić to na klasę i zdefiniować konstruktor i destruktor. Tyle że temat ma służyć "do wykręcania" wyników (IMG:style_emoticons/default/winksmiley.jpg) A klasa niestety jest nieco mniej optymalnym rozwiązaniem. Wiem jaka jest różnica między bool nazwa[size]a bool* nazwa i jestem świadom ograniczeń. Wolałem jednak by kod się wysypywał przy zbyt dużej liczbie elementów niż wysypywał i gubił pamięć (IMG:style_emoticons/default/winksmiley.jpg)
Widzę, że podzielasz moje podejście do nie szastania dostępną pamięcią. Wiem... Powinenem jeszcze dane wejściowe kontrolować, ale akurat w kodzie tego typu nie można namieszać poza wrzuceniem do int wartości innego typu.

[rzymek01]

rzymek01, jak już to delete[] wyniki; (IMG:style_emoticons/default/winksmiley.jpg) A to, że system zwalnia całą pamięć po programie mimo wszystko nie powinno usprawiedliwiać do pozostawiania wycieków.

dlatego pogrubiłem opcję 4, która wg mnie jest najlepszym rozwiązaniem w tej sytuacji

PS. co do mojego kodu, faktycznie powinien byc delete, z rozpędu zapomniałem go dodać

Ten post edytował rzymek01 2.09.2009, 14:57:44

[Jabol]

Co do tematu to niestety masz ten problem, że większość książek nie opisuje algorytmów tylko języki programowania. A nowoczesne książki o algorytmice są do bani - pokazują kilka przykładów i nawet dobrze to nie jest omówione.

Pewnie ameryki nie odkryje jak napiszę "Sztuka programowania" Knutha - stara i sprawdzona klasyka. I że książka ma 40 lat nie oznacza, że nie można się z niej wiele nauczyć. Oczywiście o algorytmach rozproszonych czy chociażby wieloprocesorowych raczej tam nie poczytasz ale też nie o to chodzi. Wyporzycz sobie najpierw na próbe w bibliotece - bo to ciężki tom - na pewno kupe kasy kosztuje. No i oczywiście zależnie od tego co Cie interesuje musisz poszukać książki do odpowiedniego tematu (algorytmy graficzne, algorytmy na grafach, kryptografia itp...).