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

Este código faz o fibonacci recursivo "simples"... Imagine que eu chamasse:

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

Como fazer que o cálculo seja em paralelo? Não quero que, por exemplo, recur_fibo(100) só seja calculado após recur_fibo(40) terminar... Gostaria de uma implementação em Python 2 e 3 para eu aprender as diferenças. Ainda não entendo Threads, por isso gostaria de uma explicação passo a passo.

4
  • 1
    Só uma observação que pode ser útil para você, por mais que você faça uma execução paralela de operações de CPU bound com Threads, o python ira executar internamente em apenas uma thread graças a GIL (global internal lock). Sendo assim, para operações de CPU bound, use multiprocess Commented 10/08/2016 às 10:59
  • Se você quer performance utilize uma função recursiva com os dois números anteriores como parâmetro, assim ela só precisará ser chamada uma vez e não vai dobrar a cada chamada. O código seria desse jeito: def f(i,j,n): return f(j,i+j,n-1) if n else i; Daí a função fibonacci ficaria assim: def fibonacci(n): return f(1,1,n-1); Veja executando no ideone aqui: ideone.com/7rXz0s Commented 10/08/2016 às 13:18
  • @drgarcia1986 O Python não, o CPython . O GIL não é uma característica da linguagem, mas sim da implementação. Commented 10/08/2016 às 16:28
  • @PabloAlmeida você tem toda razão Commented 11/08/2016 às 10:17

3 Respostas 3

7

Essa implementaçao não é paralalizável "de verdade", além de ser uma "catástrofe". Sim, você quer saber como calcular diferentes fibonaccis em threads ou processos paralelos - a resposta para isso seria um exemplo de threadpool ou processpoll (dica, olhe concurrent.futures) - mas não vou tocar nesse assunto aqui.

O que não é paralelizável é que você não tem como ter, num mesmo thread, o fibo(10) sem ter calculado antes o fibo(5) - mesmo que a sua função fibo mande calcular fibo(n-1) e fibo(n-2) em threads/processos separados, vai ter que esperar ambos terminarem. (e a catastrofe seria ainda maior - por que threads e processos são MUITO mais pesados em termos de consumo de memória do que chamadas simples)

A implementação funciona muito bem para fins didáticos, até fibonacci de 10 - talvez até 15 - mas se você pedir um fibonacci de 40 nela, vai travar seu computador. De 80 vai travar possivelmente o maior supercomputador do mundo.

Isso acontece por que você tem duas chamadas de função dentro de cada chamada do fibonacci. O Python, para chamar uma função cria em memória um novo objeto do tipo "frame" - (junto com um objeto para cada variável local da função, etc.. - no caso será só a variável 'n' - mas sendo um inteiro em Python usa uns bons 30 bytes - mas o frame tem uns 400 bytes).

Bom, se você pedir fibonacci de "3", isso é o frame inicial, mais o frame de fibo(1), mais o frame de fibo(2) - que or sua vez chama de novo fibo(1) e fibo(0) -- sao 5 chamadas - agora perceba que se pedir fibo(5) vão ser essas 5 chamadas para o fibo(3), e mais 7 chamadas para o fibo(4) ? Ou seja: o número de chamadas de função que voce faz cresce com o QUADRADO do número "n" (o que chamaos de complexidade O(n²) ) - por exemplo, se fibo(5) for usar ai uns 1000 bytes (2**10), fibo(10) já vai usar 2**20 bytes: 1 megabyte e fibo (30) um GB.

As soluções são: Use um decorador de cache: functools.lru_cache em seu fibonacci - isso fará que para qualquer valor já conhecido, a função retorne imediatemente, sem executar seu corpo (e portano sem duas outras chamadas) - ou seja, para calculcar fibo(7), fibo(6) será chamado uma vez, mas quando fibo(5) for chamado, seu valor já vai ser conhecido, e não vão ser necessárias novas chamadas aos valores 4, 3, 2, 1, 0 no ramo do (5).

Mas melhor que isso ainda é: deixe o exemplo recursivo para entender recursão no quadro branco, e escreva a função de forma interativa - passe longe da forma exponencial.

2
  • 3
    Se o metodo for interativo - isso é: voce calcular a série com um for e variáveis dentro, esse custo desaparece - em Python você podera calcular fibonacci de 10000 em menos de 1 segundo.
    – jsbueno
    Commented 10/08/2016 às 12:13
  • 1
    @jsbueno, por obséquio, poderia mostrar o código com o concurrent.futures? Deixaria o tópico mais completo. Será um excelente aprendizado. Agradeço seus comentarios! Commented 10/08/2016 às 13:32
5

Você pode usar o multiprocessing:

(Em tradução livre)

multiprocessing é um pacote que suporta os processos de desova usando uma API semelhante ao módulo threading. O pacote multiprocessing oferece concorrência local e remoto, de forma eficaz contornando o Global Interpreter Lock usando subprocessos em vez de threads.

Multiprocessing

Segue abaixo um exemplo de execução paralela usando o 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()

Ver demonstração

Threading / Queue

Conforme mencionado pelo jsbueno, a recursividade neste caso pode não ser a melhor saída, segue abaixo uma alternativa sem o uso da recursão (adaptado deste código do SOen), com Threads e 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))

Ver demonstração

concurrent.futures

Uma outra alternativa é o concurrent.futures mencionado pelo jsbueno, veja um exemplo (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))

Ver demonstração

Veja também essa pergunta: Qual é a vantagem de usarmos funções recursivas?

16
  • Não entendi muito bem: p = Pool(4) print (p.map(recur_fibo, [33, 40, 100])) Commented 10/08/2016 às 1:12
  • Está usando Threads? Commented 10/08/2016 às 1:13
  • @PaulSigonoso Pool(4) indica o número de processos que serão criados, se não especificar nenhum, os.cpu_count é usado. Sobre Threads, não não é, mas é similar!
    – stderr
    Commented 10/08/2016 às 1:16
  • tentei rodar p.map(recur_fibo, [3, 4, 5]) mas parece que fica em loop... Commented 10/08/2016 às 1:18
  • Estranho: aqui p.map(recur_fibo, [3, 4, 5]) não dá erros mas não imprime nada... parece estar em loop... Commented 10/08/2016 às 1:27
5

Vou deixar um exemplo com o modulo threading:

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}

Com 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}

DEMONSTRAÇÃO

5
  • Ficou bacana o código. Sobre guardar os resultados, você pode usar o Queue fica legal também. :)
    – stderr
    Commented 10/08/2016 às 16:26
  • 1
    Isto num obj ficava melhor, mas depois ficava muito extenso. Obgado @zekk, o seu também está top. Estou a dar um estudo em concurrent.futures, acho que também é muito bom
    – Miguel
    Commented 10/08/2016 às 16:29
  • Aproveitei que tinha posto o exemplo com Threading e Multiprocessing, coloquei também esse.
    – stderr
    Commented 10/08/2016 às 17:17
  • Respostas excelentes. Estou aprendendo bastante. Obrigado! Commented 11/08/2016 às 17:01
  • De nada @PaulSigonoso.
    – Miguel
    Commented 11/08/2016 às 17:05

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .