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]

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