bo zwyczajnie nie lubię tego języka, ale zupełnie nie w tym rzecz. )i nie wwalam wszystkich wielokrotności liczb pierwszych z możliwych kandydatów, ergo robi się brute force zamiast algorytmu. 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?
Ale tym razem słuszna
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: 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
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ś Po prostu kasuje hurtem bez sprawdzania zawartości. Dlatego jest taki szybki 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 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.
(i znów się przekonałem jaką PHP ma nieczytelną składnie )
)
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 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.
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 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.
Patrzyłem na niego jako: 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.
Ps. Przy tych wartościach u mnie cały proces pythona zajmuje 3.5 MB z tablica i resztą. I dlatego potrzebuje czegoś o algorytmach, żeby nauczyć się odpowiednio myśleć
mój: 0.540700006485 rekurencja: 7.29569997787
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 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ć 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"
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 A później sobie ją zwyczajnie zwolnić.
A to, że system zwalnia całą pamięć po programie mimo wszystko nie powinno usprawiedliwiać do pozostawiania wycieków.
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ęć A to, że system zwalnia całą pamięć po programie mimo wszystko nie powinno usprawiedliwiać do pozostawiania wycieków.