Da der nicht wirklich gute Algorithmus mit OpenMP an die offensichtliche Python-Lösung herankommt, habe ich überlegt wie man die mit möglichst wenig Aufwand schneller bekommt. Dazu habe ich sie unverändert mit PyPy statt mit CPython laufen lassen. Ergebnis: Doppelt so schnell wie die OpenMP-Variante.
[codebox=text file=Unbenannt.txt]Laufzeit (< besser):
DerTürke-Algo *********************************************************
Python-Sieve ******************************
DerTürke-Algo+OpenMP ******************************
Python-Sieve[PyPy] ***************
C-Sieve *[/code]
Python rechnet uneffizient?
Guten Tag zusammen,
Ich wollte euch mal zwei meiner optimierten Implementation des Primzahlenfilters vorstellen.
Die vanilla Variante verwendet nur buildins die Zweite einen import aus dem Itertools Module.
Als nächstes werde ich schauen wie das Problem partitioniert werden kann, für größere Primzahlen reicht der Speicher einfach nicht.
Finde Primzahlen bis: 10000000 , gemessen jeweils 10 Runden mit timeit. (Python2.7)
Der Code:
Ich wollte euch mal zwei meiner optimierten Implementation des Primzahlenfilters vorstellen.
Die vanilla Variante verwendet nur buildins die Zweite einen import aus dem Itertools Module.
Als nächstes werde ich schauen wie das Problem partitioniert werden kann, für größere Primzahlen reicht der Speicher einfach nicht.
Finde Primzahlen bis: 10000000 , gemessen jeweils 10 Runden mit timeit. (Python2.7)
Code: Alles auswählen
timeit
referenz: 18.7140735757
vanilla: 4.04164260142
itertools: 2.06300881091
Code: Alles auswählen
import __builtin__
from sys import version_info
from itertools import compress
def prim_referenz(n):
if n < 3:
return [2] if n == 2 else []
s = list(range(3, n + 1, 2)) if version_info.major > 2 else range(3, n + 1, 2)
# n**0.5 simpler than math.sqr(n)
mroot = n ** 0.5
half = len(s)
i = 0
m = 3
while m <= mroot:
if s[i]:
j = (m * m - 3) // 2 # int div
s[j] = 0
while j < half:
s[j] = 0
j += m
i = i + 1
m = 2 * i + 3
return [2] + [x for x in s if x]
def prim_vanilla(n):
if n < 3:
return [2] if n == 2 else []
range = __builtin__.range if version_info.major > 2 else __builtin__.xrange
size = len(range(3, n + 1, 2))
sieb = bytearray([True]) * size
max = int(n ** 0.5) + 1
for prim in ( 2 * i + 3 for i in range(0, max) if sieb[i] ):
start = (prim ** 2 - 3) // 2
sieb[start::prim] = bytearray([False]) * len(range(start, size, prim))
primes= [2]
primes.extend(3 + 2 * i for i,p in enumerate(sieb) if p)
return primes
def prim_itertools(n):
if n < 2:
return [2] if n == 2 else []
range = __builtin__.range if version_info.major > 2 else __builtin__.xrange
size = len(range(3, n + 1, 2))
sieb = bytearray([True]) * size
max = int(n ** 0.5) + 1
for prim in compress(range(3, max , 2), sieb):
start = (prim ** 2 - 3) // 2
sieb[start::prim] = bytearray([False]) * len(range(start, size, prim))
prime_numbers = [2]
prime_numbers.extend(compress(range(3, n + 1, 2), sieb))
return prime_numbers
if __name__ == '__main__':
import timeit
print("timeit")
print("referenz: %s" % timeit.timeit("prim_referenz(10000000)", setup="from __main__ import prim_referenz", number=10))
print("vanilla: %s" % timeit.timeit("prim_vanilla(10000000)", setup="from __main__ import prim_vanilla", number=10))
print("itertools: %s" % timeit.timeit("prim_itertools(10000000)", setup="from __main__ import prim_itertools", number=10))
Zuletzt geändert von Anonymous am Freitag 16. Dezember 2016, 08:26, insgesamt 1-mal geändert.
Grund: Quelltext in Python-Codebox-Tags gesetzt.
Grund: Quelltext in Python-Codebox-Tags gesetzt.
@pyHoax: Das mit dem `__builtin__` funktioniert so nicht, weil es das Modul in Python 3 nicht gibt:
Man könnte das ganz ohne Importe einfach so lösen:
Code: Alles auswählen
Python 3.3.6 (default, Dec 19 2014, 22:05:50)
[GCC 4.6.3] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import __builtin__
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ImportError: No module named '__builtin__'
Code: Alles auswählen
try:
range = xrange
except NameError:
pass
Danke.Das funktioniert aber nur, wenn ich es im Module und nicht im Methoden Kontext verwende.Man könnte das ganz ohne Importe einfach so lösen:
Kann ich mit leben. Dafür sieht es sexy aus.
Im Methodenbody aufgerufen bekomme ich unter python3 dann folgenden Fehler:
Code: Alles auswählen
UnboundLocalError: local variable 'range' referenced before assignment
Ähnlich sieht es mit diesem Codeschnipsel aus:
Code: Alles auswählen
if version_info.major < 3:
range = __builtin__.xrange
@pyHoax: alle Variablen, die irgendwo in einer Funktion definiert werden, sind lokal, egal ob sie zum Zeitpunkt des Zugriffs schon definiert wurden oder nicht. Woher soll auch Python wissen, ob ein if-Zweig genommen wird oder nicht.
Am besten nimmt man einen neuen Namen:
oder macht auf Modulebene einen Future-Port:
Am besten nimmt man einen neuen Namen:
Code: Alles auswählen
try:
yrange = xrange
except NameError:
yrange = range
Code: Alles auswählen
try:
xrange
except NameError:
xrange = range
Aber wenn man mal sehen will wie sich python in der Performance weiterentwickelt hat.. hier nochmal die Benchmarks mit python2.7, python3 und pypy.
Die Itertools Variante hat unter pypy eine Regression, für pypy müsste wohl der Code nochmals eigens optimiert werden .. keine meiner Varianten toppt die Referenzimplementierung unter pypy.
Interessant.. kann jemand diese Messungen bestätigen ?
PS: Ich hab nochmal den Code für eine numpy Variante angehängt.
Gemmesen unter Debian 8.6 auf:
Python 2.7.9 (default, Jun 29 2016, 13:08:31)
[GCC 4.9.2] on linux2
Python 3.4.2 (default, Oct 8 2014, 10:45:20)
[GCC 4.9.1] on linux
Python 2.7.8 (2.4.0+dfsg-3, Dec 20 2014, 13:30:46)
[PyPy 2.4.0 with GCC 4.9.2] on linux2
Die Itertools Variante hat unter pypy eine Regression, für pypy müsste wohl der Code nochmals eigens optimiert werden .. keine meiner Varianten toppt die Referenzimplementierung unter pypy.
Interessant.. kann jemand diese Messungen bestätigen ?
PS: Ich hab nochmal den Code für eine numpy Variante angehängt.
Gemmesen unter Debian 8.6 auf:
Code: Alles auswählen
vendor_id : GenuineIntel
cpu family : 6
model : 15
model name : Intel(R) Core(TM)2 Quad CPU Q6600 @ 2.40GHz
stepping : 11
[GCC 4.9.2] on linux2
Code: Alles auswählen
timeit
timeit
timeit
referenz: 26.433770895
vanilla: 5.74793505669
itertools: 2.98172211647
numpy: 1.80512595177
[GCC 4.9.1] on linux
Code: Alles auswählen
timeit
timeit
referenz: 23.37278415900073
vanilla: 5.743356631006463
itertools: 2.427294566994533
numpy: 1.89215411299665
Python 2.7.8 (2.4.0+dfsg-3, Dec 20 2014, 13:30:46)
[PyPy 2.4.0 with GCC 4.9.2] on linux2
Code: Alles auswählen
timeit
referenz: 3.46602106094
vanilla: 3.57421088219
itertools: 10.3857440948
Die numpy Variante:
Code: Alles auswählen
import numpy
def prim_numpy(n):
""" Returns a array of primes, 3 <= p < n """
if n < 3:
return []
elif n == 2:
return [2]
numbers = numpy.ones(n/2, dtype=numpy.bool)
for i in ( i for i in range(3,int(n**0.5)+1,2) if numbers[i/2]):
numbers[i*i/2::i] = False
prime_numbers = [2]
prime_numbers.extend( 2 * numpy.nonzero(numbers)[0][1::] + 1 )
return prime_numbers
Zuletzt geändert von Anonymous am Freitag 16. Dezember 2016, 11:19, insgesamt 1-mal geändert.
Grund: Quelltext in Python-Codebox-Tags gesetzt.
Grund: Quelltext in Python-Codebox-Tags gesetzt.