Witaj Gościu! ( Zaloguj | Rejestruj )

Forum PHP.pl

> Książka do Algorytmiki
sztosz
post
Post #1





Grupa: Zarejestrowani
Postów: 866
Pomógł: 32
Dołączył: 2.06.2004
Skąd: Wrocław

Ostrzeżenie: (0%)
-----


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)
Go to the top of the page
+Quote Post
 
Start new topic
Odpowiedzi
rzymek01
post
Post #2





Grupa: Zarejestrowani
Postów: 592
Pomógł: 62
Dołączył: 3.08.2006

Ostrzeżenie: (0%)
-----


  1. <?php
  2.  
  3. /* wykorzystane założenia:
  4. - rozważamy liczby tylko nieparzyste
  5. - przy eliminacji wielokrotości liczby p, eliminujemy tylko liczby nieparzyste,
  6. więc postaci: p^2, p(p+2), p(p+4), ...
  7. i jeszcze dlatego, że liczby k*p zostały przesiane wcześniej
  8.  
  9. - 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)
  10.  
  11. */
  12.  
  13. function getmicrotime() // z postu @wookieweb
  14. {
  15. list($usec, $sec) = explode(" ",microtime());
  16. return ((float)$usec + (float)$sec);
  17. }
  18.  
  19. function Sito($N) {
  20. /* Sito
  21.  * Wejście: parzysta liczba naturalna N
  22.  * Wyjście: tablica liczb pierwszych z zakresu liczb naturalnych <2, N+1>
  23. */
  24.  
  25. // inicjalizacja zmiennych
  26. $M = $N / 2;
  27. $aSito = array_fill(1, $M, true);
  28.  
  29. $i = 1;
  30. $p = 3;
  31. $q = 4;
  32.  
  33. while (true) {
  34. if ($aSito[$i]) {
  35. $j = $q;
  36.  
  37. while ($j <= $M) {
  38. $aSito[$j] = false;
  39. $j += $p;
  40. }
  41. }
  42.  
  43. ++$i;
  44. $p += 2;
  45. $q += 2*$p - 2;
  46.  
  47. if ($q > $M)
  48. break;
  49.  
  50. }
  51.  
  52. $aPierwsze = array();
  53. for ($i = 1; $i <= $M; ++$i) {
  54. if (!$aSito[$i])
  55. continue;
  56.  
  57. $aPierwsze[] = 2*$i + 1;
  58. }
  59.  
  60. return $aPierwsze;
  61. }
  62.  
  63. $start = getmicrotime();
  64. Sito(385000);
  65. $end = (getmicrotime()-$start).'<br/>';
  66.  
  67. echo $end;
  68.  
  69. ?>


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
Go to the top of the page
+Quote Post

