Perfomance im Vergleich zu C++

[DaPeter]

Hallo,

ich war vorher eher im Bereich C++/Java unterwegs, muss und möchte nun für ein Praktikum aber auch mal Python lernen.
Dazu habe ich mir mal wieder die Fragen aus dem Project Euler rausgesucht, da ich damit in der Vergangenheit neue Sprachen sehr schnell lernen konnte.

Dass Python in der Geschwindigkeit nicht an manche andere Sprachen rankommt, hatte ich eh erwartet und das ist ja auch nicht schlimm, nur leider hab ich es so extrem nicht erwartet.

Nun konkret eine sehr einfache Aufgabe von Project Euler: "What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?"

Der Algo wurde in beiden Sprachen identisch umgesetzt. Er ist natürlich an sich nicht der schnellste, aber darum geht es nicht. Mit Python dauert er ganze 13.13 Sekunden, mit C++ (gcc) nur 0.12 Sekunden, mit eingeschalteter Optimierung kompiliert nur 0.08.

Puh, dachte ich mir, das ist ein gewaltiger Unterschied.
Meine Frage: Ist das nur ein sehr unglückliches Beispiel für Python oder ist das die Regel? Liefert Python noch Optimierungsmöglichkeiten? (ohne den Algo zu ändern, sonst ist es ja nicht mehr vergleichbar)

Hier noch die Codes:

Code: Alles auswählen

number = 20
while True:
    smallest = True
    for factor in range(11,21):
        if number%factor!=0:
            smallest = False 
            break
    if smallest:
        print(number)
        break
    number+=20

Code: Alles auswählen

#include <iostream>
using namespace std;

int main()
{
    bool smallest;
    unsigned int factor;
    unsigned int number = 20;
        
    while(true) 
    {
        smallest = true;
        for(factor=11;factor<21;++factor)
        {
            if(number%factor != 0)
            {
                smallest = false;
                break;
            }
        }
        if(smallest)
        {
            cout << number << "\n";
            break;
        }
        number+=20;
    }
 
    return 0;
}

[BlackJack]

@DaPeter: Das dürfte die Regel sein. Nur das das bei normalen Programmen nichts ausmacht. Oder musst Du solche Probleme *tatsächlich* für praktische Aufgaben lösen?

Python programmiert man nicht weil die Programme besonders schnell laufen, sondern weil man schnell grössere Programme schreiben kann, die schnell genug sind. Je nach Problem benutzt man auch Python-Bibliotheken die (teilweise) in C oder C++ geschrieben sind, oder Anbindungen an solche Bibliotheken aus dem jeweiligen Problemfeld. Rechnen mit grösseren Datenmengen in mehrdimensionalen Arrays geht zum Beispiel mit `numpy` recht flott. Oder man schreibt sich den Teil der zu langsam ist in Cython (Python-Untermenge die nach C und von da in eine DLL/shared library kompiliert wird) oder C und bindet den in das Python-Programm ein. Wichtig dabei: nur Teile die wirklich messbar zu langsam sind, damit man den Vorteil der Produktivität durch Python nicht verliert.

Das Programm sieht mir übrigens nach einer 1:1 Umsetzung aus. Also nicht wirklich nach Python.

[jbs]

Oder man probiert PyPy.

[BlackJack]

@jbs: Habe ich mal gemacht mit dem Code aus dem ersten Beitrag:

Code: Alles auswählen

12.711s         f1
 0.345s         f1 (psyco)
 0.322s         f1 (pypy)

Das erste ist die Zeit mit Python 2.6, das zweite die gleiche Funktion mit ``import psyco; psyco.full()`` und das letzte ist das Programm mit `pypy` ausgeführt. Ich habe den Code in eine Funktion gesteckt, weil lokale Namen schneller aufgelöst werden können und weil `psyco` keinen Code auf Modulebene beschleunigt.

Ach ja: `psyco` ist ein JIT-Compiler.

[Sr4l]

