Uma análise comparativa no cálculo de Fibonacci com e sem uso de threads

Prévia do material em texto

Uma análise comparativa no cálculo recursivo de Fibonacci com e 
sem uso de threads 
 
Gabriel Júnior Griseli, Luis Felipe Zortea, Tobias Heitor Goettert 
gabrielgriseli@gmail.com, zortea.mil@gmail.com, tobiasheitor@gmail.com 
 
Departamento de Ciências Exatas e Engenharias - Universidade Regional Integrada do Alto 
Uruguai e das Missões (URI). 
Av. Sete de Setembro, 1621, Fátima CEP 99709-510 - Erechim - RS - Brasil 
 
Resumo. ​O cálculo de Fibonacci utilizando um algoritmo puramente recursivo é 
extremamente lento. Para sanar este problema, o presente artigo implementa uma 
solução utilizando um algoritmo recursivo com threads. Por fim são executados 
testes de comparação para verificar qual das duas abordagens, recursiva ou 
recursiva com threads, fornece o resultado de maneira mais rápida para o cálculo 
de Fibonacci. 
 
Palavras chaves:​ Fibonacci, threads, recursividade. 
 
Abstract. The calculation of Fibonacci using a purely recursive algorithm is 
extremely slow. To remedy this problem, the present article implements a solution 
using a recursive algorithm with threads. Finally, comparison tests are performed to 
verify which of the two approaches, recursive or recursive with threads, provides the 
result in a faster way for the calculation of Fibonacci. 
 
Keywords:​ Fibonacci, threads, recursion. 
 
1. INTRODUÇÃO 
 
O uso de recursividade no cálculo de Fibonacci não é indicado devido a sua natureza lenta. 
Porém, para fins de estudo de recursividade, o uso de algoritmos recursivos em Fibonacci é 
empregado. Para sanar parcialmente este problema pode-se utilizar threads no cálculo 
recursivo. 
Assim sendo, o presente trabalho tem por objetivo fazer uma comparação sobre a 
velocidade de resposta no cálculo de Fibonacci utilizando uma implementação de uma 
algoritmo puramente recursivo e outra implementação de um algoritmo recursivo com o uso 
de threads. 
A primeira abordagem vai implementar o algoritmo clássico recursivo de Fibonacci, 
com testes de tempo de execução e uso da CPU . A segunda abordagem vai da mesma forma 
buscar fazer um levantamento de velocidade e desempenho no cálculo de diversos números de 
Fibonacci, mas com uma implementação de um algoritmo recursivo com threads. Após a 
análise separada de cada abordagem implementada será feita uma comparação entre elas para 
verificar-se qual das delas apresenta um maior desempenho na velocidade de cálculo. 
Na primeira seção, será dada uma breve visão da Sequência Fibonacci, sua história e 
sua presença em nossa vida. Na segunda seção, serão apresentadas as diversas formas de 
encontrar Fibonacci, com um maior enfoque na forma recursiva. Na terceira seção, será dado 
uma explicação sobre o que são processos e principalmente threads. A quarta parte irá mostrar 
a implementação de um algoritmo recursivo com threads. A quinta seção demonstrará os 
resultados de comparação de tempo no cálculo de Fibonacci utilizando o algoritmo recursivo 
e utilizando o algoritmo recursivo com threads. Por fim, será apresentada a conclusão e as 
referências bibliográficas. 
 
2. SEQUÊNCIA DE FIBONACCI 
 
A sequência de Fibonacci é uma sequência numérica que começa com os números 0 e 1, e 
cada próximo número é encontrado através da soma dos dois números anteriores. Assim 
sendo, o próximo número da sequência é 1, esse número é resultante da soma de 0 (penúltimo 
número) e 1 (último número). Prosseguindo com este processo podemos encontrar a seguinte 
ordem numérica: 
0,1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584… 
Esta sequência numérica é conhecida pela humanidade a muito tempo. Os primeiros 
registros são gregos e indianos, porém existem resquícios de que ela já era conhecida pelos 
egípcios e até mesmo por povos pré-colombianos como os incas. 
Todavia, tal sequência numérica foi somente descrita formalmente pelo matemático 
italiano Leonardo de Pisa, mais conhecido como Fibonacci, em seu livro Liber Abaci no ano 
de 1202. Em tal livro Fibonacci descreve o crescimento de um população de coelhos que 
segue a proporção por ele estudada e que mais tarde ficou conhecida pelo seu nome, a 
Sequência de Fibonacci. 
Esta sequência tem um significado especial para estudo já que ela pode ser encontrada 
em proporções da natureza como na disposição das folhas em um ramo de uma árvore, no 
número de pétalas das flores, nas sementes de algumas flores e frutos, no formato da concha 
de alguns animais, dentre outros inúmeros lugares. Além de estar presente na natureza, a 
sequência está presente também na arquitetura humana, já que esta traz um equilíbrio 
harmônico para quem observa. 
 
