Fibonacci with parallel execution? Threads?

Question

def recur_fibo(n):
   """Recursive function to
   print Fibonacci sequence"""
   if n <= 1:
       return n
   else:
       return(recur_fibo(n-1) + recur_fibo(n-2))

This code makes the recursive Fibonacci "simple"... Imagine I called:

recur_fibo(33)
recur_fibo(40)
recur_fibo(100)

How to make the calculation in parallel? I do not want that, for example, recur_fibo(100) only be calculated after recur_fibo(40) finish... I would like an implementation in Python 2 and 3 for me to learn the differences. I still don’t understand Threads, so I’d like a step-by-step explanation.

Answer 1

This implementation is not paralyzable "for real", besides being a "catastrophe". Yes, you want to know how to calculate different fibonaccis in parallel threads or processes - the answer to that would be an example of threadpool or processpoll (tip, look Concurrent.Futures) - but I won’t touch on that here.

What is not parallelizable is that you cannot have Fibo(10) in the same thread without having calculated Fibo(5) before - even if your Fibo function has Fibo(n-1) and Fibo(n-2) in separate threads/processes, you will have to wait for both of them to end. (and the catastrophe would be even greater - because threads and processes are MUCH heavier in terms of memory consumption than simple calls)

The implementation works very well for didactic purposes, up to Fibonacci of 10 - maybe up to 15 - but if you ask for a Fibonacci of 40 on it, it will crash your computer. 80 will stop possibly the world’s largest supercomputer.

This is because you have two function calls within each Fibonacci call. Python, to call a function creates in memory a new object of type "frame" - (along with an object for each local variable of the function, etc.. - in this case it will be only the variable 'n' - but being a Python integer uses a good 30 bytes - but the frame has about 400 bytes).

Well, if you ask Fibonacci for "3", that’s the starting frame, plus the Fibo(1) frame, plus the Fibo(2) frame - what your turn calls again Fibo(1) and Fibo(0) -- are 5 calls - now realize that if you ask Fibo(5) these 5 calls to Fibo(3), and 7 more calls to Fibo(4) ? That is: the number of function calls that Voce makes grows with the SQUARE of the number "n" (what we call complexity O(n²) ) - for example, if Fibo(5) uses ai a 1000 bytes (2**10), Fibo(10) will already use 2*20 bytes: 1 megabyte and Fibo (30) a GB.

The solutions are: Use a cache decorator: functools.lru_cache in your Fibonacci - this will make that for any known value, the function returns immediately, without executing its body (and port without two other calls) - that is, to calculate Fibo(7), Fibo(6) will be called once, but when Fibo(5) is called, its value will already be known, and there will be no need for new calls to the values 4, 3, 2, 1, 0 in the branch of (5).

But better still: leave the recursive example to understand recursion on the whiteboard, and write the function interactively - pass away from the exponential form.

Answer 2

I’ll leave an example with the threading module:

import threading

def fibo(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a+b
    data[threading.currentThread().getName()] = a

def get_results():
    while(threading.active_count() > 1): # enquanto houverem threads a trabalhar vais esperar, a main thread conta como 1, quando as threads acabarem vais retornar os dados
        continue
    return data

data = {} # armazenar os dados
fibos = [10, 15, 20, 30]
for k, v in enumerate(fibos, 1):
    t = threading.Thread(target=fibo, args=(v,), name='t_{}'.format(k)).start() # preparar cada thread e comecar trab

print(get_results()) # {'t_1': 55, 't_3': 6765, 't_2': 610, 't_4': 832040}

With queue:

import threading, queue

def fibo(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a+b
    data[threading.currentThread().getName()] = a
    if(threading.active_count() == 2): # se só houverem 2 threads, esta e a main
        kill_sig.put(True)

data = {} # armazenar os dados
kill_sig = queue.Queue()
fibos = [10, 15, 20, 30]
for k, v in enumerate(fibos, 1):
    t = threading.Thread(target=fibo, args=(v,), name='t_{}'.format(k)).start() # preparar cada thread e comecar trab

kill_sig.get() # bloquear aqui ate receber 'sinal'
print(data) # {'t_1': 55, 't_3': 6765, 't_2': 610, 't_4': 832040}

DEMONSTRATION

Answer 3

You can use the multiprocessing:

(In free translation)

multiprocessing is a package that supports spawning processes using an API similar to the module threading. The package multiprocessing offers local and remote competition, so efficient by bypassing the Global Interpreter Lock using subprocesses in turn of threads.

Multiprocessing

Below is an example of parallel execution using Pool:

from multiprocessing import Pool

def fib(n):
   if n <= 1:
       return n
   else:
       return(fib(n-1) + fib(n-2))

try:
    p = Pool()
    print (p.map(fib, [10, 15, 20]))
finally:
    p.close()

See demonstração

Threading / Queue

In accordance with mentioned by jsbueno, recursion in this case may not be the best output, below follows an alternative without the use of recursion (adapted of this Soen code), with Threads and Queue (FIFO, First In, First Out):

import Queue, threading

q = Queue.Queue()

def fib(n):
    a, b = 0, 1
    for i in range(0, n):
        a, b = b, a + b
    q.put((n, a))
    return

numeros = [10, 20, 25]

for n in numeros:
    t = threading.Thread(target=fib, args = (n,))
    t.daemon = True
    t.start()

while not q.empty():
    n, f = q.get()
    print ("{0}: {1}".format(n, f))

See demonstração

Concurrent.

Another alternative is the concurrent.futures mentioned by jsbueno, see an example (Python 3.x):

from concurrent.futures import ThreadPoolExecutor, as_completed

def fib(n):
    a, b = 0, 1
    for i in range(0, n):
        a, b = b, a + b
    return ((n, a))

numeros = [10, 20, 25]

with ThreadPoolExecutor(max_workers=5) as executor:
    fibSubmit = {executor.submit(fib, n,): n for n in numeros}

    for future in as_completed(fibSubmit):
        try:
            n, f = future.result()
        except Exception as exc:
            print("Erro! {0}".format(exc))
        else:
            print ("{0}: {1}".format(n, f))

See demonstração

See also this question: What is the advantage of using recursive functions?