Puh, dachte ich mir, das ist ein gewaltiger Unterschied.
Meine Frage: Ist das nur ein sehr unglückliches Beispiel für Python oder ist das die Regel? Liefert Python noch Optimierungsmöglichkeiten? (ohne den Algo zu ändern, sonst ist es ja nicht mehr vergleichbar)

Ja und nein. Ja es ist ein unglückliches Beispiel, weil es nur auf Berechnungen setzt. Andererseit nein weil Python, zumindest CPython bei dieser Art von Arbeit schlecht abschneidet. Dafür gibt es aber viele Lösungen.

Code: Alles auswählen

$ time ./test
232792560

real    0m0.133s
user    0m0.108s
sys     0m0.015s

$ time pypy test.py
232792560

real    0m0.484s
user    0m0.046s
sys     0m0.000s

$ time python test.py
232792560

real    0m9.064s
user    0m0.031s
sys     0m0.047s

[jbs]

Nutzt man die PyPy-toolchain so reduziert sich die Zeit bei mir auf 0.073 Sekunden.

[BlackJack]

Was man auch machen kann ist ein wenig über das Problem nachdenken. Ich habe für das Problem eine BASIC-Lösung für den C64 die 5 Sekunden braucht. Auf einem Rechner mit einem knapp unter 1 MHz 8-Bit-Prozessor und einem scheusslich langsamen, interpretierten BASIC.

[DaPeter]

Vielen Dank für die Antworten. Das reicht mir wohl erstmal, da hab ich genug zu lesen.

@BlackJack:
Ja, in der Arbeitsstelle werden eher algorithmische Fragestellungen mit Python betrachtet. Wie genau das abläuft, weiß ich nocht nicht, aber ich denke mal nicht, dass sie nur "reines" Python verwenden und die schlechtere Laufzeit in Kauf nehmen, die werden sich schon auskennen hoffentlich.
Und mein Code sieht sehr nach 1:1 aus, ja. Ich bin erst seit einem Tag an Python dran und denke daher noch in anderen Sprachen, aber das wird noch

Und natürlich kann man das Problem einfach auf eine andere Art schneller lösen, aber das schrieb ich ja bereits im ersten Post.

[darktrym]

Bei mir ist der Code 1/3 schneller wenn ich den range-Kram außerhalb der Schleife definiere.

[jerch]

Mit einem anderen Ansatz (modifiziertes Sieb, welches sich frühere Faktorisierungen merkt) schmilzt der Unterschied dahin (<5x) und CPython schaffts in:

Code: Alles auswählen

$> time python prim_sieve_factors.py
232792560

real    0m0.028s
user    0m0.017s
sys     0m0.010s

Deine Brute-Force-Variante ist ein ungünstiges Bsp., da Pythons Schleifen weit hinter denen in C/C++ liegen.

[snafu]

@jerch: Kannst den Code zu deinem Ansatz gerne mal posten. Würde mich interessieren.

[jerch]

So siehts in Python aus:

Code: Alles auswählen

def factorize_sequence(num):
    factored_sieve = [False] * num
    prims = {}
    for i in xrange(2, num):
        if not factored_sieve[i]:
            factored_sieve[i] = (i,)
            counts = 1
            for j in xrange(2, num):
                if i*j >= num:
                    break
                if factored_sieve[j]:
                    factored_sieve[i*j] = (i,) + factored_sieve[j]
                    count_i = factored_sieve[i*j].count(i)
                    if count_i > counts:
                       counts = count_i
            prims[i] = counts
    return factored_sieve[2:], prims

def total_product(factors):
    result = 1
    for prim, count in factors.iteritems():
        result *= prim ** count
    return result

sieve, factors = factorize_sequence(21)
#print sieve, factors
print total_product(factors)

Kann man sicher noch weiter optimieren, hatte allerdings keine Lust, da lange dranrum zu überlegen.

[jbs]

Meine Lösung wäre die hier:

Code: Alles auswählen

def ggt(a,b):
    while a:
            a, b = b%a, a
    return b

def kgv(x,y):
    return x*y/ggt(x,y)

print reduce(kgv, range(11, 21))