Seite 1 von 1
Potenzierung
Verfasst: Sonntag 10. April 2011, 18:03
von 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
Re: Potenzierung
Verfasst: Sonntag 10. April 2011, 18:21
von /me
Peak_me hat geschrieben:
Fallen euch noch andere Varianten ein?
Bei Variante 3 ist es nicht nötig, das Dictionary jedes Mal neu aufzubauen.
Re: Potenzierung
Verfasst: Sonntag 10. April 2011, 18:27
von 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.
Re: Potenzierung
Verfasst: Sonntag 10. April 2011, 18:39
von 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?
Re: Potenzierung
Verfasst: Sonntag 10. April 2011, 18:48
von 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]
Re: Potenzierung
Verfasst: Sonntag 10. April 2011, 19:17
von 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
Re: Potenzierung
Verfasst: Sonntag 10. April 2011, 19:36
von 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)
Re: Potenzierung
Verfasst: Sonntag 10. April 2011, 19:47
von 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:
Re: Potenzierung
Verfasst: Sonntag 10. April 2011, 19:49
von /me
Peak_me hat geschrieben:
@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.