3. FORMAS DE ENCONTRAR FIBONACCI 
 
A sequência de fibonacci pode ser encontrada de diversas formas. A forma mais usual é 
através da soma dos dois números anteriores, porém em Computação, a principal forma de 
encontrar a Sequência de Fibonacci é através da recursividade. A forma Recursiva de calcular 
Fibonacci é utilizada sobretudo para fins de estudo e compreensão dos alunos sobre 
algoritmos recursivos. Entretanto vale ressaltar que tal forma de calcular Fibonacci se mostra 
muito pouco eficiente quando comparado a outras técnicas. O algoritmo de Fibonacci 
recursivo em C++ pode ser observado na Figura 1. 
 
Figura 1 - Algoritmo recursivo de Fibonacci em C++ 
 
Fonte: elaborada pelos autores do artigo. 
 
Como demonstra a Figura 1, o algoritmo recursivo irá testar se n é menor ou igual a 1, 
caso seja verdadeiro irá retornar o valor de n. Caso n seja maior de 1, será chamada duas 
funções fib para calcular o Fibonacci de n - 1 e Fibonacci de n - 2. Este algoritmo irá gerar a 
árvore apresentada na Figura 2 para Fibonacci de 5. 
Como escrito anteriormente, o método recursivo para Fibonacci não é interessante em 
termos práticos , pois, conforme a figura mostra, o cálculo de muitos números é repetido, 
tornando o algoritmo extremamente lento. No caso apresentado na Figura 2 fib(2) é calculado 
3 vezes. 
Figura 2 - Árvore Gerada a partir de Fibonacci de 5 
 
Fonte: https://classes.soe.ucsc.edu/cmpe012/Fall08/labs/lab8-Recursion-vs-Iteration/ 
 
4. PROCESSOS E THREADS 
 
Uma definição interessante para processos e threads pode ser encontrado no livro Sistemas 
Operacionais de Oliveira, Carissimi e Toscani: 
 
Um processo é uma abstração que reúne uma série de atributos como espaço de 
endereçamento, descritores de arquivos abertos, permissões de acesso, quotas, etc. 
Um processo possui, ainda, áreas de código, dados e pilha de execução. Também é 
associado ao processo um fluxo de execução. Por sua vez, uma thread nada mais é 
que um fluxo de execução. Na maior parte das vezes, cada processo é formado por 
um conjunto de recursos mais uma única thread.(OLIVEIRA; CARISSIMI; 
TOSCANI, 2010, p. 110). 
 
Portanto, threads são linhas de execução em um processo. Ela traz inúmeras vantagens 
como uma maior capacidade de resposta, compartilhamentode recursos, economia e 
escalabilidade. 
É importante que um processo tenha maior capacidade de resposta. Por exemplo, caso 
o programador utilize em um editor de texto uma única thread e o usuário imprimir algo, será 
necessário que a impressão acabe para o usuário poder voltar a editar o texto. Agora, caso o 
programador use uma thread para edição e uma para impressão, irá aumentar a capacidade de 
resposta do processo e interatividade com o usuário. 
O compartilhamento de recursos é outro fator importante. O uso de threads permite 
que cada nova linha de execução criada compartilhe dos recursos do processo. Isso possibilita 
um uso menor da memória principal e também torna a comunicação entre threads mas fácil, já 
que todos os recursos são compartilhados. 
Economia é um dos principais pontos favoráveis no uso de threads, já que vários 
fluxos de execução em um processo permite uma economia de tempo e recursos, tornando a 
execução de um programa mais rápido. 
Por fim temos a escalabilidade. A escalabilidade permite que em uma CPU 
multithread um processo tenha partes de seu código sendo executadas simultaneamente. 
 
5. FIBONACCI COM THREADS 
 
