Potenzierung

[Peak_me]

hallo!

Ich möchte die schnellste Variante finden, um Potenzen zur Basis 10 zu berechnen. Der Exponent kann dabei zwischen 0 und 100 liegen.
5 verschiedene Varianten sind mir eingefallen:

Code: Alles auswählen

def potenz1(a):
    b=10**a
    return b

def potenz2(a):
    b=int('1'+a*'0')
    return b

def potenz3(a):
    d={	0 : 1,
	1 : 10,
	[...die restlichen Möglichkeiten...]
	99 : 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}
    b=d[a]
    return b

def potenz4(a):
    if a== 0 :
        b= 1
    if a== 1 :
        b= 10
	[...die restlichen Möglichkeiten...]
    if a== 99 :
        b= 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    return b

def potenz5(a):
    if a== 0 :
        b= 1
    elif a== 1 :
        b= 10
	[...die restlichen Möglichkeiten...]
    elif a== 99 :
        b= 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    return b

Dann rufe ich alle 4 Definitionen so auf:

Code: Alles auswählen

zufall=list(randint(0,99) for i in range(1000000))
for i in zufall:
    potenz1(i)

Es treten folgende Laufzeiten auf:
potenz1: 2.68 s
potenz2: 4.09 s
potenz3: 8.38 s
potenz4: 3.07 s
potenz5: 1.62 s

Am schnellstet ist also die elif-Fallunterscheidung, gefolgt von
direkter Potenzierung,
if-Fallunterscheidung,
String-Konstruktion,
Dictionary.

Fallen euch noch andere Varianten ein? Dann kann ich mal deren Laufzeit testen.
Gerade die Stringkonstruktion (potenz2) kann man sicher noch besser machen.


Gruß
Paul

[/me]

Fallen euch noch andere Varianten ein?

Bei Variante 3 ist es nicht nötig, das Dictionary jedes Mal neu aufzubauen.

[BlackJack]

@Peak_me: Mir fehlt da irgendwie die Liste mit vorberechneten Werten. Und auch da sollte man die Wertetabelle *ausserhalb* der Funktion nur *einmal* erstellen und nicht bei jedem Aufruf.

[Peak_me]

Bei Variante 3 ist es nicht nötig, das Dictionary jedes Mal neu aufzubauen.

Du hast natürlich Recht.
Ich habe den Aufbau des Dictionarys jetzt aus der Definition rausverlagert.
potenz3 liegt jetzt mit 0,35 s vorne.

@Peak_me: Mir fehlt da irgendwie die Liste mit vorberechneten Werten.

Das Dictionary in potenz3 enthält doch die vorberechneten Werte:

Code: Alles auswählen

    d={ 0 : 1,
        1 : 10,
        [...die restlichen Möglichkeiten...]
        99 : 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}

Und auch in den If- und Elif-Fallunterscheidungen sind doch die vorberechneten Werte vorhanden.
Oder was meinst du?

[DasIch]

Grob etwa sowas, dürfte recht schnell sein.

Code: Alles auswählen

_precomputed = [i ** 10 for i in xrange(100)]
def potenzn(i):
    return _precomputed[i]

[Peak_me]

Du hattest Basis und Exponent vertauscht, aber natürlich ist

Code: Alles auswählen

_precomputed = [10**i for i in xrange(100)]
def potenzn(i):
    return _precomputed[i]

am schnellsten. Keine Ahnung, wieso ich hier mit if- und elif- Rumgespielt habe
Natürlich ist ne einfache Liste das schnellste.

Ich habs jetzt mal auf 10.000.000 Zufallszahlen hochgeschraubt und jetzt siehts so aus:
2.9 s (DasIch, procomputed-Liste)
3,17 s (Dictionary)
16,89 s (elif)
25,67 (direkte Potenzierung)
29,27 (if)
40,01 (String-Zusammenfügung)

Natürlich ist das mit der Liste am schnellsten und irgendwie hätte mir das vor der Erstellung dieses Threads klar sein sollen.
Erkannt habe ich das aber nicht, weil ich den Listen- bzw. Dictionary-Aufbau in der Definition hatte.

danke also an alle,
Gruß
Paul

[welt-von-max]

Rekursion ist auch eine Möglichkeit ...
wenn auch nicht die schnellste in der Ausführung ^^

Code: Alles auswählen

#endrekursiv
#a muss 1 sein
def potenz_endrek(a,b):
    if(b== 0):
        return a
    else:
        return potenz_endrek(10*a,b-1)


#rekursiv 
def potenz_rek(a):
    if(a== 0):
        return 1
    else :
        return 10*potenz_rek(a-1)

[BlackJack]

@welt-von-max: Das dürfte sogar bei *weitem* die langsamste Lösung bisher sein.

@Peak_me: Du könntest noch einen Funktionsaufruf eliminieren:

Code: Alles auswählen

potenzn = [10**i for i in xrange(100)].__getitem__

[/me]

@Peak_me: Mir fehlt da irgendwie die Liste mit vorberechneten Werten.

Das Dictionary in potenz3 enthält doch die vorberechneten Werte:

Gemeint war wohl eine echte Liste (list) in der du einfach über den Index auf den passenden Wert zugreifst. Das müsste meiner Einschätzung nach noch einen Tacken schneller sein als der Dictionary-Zugriff.

Edit: OK, ich sehe gerade, dass sich dieses Thema schon erledigt hatte.