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.