Python rechnet uneffizient?

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
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]
Benutzeravatar
pyHoax
User
Beiträge: 84
Registriert: Donnerstag 15. Dezember 2016, 19:17

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))
Zuletzt geändert von Anonymous am Freitag 16. Dezember 2016, 08:26, insgesamt 1-mal geändert.
Grund: Quelltext in Python-Codebox-Tags gesetzt.
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
Benutzeravatar
pyHoax
User
Beiträge: 84
Registriert: Donnerstag 15. Dezember 2016, 19:17

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
User
Beiträge: 17711
Registriert: Sonntag 21. Oktober 2012, 17:20

@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
Benutzeravatar
pyHoax
User
Beiträge: 84
Registriert: Donnerstag 15. Dezember 2016, 19:17

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
Benutzeravatar
pyHoax
User
Beiträge: 84
Registriert: Donnerstag 15. Dezember 2016, 19:17

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.
Antworten