Eratoszthenész szitájánál milyen hatékonyabb prímkereső algortumus van ami megkeresi 1-től n-ig az összes prímet?
A próbaosztásoknál jóval gyorsabb futási idejű ez a szita algortimus, még akkor is ha csak a négyzetgyökig próbaosztunk.
Természetesen mint tudjuk mindig az adott szitálandó szám négyzetétől kell szitálni az összes többszörösére.
Hatékonyság növelése:
2-nél nagyobb szitaérték esetében valójában elegendő a négyzetét és az annál nagyobb onnan számított minden második többszörösével foglakozni és kiszórni, hiszen a többi az úgy is ki van szórva hiszen azok csak párosak lehetnek amik eleve ki lettek zárva a 2 többszörösei miatt. Továbbá elegendő a kezdő állapotnak 3-től kezdve az intervallum végéig minden páratlan számtól indulni. A kettő többszöröseit nem is kell kiszórni, eleve bele se raktam kezdetben sem. Nagyon kezdenek nem érdemes még ennél is jobban kizárni további számokat kezdeti állapotnak, csekély mértékben járul hozzá futási idő lefaragásához, sőt rossz esetben még növeli is a futási időt a további kezdeti "hókuszpókusz".
Természetesen ha a páratlanokkal indítuttunk kezdetben akkor utólag a 2-őt bele kell rakni mesterségesen, mert a 2 az páratlan a prímek között hiszen egyes egyedüli páros prím.
Dinamikusan növekvő változat:
Egy "legyártott" kiszitált prímlistát lehet dinamikusan folytatni, egy menetbe dinamikusan folytatva a négyzetéig lehet menni, az dinamikus folytatás új listájának első kiszitálandó listaelemének az indexe j = (p - start % p) % p minden előző p prímre, ahol start az új lista legkisebb eleme és a listában a 0-ik elem, %-al jelöltem a moduló operátort. Majd a következő szitálandó listaelem p-vel nagyobb indexű, pontosabban 2*p-vel ha már 2-vel ki vannak szitálva, azonban itt is lehet trükközni hogy kezdetben csak páratlan számokat tartalmaz az új lista, erre kitérek ha valakit értdekel.
A dinamikus bővítést felhasználva további gyorsístást lehet elérni a párhuzamosított feldolgozással számított szita módosítással, hogy több szálon párhuzamos feldolgozással az intervallumot felosztva annyi részre ahány cpu mag áll rendelkezésre és annyi szálon, de kezdetben egy szálon az 1-től n-ig intervallum négyzetgyökéig felső becsléssel, hiszen n négyzetgyöke (egész része vagy felfele kerekítve) nem biztos hogy prím. Felső becslés pl hogy másfélszeresét vesszük a négyzetgyökének, nem ezen múlik a sok szál overheadje hogy mennyire sikerül minél (felső) jobb becslést adni rá vagy egzaktul tudjuk gyors futási időbe.
válasza:Egy egyszerű szita
from datetime import time
from datetime import datetime
import math
kezd = datetime.now()
primes=[2]
max=1000000
def IsPrime(n):
prime=True
maximum=int(math.sqrt(n))+1
for i in primes:
if i>maximum : break
if n%i==0:
prime=False
break
return prime
for i in range(3,max,2):
if IsPrime(i): primes.append(i)
print('runtime: ',datetime.now()-kezd)
print(primes)
válasza:Hopp kivette a behúzásokat
Akkor a párhuzamost ki se teszem
Aki legalább érti a kérdést az válaszoljon!
Ez nem szita, hanem próbaosztásos prímlista generálás.
Ez a szita a gyengébbek kedvéért : [link]
Animált gif is szempélteti. Én még ennél is jobban kioptimalizáltam lásd a kérdés leírásába feljebb (már a nem párhuzamosított változatot is). 300 millióig a próbaosztásos módszert ki se várom mikor hajlandó lefutni -közbe jóllakok pihenek stb. az se elég-, a szitával úgy is másodpercekbe mérhető, a párhuzamosítás ereje a párhuzamosítás menteshez képesti szitára ott már érződik, persze nem csak ilyen nagy szitára érződik csak példának írtam. Kis szitára a párhuzamosításott változat a párhuzamosítás közben fellépő overhead miatt nem is feltétlen gyorsabb. A szálak össz ideje meg gyakorlatilag mindig több. (Pl. aktív 2 másodperc alatt 4 szálon 8 másodperc számítási összesített idő. Persze ha nincs se zár közbe meg van 4 cpu mag hozzá stb. Valójában egy sok összetevős rendszer a szálak, az ütemező, a többi processz stb.)
Azaz benchmark tesztekkel tetten érhető hogy a próbasztásos módszer sokkal sokkal lassabb mint az Eratoszthenész szitája.
Még továbbá a kérdés az volt hogy lehet még gyorsabb futási időt elérni mint maga az Eratoszthenész szitája, ha nem voltam egyértelmű a kérdés kiírásakkor akkor leírom hogy futási időben gyorsabbra vagyok kíváncsi mint ami ebből a szitából kihozható akár párhuzamosítással.
Még jobban pontosítva algoritmus futási idő elemzési szinjtén érdekel, hogy úgy gyorsabb futási idejű aszimptotikusan ordóba például. Elvégre ordóba egyforma javascripttel vagy assemblybe akár x konstans darab párhuzamosított szálon is.
válasza:Érdekes ez a szita elmélet. Módosított szitában mely előszitáló én is gondolkodtam nagyon nagy nagy prímszámok keresése eseténben régebben, bár ott nem volt cél 1-től N-ig az ÖSSZES prím keresése (nem is lehetne mert úgy több prímszám van annyi sok száz/ezer jegyű számokig mint a belátható univerzumban ahány elektron elférne compton hullámhosszal számolva), pont ez a 30030 = 2*3*5*7*11*13 előszita méretet használtam, bár ott nem volt akkora gyorsítása mint amire számítottam a Miller–Rabin prímtesztnél a domináns időt a valóban prímek vitték el, ez esetben ahol 1-N-ig kell az összes prím azt írja 6x-os gyorsítás.
Próbaosztással legfeljebb négyzetgyökig próbálkozva az időkomplexitás felső becslés : O(n*gyök(n)) = O(n^(1.5)) . Nem beszélve a ciklusonkénti moduló műveletek, a sok négyzetgyökvonás művelet overhead-jeire mely sok c1,c2 stb konstans szorzó futási idő szempontjából gyakorlatilag.
Az Eratoszthenész szitájának időkomplexitása : O(n log log n) , vagyis több mint lineáris idejű, bár majdnem lineáris.
Találtam még szitát : Atkin szita ( [link] ) , az Eratoszthenész szitájának tovább gondolása. Érdekes hogy ennek időkomplexitása O(n) vagyis lineáris futási idejű, elvileg gyorsabb mint az Eratoszthenész féle szita.
Kijön az O(n) idő hogy egymásba égyazott 2 for ciklus melyek négyzetgyök n-ig mennek el vagyis O(gyök(n)*gyök(n)) = O(n) . Viszont temérdek overhead-ot ad hozzá ciklusonként az a sok szorzás összeadás moduló művelet, valamint párhuzamosítás is aggájos lévén hogy van egy boolean array melyben bizonyos feltételek mentén negáljuk ezen értékeket, ami már negálva lett az lehet még máskor is negálva. Bizonyos nagy n értéktől gyakorlatilag is gyorsabbnak kéne hogy legyen, hiszen az O(n) lassabban tart a végtelenhez mint a O(n log log n) függvény, még ha előbbi meg van jól patkolva bizonyos konstans szorzókkal. Valójában még a szorzás , moduló műveletek miatt is hozzá kellene jönnie szorzatként valamilyen logaritmikus időkomplexitásnak, hiszen ezeket minden ciklusban végrehajtja, de lévén hogy legrosszabb futási időt véve minden számot olyan hosszan ábrázoljuk mint az adott bementnél elvégzendő maximális eset akkor kijön hogy ordóba az is csak egy c konsans ami elhagyható aszimptotaikusan. Vagyis elég nagy n-re az Atkin szita fog győzni sebességre. Vagy még máshogy mondva ha győzzük memóriával akkor elég nagy n-re az Atkin szita gyorsabb javascipt-ben mint az Eratoszthenész szita assembly-ben.
További kérdések:
Minden jog fenntartva © 2025, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!