Posty w temacie
- sztosz   Książka do Algorytmiki   29.08.2009, 09:33:15
- - wookieb   Zależy jakich algorytmów poszukujesz. W phpie nie ...   29.08.2009, 09:37:21
- - blooregard   @sztosz - jeśli byłbyś zainteresowany zakupem ksią...   29.08.2009, 09:43:04
- - sztosz   Od razu mówię że PHP to mnie akurat mało interesuj...   29.08.2009, 09:56:56
- - wookieb   Niestety ta książka akurat sit nie omawia. Na stro...   29.08.2009, 10:13:04
- - thek   Tak naprawdę to nie ma dobrej książki do algorytmi...   29.08.2009, 19:39:46
- - Shadowsword   Kup "Wprowadzenie do algorytmów" Wydawni...   29.08.2009, 20:04:07
- - sztosz   No ładnie książka wszędzie kosztuje około 140 zł, ...   29.08.2009, 21:00:28
- - Shadowsword   Naprawdę warto. Jest gruba, dokładnie opisuje napr...   29.08.2009, 21:26:38
- - l0ud   CytatPoza tym nie można temu algorytmowi nic zarzu...   29.08.2009, 22:17:06
- - wookieb   Cytat(l0ud @ 29.08.2009, 23:17:06 ) O...   29.08.2009, 22:34:16
- - sztosz   @Shadowsword: ściągnąłem kilka rozdziałów, przeczy...   29.08.2009, 22:37:05
- - wookieb   CytatUPDATE Wynik mi wyszedł taki: 11.087609052658...   29.08.2009, 22:44:01
- - sztosz   CytatU mnie dzieje się to tutaj [PHP] pobierz, pla...   29.08.2009, 22:55:38
- - wookieb   Jeszcze mała uwaga Loud Ale tym razem słuszna [P...   29.08.2009, 23:04:52
- - thek   Kod l0ud'a jest szybszy tylko z jednego powodu...   30.08.2009, 00:33:43
- - sztosz   Ale cała szybkość nie polega na tym że do danego i...   30.08.2009, 01:52:38
- - thek   A popatrz sobie na wyjaśnienie moje oraz chłopaków...   30.08.2009, 02:41:38
- - sztosz   OK, może ten algorytm jest lepszy przy "zrów...   30.08.2009, 10:30:38
- - rzymek01   również polecam "Wprowadzenie do algorytmów...   30.08.2009, 13:34:12
- - thek   Zrównolegnianie to proces przekształcania kodu z s...   30.08.2009, 14:43:15
- - sztosz   Parallel computing (Obliczenia równoległe), tak si...   30.08.2009, 20:08:16
- - l0ud   CytatAlgorytm pierwszy jest bardziej optymalny i l...   30.08.2009, 22:12:53
- - thek   Wczoraj źle zrozumiałem algorytm Patrzyłem na nie...   31.08.2009, 00:04:23
- - rzymek01   [PHP] pobierz, plaintext <?php /* wykorzys...   31.08.2009, 09:16:03
- - sztosz   W Pythonie [PYTHON] pobierz, plaintext from time ...   31.08.2009, 15:33:05
- - l0ud   Cytatadded: ktoś wie dlaczego tablica bool [400 00...   31.08.2009, 16:32:05
- - thek   Zabrzmiało to jakby C++ sam nie był językiem wysok...   31.08.2009, 16:52:35
- - sztosz   Nadal jest błąd: [32680]=> int(385001) to jest...   31.08.2009, 16:56:55
- - l0ud   CytatZabrzmiało to jakby C++ sam nie był językiem ...   31.08.2009, 17:13:12
- - sztosz   A przede mną naprawdę dużo nauki, prosta rekurencj...   31.08.2009, 17:22:30
- - rzymek01   @sztosz, wiadomo, że rekurencja jest wolniejsza i ...   31.08.2009, 19:18:07
- - thek   OK... czas na mnie Kod#include <cstdlib> ...   1.09.2009, 01:50:22
- - rzymek01   no tak, memset jest znacznie szybszy jak ci się ...   1.09.2009, 13:53:48
- - thek   Można robić przez new... Tylko że przy wywoływaniu...   1.09.2009, 20:07:24
- - l0ud   Cytatale gdybym miał zwrócić wynik to byłaby kapli...   1.09.2009, 20:39:12
- - rzymek01   1. program po zakończeniu swojej pracy zwalnia prz...   1.09.2009, 21:19:48
- - l0ud   rzymek01, jak już to delete[] wyniki; A to, że sy...   1.09.2009, 21:34:17
|- - rzymek01   Cytat(l0ud @ 1.09.2009, 22:34:17 ) rz...   2.09.2009, 14:55:32
- - thek   @loud: gdyby rezerwacja i kasowanie pamięci były w...   1.09.2009, 22:17:54
- - Jabol   Co do tematu to niestety masz ten problem, że więk...   4.09.2009, 10:43:47


Reply to this topicStart new topic
2 Użytkowników czyta ten temat (2 Gości i 0 Anonimowych użytkowników)
0 Zarejestrowanych:

 



RSS Aktualny czas: 15.10.2025 - 01:07