06 Dec 2019

Python vs Numpy

Zur Berechnung von Fakultät, Fibonacci, Ackermann: Ein Herausforderer erscheint! Python steigt in den Ring.

Zu diesem Beitrag Haskell versus C reiche ich jetzt noch eine Version in Python und Python mit Numpy und weiteren Tricks nach.

Die Kandidaten

A.py

#!/usr/bin/python3.6

import resource, sys
resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
sys.setrecursionlimit(10**6)
 
# Fibonacci function
def Fibonacci(n): 
    elif n<=1: 
        return n
    else: 
        return Fibonacci(n-1)+Fibonacci(n-2) 
  
# Faculty function
def Faculty(n):
    factorial = 1
    if n < 0:
        return -1
    elif n == 0:
        return 1
    else:
        for i in range(1, n + 1):
            factorial = factorial*i
        return factorial

# Ackermann function
def Ackermann(m,n):
     if m == 0:
          return (n + 1)
     elif n == 0:
          return Ackermann(m - 1, 1)
     else:
          return Ackermann(m - 1, Ackermann(m, n - 1))

print("Faculty  : ", Faculty(20))
print("Fibonacci: ", Fibonacci(34))
print("Ackermann: ", Ackermann(3, 10))

A-sci.py

#!/usr/bin/python3.6
import scipy, numpy, math
from functools import lru_cache

# extend resources for ackerman (sic!)
import resource, sys
resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
sys.setrecursionlimit(10**6)

# recursive fibonacci function
def Fibonacci(n): 
    Matrix = numpy.matrix([[0,1],[1,1]])
    vec = numpy.array([[0],[1]])
    fib = numpy.matmul(Matrix**n,vec)
    return fib[0][0]
  
# faculty function
def Faculty(n):
    factorial = math.factorial(n)
    return factorial

# ackermann function
@lru_cache(None)
def Ackermann(m,n):
     if m == 0:
          return (n + 1)
     elif n == 0:
          return Ackermann(m - 1, 1)
     else:
          return Ackermann(m - 1, Ackermann(m, n - 1))

print("Faculty  : ", Faculty(20))
print("Fibonacci: ", Fibonacci(34))
print("Ackermann: ", Ackermann(3, 10))

Alle Listings mit makefile kann man hier herunterladen: python-vs-numpy.tar.gz

Vorbereitungen

  • Wenn bei Python dieser Fehler auftritt
RecursionError: maximum recursion depth exceeded in comparison

Muss man die Verfügbaren Ressourcen extenden, mit sys.setrecursionlimit wie in den Listings getan.

  • Für Numpy / Scipy muss man die entsprechenden Bibliotheken installieren, unter Gentoo geht das so
#  emerge dev-python/numpy sci-libs/scipy

Und los gehts!

  • native Python-Version
$ time ./A.py 
Faculty  :  2432902008176640000
Fibonacci:  5702887
Ackermann:  8189

real	0m18.292s
user	0m15.173s
sys	0m3.119s

Das bislang enttäuschendste Ergebnis, besonders Ackermann setzt Python stark zu und führt nahezu zum Torkeln im Ring!

  • Version mit Numpy und weiteren Tricks
time ./A-sci.py 
Faculty  :  2432902008176640000
Fibonacci:  [[5702887]]
Ackermann:  8189

real	0m0.161s
user	0m0.146s
sys	0m0.014s

Ein gutes Ergebnis. Numpy / Scipy verwenden aber im Hintergrund mathematische Bibliotheken, die in Fortran77 geschrieben sind. Python ist also nur dann schnell, wenn man es nicht benutzt. Schade.