COMPARATIVE ANALYSIS OF DATA STRUCTURE EFFICIENCY IN DIFFERENT PROGRAMMING LANGUAGES (RUST, C#, JAVA, AND PYTHON 3)
REGISTRO DOI: 10.69849/revistaft/cl10202411231210
João Paulo Favaretto Silva1
João Henrique Gião Borges2
Fabiana Florian3
Resumo: Este trabalho apresenta uma análise comparativa de desempenho de três algoritmos de ordenação — Bubble Sort, Quick Sort e Shell Sort — em quatro linguagens de programação: Rust, C#, Java e Python 3. O estudo visa avaliar como a escolha da linguagem de programação pode influenciar a eficiência dos algoritmos, especialmente em cenários com grandes volumes de dados. Cada algoritmo foi executado em contêineres isolados e repetido cinco vezes com vetores gerados a partir de uma mesma semente, para garantir uniformidade nos testes. A mediana dos tempos de execução foi utilizada para indicar as discrepâncias de desempenho entre as linguagens. Os resultados mostraram que Rust apresenta a melhor eficiência, com tempos de execução menores, enquanto Python foi a linguagem com o pior desempenho, devido à sua natureza interpretada. Java e C# obtiveram resultados intermediários, com desempenho inferior a Rust e C# em alguns casos, mas superior ao Python. Conclui-se que esta análise fornece insights valiosos para desenvolvedores e pesquisadores sobre a escolha de linguagens e estruturas de dados para aplicações que exigem alta performance, oferecendo uma base para decisões informadas no desenvolvimento de software eficiente.
Palavras-chave: Desempenho. Algoritmos. Linguagens. Eficiência. Ordenação. Análise.
Abstract: This paper presents a comparative performance analysis of three sorting algorithms — Bubble Sort, Quick Sort, and Shell Sort — in four programming languages: Rust, C#, Java, and Python 3. The study aims to evaluate how the choice of programming language can influence algorithm efficiency, particularly in scenarios with large data volumes. Each algorithm was executed in isolated containers and repeated five times with vectors generated from the same seed to ensure uniformity in the tests. The median of the execution times was used to indicate performance discrepancies among the languages. The results showed that Rust demonstrated the best efficiency, with shorter execution times, while Python had the worst performance due to its interpreted nature. Java and C# yielded intermediate results, with performance inferior to Rust but better than Python in some cases. It is concluded that this analysis provides valuable insights for developers and researchers regarding the choice of languages and data structures for applications requiring high performance, offering a foundation for informed decision-making in the development of efficient software.
Keywords: Performance. Algorithms. Languages. Efficiency. Sorting. Analysis.
1 INTRODUÇÃO
Pequenas melhorias no tempo de execução de algoritmos podem ter um impacto significativo, especialmente em cenários onde o processamento de grandes volumes de dados se faz necessário seja na análise de dados em tempo real ou em sistemas de processamento de transações financeiras. Pequenas otimizações no desempenho de algoritmos podem resultar em ganhos perceptíveis de eficiência e economia de recursos computacionais. Para os clientes e usuários finais, isso se traduz em uma experiência mais ágil e responsiva, enquanto para as empresas, pode representar economias de custo significativas e a capacidade de lidar com um maior volume de dados sem comprometer a qualidade do serviço. Portanto, a busca por estruturas de dados e algoritmos mais eficientes não apenas beneficia os desenvolvedores e pesquisadores, mas também tem um impacto direto na satisfação do cliente e no sucesso do negócio.
A rápida evolução da capacidade computacional tem sido acompanhada por um aumento exponencial na quantidade de dados manipulados pelos sistemas computacionais. Conforme Weiss(2014, p.15):
“À medida que os computadores se tornam cada vez mais rápidos, a necessidade de programas que possam lidar com grandes quantidades de dados se torna mais urgente. Paradoxalmente, isso exige uma atenção mais cuidadosa à eficiência, pois as ineficiências nos programas se tornam mais evidentes quando os tamanhos dos dados são grandes.”
Portanto, torna-se essencial realizar uma análise comparativa das estruturas de dados em diferentes linguagens de programação, a fim de identificar as abordagens mais eficientes para lidar com essa crescente demanda por processamento de dados.
O objetivo deste trabalho é analisar o desempenho em algumas estruturas de dados (bubblesort, quicksort, shellsort) em quatro linguagens de programação (Rust, C#, Java e Python 3). Este estudo visa compreender como a escolha da linguagem de programação pode afetar o desempenho e a eficiência dos algoritmos.
Com base nos resultados, foi possível identificar padrões e tendências que possam orientar desenvolvedores na seleção das estruturas de dados mais adequadas para cada situação.
Ao fornecer informações sólidas e comparativas sobre o desempenho das estruturas de dados em diferentes linguagens, a pesquisa busca oferecer aos desenvolvedores uma base sólida para tomadas de decisão mais informadas no início da criação de projetos, visando a otimização e eficiência do desenvolvimento de software.
Foi realizada uma pesquisa bibliográfica e comparado três códigos de ordenação que foram isolados em containers, onde ordenarão um vetor de números feito por uma função com uma semente, que resulta no mesmo vetor entre as linguagens, o vetor foi ordenado cinco vezes com uma semente. Foram analisadas cinco sementes diferentes, para cada linguagem, resultando em uma mediana que mostrará discrepâncias entre os resultados. Foram comparados os métodos de ordenação bubble sort, quick sort, shellsort em quatro linguagens de programação: Rust, C#, Java e Python 3.
2 REVISÃO BIBLIOGRÁFICA
Esta seção apresenta um breve conceito sobre as ferramentas utilizadas na comparação e na criação dos métodos de estruturas de dados.
2.1 ALGORITMOS
Algoritmos de ordenação organizam dados em uma sequência específica, como numeração crescente ou decrescente, facilitando a busca e análise dos dados.
“De forma informal, um algoritmo é qualquer procedimento computacional bem definido que recebe um valor, ou conjunto de valores, como entrada e produz um valor, ou conjunto de valores, como saída. Assim, um algoritmo é uma sequência de passos computacionais que transformam a entrada na saída.” (CORMEN, etc 2009, p. 5).
2.2 MÉTODOS DE ORDENAÇÃO
Algoritmos de ordenação organizam dados em uma sequência específica, como numeração crescente ou decrescente, facilitando a busca e análise dos dados.
” A ordenação nada mais é do que alfabetizar, categorizar, organizar ou colocar itens em uma sequência ordenada. É uma operação fundamental na área da ciência da computação. ” (MUHAMMAD IDREES, etc, 2016, p. 1).
2.2.1 BUBBLE SORT
Bubble sort é um algoritmo de ordenação simples que compara e troca elementos adjacentes repetidamente até que a lista esteja ordenada.
“O Bubble Sort é um algoritmo de ordenação popular, mas ineficiente. Ele funciona trocando repetidamente elementos adjacentes que estão fora de ordem.” (CORMEN, etc 2009, p. 40).
2.2.2 QUICK SORT
Quicksort é um algoritmo de ordenação eficiente que utiliza a abordagem de divisão e conquista, dividindo a lista em partições menores, ordenando-as recursivamente e combinando os resultados.
“O quicksort é frequentemente a melhor escolha prática para ordenação porque é notavelmente eficiente em média: seu tempo de execução esperado é O(n log n), e os fatores constantes ocultos na notação O(n log n) são bastante pequenos.” ((CORMEN, etc 2009, p. 170).
2.2.3 SHELL SORT
Ele é uma extensão do algoritmo de inserção, destinado a melhorar sua eficiência em grandes listas. O Shellsort é baseado na ideia de comparar e trocar elementos que estão distantes uns dos outros, diminuindo gradualmente a distância até que a comparação final seja feita entre elementos adjacentes.
“Introduzida por D. L. Shel, que utiliza a ordenação por inserção em subsequências periódicas da entrada para produzir um algoritmo de ordenação mais rápido.” (CORMEN, etc 2009, p. 192).
2.3 LINGUAGENS DE PROGRAMAÇÃO
Linguagens de programação diferem em como gerenciam a memória, otimizam o código e tratam a concorrência, características que afetam diretamente o desempenho de algoritmos intensivos, como os de ordenação. Linguagens como Rust, C#, Java e Python variam em abordagem, desde linguagens compiladas e de baixo nível até linguagens interpretadas e de uso geral, influenciando diretamente a eficiência computacional.
“As linguagens de programação não apenas determinam a forma da implementação de um algoritmo, mas também impactam seu desempenho por meio de diferentes abordagens de compilação, gerenciamento de memória e estruturação de dados.” (Sebesta, Robert W., 2012, p. 65).
2.3.1 RUST
Rust é uma linguagem de programação de sistemas focada em segurança, velocidade e concorrência.
“Rust é uma linguagem de programação que oferece controle de baixo nível, memória segura e alta performance, projetada para garantir segurança e evitar problemas como falhas de segmentação e concorrência de dados. (Mozilla, 2021).
2.3.2 C#
C# é uma linguagem de programação moderna, orientada a objetos, desenvolvida pela Microsoft, utilizada principalmente para desenvolvimento de aplicações na plataforma .NET.
“C# é uma linguagem de programação simples, moderna, orientada a objetos e com tipagem forte, projetada para ser utilizada na plataforma .NET para desenvolvimento de uma ampla gama de aplicações” (Microsoft, T.V., 2016).
2.3.3 JAVA
Java é uma linguagem de programação orientada a objetos, conhecida por sua portabilidade, que permite que o mesmo código seja executado em diferentes plataformas.
“Java é uma linguagem de programação e plataforma computacional de alta performance, orientada a objetos, que permite a criação de software que pode rodar em qualquer dispositivo que suporte a Java Virtual Machine (JVM).” (Oracle, 2024).
2.3.4 PYTHON 3
Python é uma linguagem de programação de alto nível, interpretada e de propósito geral, conhecida por sua sintaxe clara e suporte robusto para múltiplos paradigmas de programação.
“Python é uma linguagem de programação interpretada, interativa e orientada a objetos, que combina clareza de sintaxe com extensibilidade e uma ampla biblioteca padrão.” (Python Software Foundation, 2024).
2.3 CONTAINERS
Containers são ambientes isolados e padronizados que permitem a execução consistente de aplicativos, proporcionando reprodutibilidade e minimizando problemas de compatibilidade entre sistemas operacionais. Eles oferecem um nível de isolamento semelhante ao das máquinas virtuais, mas com menor sobrecarga, o que os torna ideais para experimentos de desempenho.
“Containers têm revolucionado a implantação de software ao fornecer ambientes leves e consistentes, eliminando as discrepâncias entre ambientes de desenvolvimento e produção e promovendo a reprodutibilidade.” (Merkel, Dirk, 2014, p. 3).
3 DESENVOLVIMENTO
Para os métodos de ordenação serem analisados, foi necessário que elas sejam equivalentes nas suas respectivas linguagens. Neste trabalho, implementado o algoritmo de ordenação Bubble Sort em Rust, C#, Java e Python, garantindo que a funcionalidade e o comportamento sejam consistentes entre as linguagens.
3.1 IMPLEMENTAÇÃO DO BUBBLESORT
Foi implementado o algoritmo BubbleSort de maneira idêntica em cada linguagem. Foi incluído um contador para cada linguagem registrar o número de trocas de memória realizadas durante a ordenação e uma função para contabilizar o início e a parada da estrutura de dados (Figura, 1,2,3,4).
Figura 1 – bubble sort em Python 3
Fonte: Própria.
Figura 2 – bubble sort em C#
Fonte: Própria.
Figura 3 – bubble sort em JAVA
Fonte: Própria.
Figura 4 – bubble sort em Rust
Fonte: Própria.
3.2 IMPLEMENTAÇÃO DO SHELLSORT
Foi implementado o algoritmo Shell Sort de maneira idêntica em cada linguagem. Foi incluído um contador para cada linguagem registrar o número de trocas de memória realizadas durante a ordenação e uma função para contabilizar o início e a parada da estrutura de dados (Figura, 5,6,7,8).
Figura 5 – shell sort em Python 3
Fonte: Própria.
Figura 6 – shell sort em C#
Fonte: Própria.
Figura 7 – shell sort em JAVA
Fonte: Própria
Figura 8 – shell sort em Rust
Fonte: Própria.
3.2 IMPLEMENTAÇÃO DO QUICKSORT
Foi implementado o algoritmo QuickSort de maneira idêntica em cada linguagem. Foi incluído um contador para cada linguagem registrar o número de trocas de memória realizadas durante a ordenação e uma função para contabilizar o início e a parada da estrutura de dados (Figura, 9,10,11,12).
Figura 9 – QuickSort em Python 3
Fonte: Própria.
Figura 10 – QuickSort em C#
Fonte: Própria.
Figura 11 – QuickSort em JAVA
Fonte: Própria.
Figura 12 – QuickSort em Rust
Fonte: Própria.
3.5 ALGORITMO DE GERAÇÃO
Para garantir que os mesmos dados sejam utilizados em todas as linguagens e que a geração dos números seja feita de maneira controlada, podemos usar um gerador de números pseudo-aleatórios que aceita uma semente. Dessa forma, ao passar a mesma semente para cada implementação, foi garantido que o vetor gerado em cada linguagem seja idêntico (Figura, 13,14,15,16).
3.5.1 PYTHON 3
Figura 13 – Algorítimo de geração em Python
Fonte: Própria.
3.5.2 JAVA
Figura 14 – Algorítimo de geração em Java
Fonte: Própria.
3.5.3 C#
Figura 15 – Algorítimo de geração em C#
Fonte: Própria.
3.5.4 RUST
Figura 16 – Algorítimo de geração em Rust
Fonte: Própria.
3.6 COMPARAÇÃO DE RESULTADO
Para analisar a eficiência de diferentes estruturas de dados e algoritmos em várias linguagens de programação, foi e comparado os algoritmos de ordenação Bubble Sort e Quick Sort nas linguagens Rust, C#, Java e Python. Esta análise permite observar as diferenças de desempenho de cada linguagem em termos de tempo de execução e número de trocas de memória realizadas durante a ordenação de um conjunto de dados.
Os algoritmos foram testados com conjuntos de dados contendo 1.000, 10.000 e 100.000 números, assegurando que as condições de teste fossem idênticas para todas as implementações. Todos os testes foram executados no mesmo ambiente, em um contêiner Debian. O tempo de execução e o número de trocas de memória foram registrados e comparados, sendo que cada teste foi repetido cinco vezes com diferentes sementes, e a mediana dos resultados foi utilizada para análise, representadas nos seguintes quadros (quadros, 1,2,3,4).
Quadro 1 – O tempo de execução em Python.
| Mediana na Base de 1.000 | Python | |
| Mediana do Bubble Sort: | 0,192748 | segundos |
| Mediana do Shell Sort: | 0,006012 | segundos |
| Mediana do Quick Sort: | 0,00577 | segundos |
| Mediana na Base de 10.000 | Python | |
| Mediana do Bubble Sort: | 20,471339 | segundos |
| Mediana do Shell Sort: | 0,093175 | segundos |
| Mediana do Quick Sort: | 0,26579 | segundos |
| Mediana na Base de 100.000 | Python | |
| Mediana do Bubble Sort: | 2157,160532 | segundos |
| Mediana do Shell Sort: | 1,127856 | Segundos |
| Mediana do Quick Sort: | 23,855839 | segundos |
Fonte: Própria.
Quadro 2 – O tempo de execução em Java
| Mediana na Base de 1.000 | JAVA | |
| Mediana do Bubble Sort: | 0,01554181 | segundos |
| Mediana do Shell Sort: | 0,00187939 | segundos |
| Mediana do Quick Sort: | 0,00138156 | segundos |
| Mediana na Base de 10.000 | JAVA | |
| Mediana do Bubble Sort: | 0,21741443 | segundos |
| Mediana do Shell Sort: | 0,00922003 | segundos |
| Mediana do Quick Sort: | 0,00841898 | segundos |
| Mediana na Base de 100.000 | JAVA | |
| Mediana do Bubble Sort: | 19,27737299 | segundos |
| Mediana do Shell Sort: | 0,01876017 | segundos |
| Mediana do Quick Sort: | 0,10704652 | segundos |
Fonte: Própria.
Quadro 3 – O tempo de execução em C#
| Mediana na Base de 1.000 | C# | |
| Mediana do Bubble Sort: | 0,004185 | segundos |
| Mediana do Shell Sort: | 0,000435 | segundos |
| Mediana do Quick Sort: | 0,001043 | segundos |
| Mediana na Base de 10.000 | C# | |
| Mediana do Bubble Sort: | 0,531742 | segundos |
| Mediana do Shell Sort: | 0,002539 | segundos |
| Mediana do Quick Sort: | 0,00706 | segundos |
| Mediana na Base de 100.000 | C# | |
| Mediana do Bubble Sort: | 69,858435 | segundos |
| Mediana do Shell Sort: | 0,0297 | segundos |
| Mediana do Quick Sort: | 0,616691 | segundos |
Fonte: Própria.
Quadro 4 – O tempo de execução em Rust
| Mediana na Base de 1.000 | Rust | |
| Mediana do Bubble Sort: | 0,00067344 | segundos |
| Mediana do Shell Sort: | 0,0000553 | segundos |
| Mediana do Quick Sort: | 0,000048 | segundos |
| Mediana na Base de 10.000 | Rust | |
| Mediana do Bubble Sort: | 0,08409204 | segundos |
| Mediana do Shell Sort: | 0,00085084 | segundos |
| Mediana do Quick Sort: | 0,00140377 | segundos |
| Mediana na Base de 100.000 | Rust | |
| Mediana do Bubble Sort: | 12,61619019 | segundos |
| Mediana do Shell Sort: | 0,00842582 | segundos |
| Mediana do Quick Sort: | 0,07672308 | segundos |
Fonte: Própria.
Com base nos dados obtidos, foi realizada uma análise gráfica que revela a eficiência das linguagens e dos métodos de ordenação. Foram elaborados dois tipos de gráficos: um para demonstrar a eficiência entre as linguagens e outro para mostrar a eficiência entre os métodos de ordenação. Ao compararmos o tempo de processamento em relação ao tamanho do conjunto de dados, obtemos os gráficos a seguir.
Figura 17 – Gráfico para os métodos.
Fonte: Própria.
Figura 18 – Gráfico para as Linguagens.
Fonte: Própria.
Observa-se claramente as complexidades de tempo dos algoritmos (notação O(n)) representadas em seus respectivos desempenhos. Como esperado, o Bubble Sort apresentou o pior desempenho em todas as situações, enquanto o Quick Sort e o Shell Sort mantiveram tempos de execução semelhantes. A vantagem do Shell Sort se deve à menor quantidade de dados processada e a seu comportamento ligeiramente mais imprevisível.
É notável que a linguagem Rust demonstrou uma maior estabilização no crescimento do tempo de execução, destacando-se como a mais eficiente. Python, por outro lado, apresentou um desempenho consideravelmente mais lento, exibindo um crescimento no tempo de execução que sugere uma complexidade efetiva superior à das outras linguagens. Isso pode ser interpretado como um comportamento próximo de O(nk), onde k > 2 em algumas situações, especialmente para o Bubble Sort.
Rust conseguiu manter um desempenho superior às demais linguagens, especialmente nos casos com 10.000 e 100.000 dados, apresentando uma complexidade efetiva próxima de O(nk) para Shell Sort e Quick Sort, enquanto C# e Java mantiveram O(nk+1).
4 CONCLUSÃO
Este trabalho apresentou uma análise comparativa do desempenho de três algoritmos de ordenação — Bubble Sort, Quick Sort e Shell Sort — implementados em quatro linguagens de programação: Rust, C#, Java e Python 3. A análise foi conduzida em um ambiente controlado, onde os algoritmos foram isolados em containers e executados cinco vezes para cada linguagem, utilizando um vetor gerado a partir de funções com sementes idênticas para garantir consistência nos resultados. A mediana dos tempos de execução foi utilizada para destacar discrepâncias e fornecer uma medida representativa de desempenho.
Os resultados revelaram diferenças significativas no tempo de execução dos algoritmos entre as linguagens. O Python, notoriamente mais lento em operações intensivas de CPU devido à sua natureza interpretada, apresentou tempos de execução maiores, especialmente com o algoritmo Bubble Sort, que possui complexidade quadrática. Linguagens compiladas como Rust e C# demonstraram desempenho muito superior em todos os algoritmos, evidenciando sua adequação para aplicações onde a eficiência é crucial. Java, enquanto mais rápido que Python, apresentou desempenho inferior a Rust e C# em alguns cenários, confirmando as limitações do ambiente de execução da JVM em comparação direta com código nativo.
A pesquisa confirma que a escolha da linguagem de programação pode impactar significativamente o desempenho dos algoritmos de ordenação, especialmente em contextos de grandes volumes de dados. Rust e C#, com suas arquiteturas de baixo nível e gestão eficiente de memória, destacaram-se como as opções mais adequadas para aplicações que exigem alta performance. Já o Python, apesar de menos eficiente, ainda é valioso para prototipação e desenvolvimento rápido em contextos onde o desempenho extremo não é o principal requisito.
Este estudo oferece uma base sólida para desenvolvedores e arquitetos de software avaliarem a linguagem e os algoritmos de ordenação mais adequados para suas necessidades específicas. Em um cenário onde o volume de dados cresce exponencialmente, a escolha informada de ferramentas e técnicas pode proporcionar uma economia significativa de recursos e uma melhor experiência para o usuário final. A metodologia adotada também fornece um modelo que pode ser replicado e expandido para avaliar outras estruturas de dados e algoritmos, promovendo práticas de desenvolvimento mais eficientes e baseadas em evidências.
REFERÊNCIAS BIBLIOGRÁFICAS
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C., Introduction to Algorithms, Third Edition. MIT Press., 2009.
Microsoft. C# Documentation. Disponível em: https://dotnet.microsoft.com/pt-br/learn/csharp. Acesso em 2024.
Mozilla. Mozilla Welcomes the Rust Foundation. Disponível em: https://blog.mozilla.org/en/mozilla/mozilla-welcomes-the-rust-foundation. Acesso em 2024.
Muhammad Idrees, Naeem Akhter, Furqan-ur-Rehman. Sorting Algorithms – A Comparative Study. International Journal of Computer Science and Information Security, 2016.
Oracle. Java SE at a Glance. Disponível em: https://www.oracle.com/java/technologies/java-se-glance.html. Acesso em 2024.
Python Software Foundation. General Python Overview. Disponível em: https://www.python.org/doc/essays/blurb/. Acesso em 2024.
Sahni, S. Data Structures, Algorithms, and Applications in C++. McGraw-Hill Education. (2011).
Sebesta, R. W., Concepts of Programming Languages (10th ed.). Pearson., 2012.
Weiss, M. A. Data Structures and Algorithm Analysis in C++. Pearson., (2014).
1Graduando do Curso de Sistemas de Informação da Universidade de Araraquara- UNIARA. Araraquara-SP. E-mail: favarettojpfs7@gmail.com
2Orientador. Docente do Curso de Sistemas de Informação da Universidade de Araraquara – UNIARA. Araraquara-SP
3Coorientador. Docente do Curso de Sistemas de Informação da Universidade de Araraquara – UNIARA. Araraquara-SP.