Fibonacci running in parallel? Threads?

You can use multiprocessing :

  

(In free translation)

     

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

Multiprocessing

Below is an example of running parallel 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()

View demonstração

Threading / Queue

As mentioned by jsbueno , recursion in this case may not be the best output, below is an alternative without the use of recursion (adapted this SOen code ), with Threads and , First Out , / em>):

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))

View Queue

concurrent.futures

Another alternative is FIFO 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))

View demonstração

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

This implementation is not paralyzing "for real", besides being a "catastrophe". Yes, you want to know how to calculate different fibonaccis in threads or parallel processes - the answer to this would be an example of threadpool or processpoll (hint, look at concurrent.futures) - but I will not touch that subject here.

What is not parallelizable is that you can not have fibo (10) without first calculating fibo (5) - even if your fibo function has fibo (n-1) and fibo (n-2) in separate threads / processes, will have to wait both ends. (and the catastrophe would be even worse - because threads and processes are MUCH heavier in terms of memory consumption than simple calls)

The implementation works great for educational purposes, up to 10 fibonacci - maybe up to 15 - but if you ask for a fibonacci of 40 in it, it will crash your computer. The 80's will probably hold the world's largest supercomputer.

This happens 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 only be the variable 'n' - but being an integer in Python uses a good 30 bytes - but the frame has about 400 bytes).

Well, if you ask fibonacci of "3", this is the initial frame, plus the fibon frame (1), plus the fibon frame (2) - which in turn calls fibo (1) and fibo (0) - are 5 calls - now notice that if you ask for fibo (5) these calls will be to fibo (3), and another 7 calls to fibo (4)? That is, the number of function calls you make grows with the number squared "n" (what you call complexity O (n²)) - for example, if fibo (5) will use 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 cause that for any already known value, the function returns immediately, without executing its body (and portano 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 no new calls will be necessary to 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 - go away from the exponential form.

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}

STATEMENT