Python rechnet uneffizient?

[BlackJack]

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]

[pyHoax]

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)

Code: Alles auswählen

timeit
referenz:  18.7140735757
vanilla:   4.04164260142
itertools: 2.06300881091

Der Code:

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))

[BlackJack]

@pyHoax: Das mit dem `__builtin__` funktioniert so nicht, weil es das Modul in Python 3 nicht gibt:

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__'

Man könnte das ganz ohne Importe einfach so lösen:

Code: Alles auswählen

try:
    range = xrange
except NameError:
    pass

[pyHoax]

Man könnte das ganz ohne Importe einfach so lösen:

Danke.Das funktioniert aber nur, wenn ich es im Module und nicht im Methoden Kontext verwende.

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

Interessant das python offensichtlich bereits beim Parsen der Methode Variablen deklariert, auch wenn sie nicht initilaisiert werden. Anders kann ich mir das so nicht erklären.

Ähnlich sieht es mit diesem Codeschnipsel aus:

Code: Alles auswählen

    if version_info.major < 3:
        range = __builtin__.xrange

[Sirius3]

@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:

Code: Alles auswählen

    try:
        yrange = xrange
    except NameError:
        yrange = range

oder macht auf Modulebene einen Future-Port:

Code: Alles auswählen

    try:
        xrange
    except NameError:
        xrange = range

[pyHoax]

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:

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

Python 2.7.9 (default, Jun 29 2016, 13:08:31)
[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

Python 3.4.2 (default, Oct 8 2014, 10:45:20)
[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

[pyHoax]

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