Para fins de estudo e comparação com o algoritmo puramente recursivo foi utilizado threads 
no cálculo de Fibonacci. Ao invés de empilhar as chamadas de funções e ir retornando e 
calculando cada chamada de função, o uso de threads permite que mais de uma linha de 
execução (mais de uma chamada de função) seja feita ao mesmo tempo. 
Na abordagem recursiva toda sub árvore criada a esquerda de um chamada de 
Fibonacci deve ser calculada antes da sub árvore criada a direita. Com o uso de threads esse 
problema pode ser parcialmente resolvido. Cada nova subárvore criada cria-se uma thread 
para calculá-la. Desta maneira não é necessário calcular cada chamada de Fibonacci uma por 
vez, mas com várias simultaneamentes. Entretanto para evitar um excesso de threads e estouro 
da pilha de threads optou-se por limitar o número máximo para 15 linhas de execução. 
A linguagem de programação escolhida para implementação dos algoritmos foi C++ 
na sua versão 11, que disponibiliza uma biblioteca para trabalhar com threads. a Função 
principal pode ser observada na Figura 3 e a função que calcula o n-ésimo elemento de 
Fibonacci pode ser analisada na Figura 4. 
 
Figura 3 - Função Principal 
 
Fonte: elaborada pelos autores do artigo. 
 
Figura 4 - Função que calcula o n-ésimo elemento de Fibonacci 
 
Fonte: elaborada pelos autores do artigo. 
 
Além da biblioteca threads foi necessário a utilização da biblioteca future, pois uma 
thread não permite retornar um valor. Assim, como é necessário obter o resultado da thread, a 
classe future possibilita isto acessando o dado somente quando este estiver sido calculado. 
Basicamente o algoritmo apresentado chama a função cal_fib para calcular o n-ésimo 
número de Fibonacci. Caso n seja menor ou igual a 1 retorna-se seu valor. Caso contrário 
verifica-se se o número limite de threads foi ultrapassado, caso não tenha sido ultrapassado 
cria-se duas threads, uma para fib(n-1) e outra para fib(n-2). Porém caso o número máximo de 
threads tenha sido alcançado Fibonacci é calculado recursivamente atraves da função 
cal_fib_rec. 
 
6. TESTES 
 
Os testes visaram verificar a diferença no tempo de execução do cálculo do n-ésimo elemento 
da Sequência Fibonacci utilizando recursividade com threads e utilizando apenas 
recursividade. Para isso os testes foram conduzidos em um computador equipado com um 
processador Intel Core i3 2100 (2 núcleos, suporta 4 threads, frequência baseada em 
processador igual a 3.10 GHz e 3 MB de cache) e Windows 7 como Sistema Operacional. 
Para fins de comparação de performance, foi utilizado a IDE Visual Studio 2017, ferramenta 
esta que permitiu diversas comparações de tempo de execução e uso da CPU. 
O algoritmo recursivo e com uso de threads calculou o 5°, 15°, 25°, 35°, 36°, 37°, 38°, 
39° e 40° elemento de Fibonacci. Foram feitas inúmeras buscas e após o levantamento de 
tempo eliminou-se os menores e maiores resultados para, desta forma, proporcionar uma 
média mais realista. Os dados recolhidos foram dispostos em dois gráfico, para deixar mais 
visível a diferença de tempo entre cada implementação de cálculo. 
O primeiro gráfico, ilustrado na Figura 5, mostra o tempo de execução de Fibonacci de 
5, 15, 25 e 35. É perceptível que nas duas primeiras comparações a abordagem recursiva 
mostra-se minimamente mais vantajoso sobre o algoritmo com uso de threads. Já na terceira 
comparação os dois algoritmos praticamente se equiparam no tempo de execução. A partir da 
quarta comparação, com Fibonacci de 35, o uso de threads mostra-se ligeiramente mais 
vantajoso. 
As primeiras comparações mostram uma pequena vantagem para o uso da 
recursividade, isso se deve em grande parte ao fato de que a criação de threads demanda um 
pequeno acréscimo de tempo que não se mostra vantajoso em números pequenos de 
Fibonacci. Porém a partir de maiores números, o tempo gasto com a criação de outras linhas 
de execução torna-se compensatória. 
Figura 5 - Tempo de execução em segundos de Fibonacci de 5, 15, 25 e 35.
 
Fonte: elaborada pelos autores do artigo. 
 
