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)

[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