A decorator for automatic algorithms optimization via fast matrix exponentiation
Project description
A decorator for automatic algorithms optimization via fast matrix exponentiation
Installation
You can install the stable version of the library using pip:
sudo pip install cpmoptimize
Or install a previously downloaded and extracted package:
sudo python setup.py install
Basic Example
Suppose we want to calculate the ten millionth Fibonacci number using a program in Python. The function with a trivial algorithm is rather slow:
def fib(n):
a = 0
b = 1
for i in xrange(n):
a, b = b, a + b
return a
result = fib(10 ** 7)
# Time: 25 min 31 sec
But if we apply the optimizing decorator, the function will give you the answer much faster:
from cpmoptimize import cpmoptimize
@cpmoptimize()
def fib(n):
a = 0
b = 1
for i in xrange(n):
a, b = b, a + b
return a
result = fib(10 ** 7)
# Time: 18 sec (85x faster)
Description
Actually, the decorator disassembles bytecode of a function using pretty byteplay library, analyzes the code, and tries to reduce time complexity of the algorithm used in it using fast matrix exponentiation.
The decorator uses a method implemented by Alexander Skidanov in his simple optimizing interpreter.
A detailed description of the library (including an idea explanation and an interface reference) is available in English and Russian.
Project details
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.