A partir de Fibonacci de 36 optou-se separar em outro gráfico, Figura 6, para tornar a 
comparação entre os valores mais clara. Neste gráfico percebe-se que o uso de threads tende a 
terminar antes do uso de recursividade apenas. 
 
Figura 6 - Tempo de execução em segundos de Fibonacci de 36, 37, 38, 39 e 40. 
 
Fonte: elaborada pelos autores do artigo. 
 
Por fim, pode-se observar na Figura 7 o uso da CPU sem e com threads 
respectivamente. 
 
Figura 7 - Uso da CPU com recursividade e com threads. 
 
Fonte: elaborada pelos autores do artigo. 
 
É perceptível que o uso de threads faz com que a CPU seja usada praticamente 
o tempo inteiro a 100% de seu potencial de processamento, enquanto o uso da abordagem 
recursiva utiliza por volta de 25% de todo potencial de processamento da CPU. 
Verificando as especificações do processador, constatou-se que este pode trabalhar 
com até quatro threads simultaneamente. Ao observarmos a Figura 7 é possível visualizar que 
a abordagem recursiva utiliza uma única linha de execução e desta forma somente uma parte 
da CPU é utilizada, isto ocasiona no uso de apenas 25% do processador (¼). Porém ao utilizar 
mais linhas de execução todo poder de processamento da CPU é utilizado. 
 
7. CONCLUSÃO 
 
O uso de threads é muito importante em Cálculos computacionais. Quando bem aplicada, a 
utilização de mais linhas de execução permite um desempenho muito mais ágil do processo 
todo. 
O presente artigo retratou justamente este ponto utilizando como pano de fundo o 
cálculo de Fibonacci, cálculo este muito estudado em computação. A implementação 
puramente recursiva mostrou-se na imensa maioria das vezesmuito mais lenta no 
processamento das operações, enquanto a implementação recursiva com uso de threads 
mostrou um desempenho superior de maneira geral. Quanto maior era o número de Fibonacci 
a ser calculado, maior mostrava-se a diferença na comparação entre as duas implementações. 
Outro ponto constatado foi o fato que o uso de threads possibilita um uso muito maior 
do poder de processamento da CPU. Enquanto a abordagem recursiva atingia apenas 25% de 
uso da CPU, a abordagem recursiva com threads utilizava praticamente 100% da CPU, fator 
este condicionado pelo suporte de até 4 threads do processador. 
Finalmente é perceptível que a utilização de threads em um processo pode tornar seu 
tempo de execução muito menor e aproveitar o processador de forma mais eficaz. Portanto 
um programa construído sob tal perspectiva pode melhorar o desempenho consideravelmente 
e tornar a experiência do usuário extremamente positiva. 
 
REFERÊNCIA BIBLIOGRÁFICAS 
 
OLIVEIRA, R. S.; CARISSIMI, A. S.; TOSCANI, S. S. ​Sistemas operacionais ​. 4. ed. Porto 
Alegre: Bookman, 2010. (Livros Didáticos Informática UFRGS, v. 11). 
 
SILBERSCHATZ, Abraham ; GALVIN, Peter Baer; GAGNE, Greg. ​Fundamentos de 
Sistemas Operacionais Princípios Básicos​.1/2013. ed. [S.l.]: LTC, 2013. 450 p. 
 
ROHDE, Tiago M.; DESTEFANI, Luciano; MARTINS, Rogério.; FERRARI, Edilaine R. ​As 
diferentes técnicas de implementação paralela de algoritmos recursivos em C. Disponível 
em: <http://www.lbd.dcc.ufmg.br/colecoes/erad-rs/2012/0034.pdf>. Acesso em: 05 maio 
2017. 
 
TANENBAUM, Andrew S. ​Sistemas Operacionais Modernos ​. 3ª. ed. / ​5º reimpressão​: 
Pearson, 2010. 653 p. 
 
WIKIPÉDIA, a enciclopédia livre. ​Sequência de Fibonacci. ​Disponível em: 
<https://pt.wikipedia.org/wiki/Sequ%C3%AAncia_de_Fibonacci>. Acesso em: 07 maio 2017. 
 
CORPORATION, Intel. ​Processador Intel Core i3 2100​. Disponível em: 
<https://ark.intel.com/pt-br/products/53422/Intel-Core-i3-2100-Processor-3M-Cache-3_10-G
Hz>. Acesso em: 30 jun. 2017.