Maximizando a Eficiência da Ordenação
Ordenação Embutida
Sempre que for necessário ordenar uma lista, exceto em alguns casos especiais raros, quase sempre é melhor utilizar uma das duas ferramentas de ordenação altamente otimizadas: a função sorted() ou o método sort(). Ambas são implementadas em C e utilizam o Timsort, um algoritmo híbrido que combina merge sort e insertion sort para maior eficiência.
sorted() é ideal para ordenação geral quando é necessário ordenar qualquer iterável sem alterar os dados originais. Por outro lado, sort() é mais adequado para listas quando a modificação in-place é aceitável.
sorted_list = sorted(some_list) # Returns a new sorted list
some_list.sort() # Sorts the list in place
Ambos os métodos são eficientes, mas list.sort() pode ser apenas ligeiramente mais rápido para listas muito grandes, pois evita a criação de uma nova lista. No entanto, utilize sorted() se for necessário manter a lista original intacta.
Ordenação Parcial com heapq
Para situações em que é necessário apenas os menores ou maiores elementos de um conjunto de dados, ordenar todos os dados é desnecessário. O módulo heapq oferece métodos eficientes como heapq.nsmallest() e heapq.nlargest() para extrair esses elementos sem ordenar completamente o iterável, tornando o processo mais rápido e eficiente em termos de memória.
Vamos comparar o desempenho da função sorted() e da função heapq.nsmallest() para obter os 10 menores números de uma lista:
1234567891011121314151617181920212223import heapq import os decorators = os.system('wget https://staging-content-media-cdn.codefinity.com/courses/8d21890f-d960-4129-bc88-096e24211d53/section_1/chapter_3/decorators.py 2>/dev/null') from decorators import timeit_decorator import random # Generate a large list of random integers numbers = [random.randint(1, 1000000) for _ in range(1000000)] @timeit_decorator(number=10) def partial_sort_heapq(): return heapq.nsmallest(10, numbers) @timeit_decorator(number=10) def partial_sort_sorted(): return sorted(numbers)[:10] # Compare performance heapq_result = partial_sort_heapq() sorted_result = partial_sort_sorted() # Ensure both methods give the same result print(heapq_result == sorted_result)
Como pode ser observado, em nosso exemplo específico, heapq.nsmallest() é aproximadamente 10 vezes mais rápido.
No entanto, se o número de maiores ou menores elementos (n) que você deseja recuperar for próximo ao número total de elementos na lista, heapq geralmente é mais lento do que utilizar a função sorted() ou o método .sort().
Por exemplo, agora vamos recuperar os 100000 menores elementos da lista:
1234567891011121314151617181920212223import heapq import os decorators = os.system('wget https://staging-content-media-cdn.codefinity.com/courses/8d21890f-d960-4129-bc88-096e24211d53/section_1/chapter_3/decorators.py 2>/dev/null') from decorators import timeit_decorator import random # Generate a large list of random integers numbers = [random.randint(1, 1000000) for _ in range(1000000)] @timeit_decorator(number=10) def partial_sort_heapq(): return heapq.nsmallest(100000, numbers) @timeit_decorator(number=10) def partial_sort_sorted(): return sorted(numbers)[:100000] # Compare performance heapq_result = partial_sort_heapq() sorted_result = partial_sort_sorted() # Ensure both methods give the same result print(heapq_result == sorted_result)
A função sorted() neste caso claramente supera o heapq.
1. É necessário ordenar uma lista inteira de números mantendo a lista original intacta. Qual função/método de ordenação deve ser utilizado?
2. Você está analisando um conjunto de dados com 500.000 registros de vendas. Para identificar as 20 transações com maior receita, qual abordagem tende a ser mais rápida e eficiente em termos de memória?
Obrigado pelo seu feedback!
Pergunte à IA
Pergunte à IA
Pergunte o que quiser ou experimente uma das perguntas sugeridas para iniciar nosso bate-papo
Awesome!
Completion rate improved to 7.69Maximizando a Eficiência da Ordenação
Deslize para mostrar o menu
Ordenação Embutida
Sempre que for necessário ordenar uma lista, exceto em alguns casos especiais raros, quase sempre é melhor utilizar uma das duas ferramentas de ordenação altamente otimizadas: a função sorted() ou o método sort(). Ambas são implementadas em C e utilizam o Timsort, um algoritmo híbrido que combina merge sort e insertion sort para maior eficiência.
sorted() é ideal para ordenação geral quando é necessário ordenar qualquer iterável sem alterar os dados originais. Por outro lado, sort() é mais adequado para listas quando a modificação in-place é aceitável.
sorted_list = sorted(some_list) # Returns a new sorted list
some_list.sort() # Sorts the list in place
Ambos os métodos são eficientes, mas list.sort() pode ser apenas ligeiramente mais rápido para listas muito grandes, pois evita a criação de uma nova lista. No entanto, utilize sorted() se for necessário manter a lista original intacta.
Ordenação Parcial com heapq
Para situações em que é necessário apenas os menores ou maiores elementos de um conjunto de dados, ordenar todos os dados é desnecessário. O módulo heapq oferece métodos eficientes como heapq.nsmallest() e heapq.nlargest() para extrair esses elementos sem ordenar completamente o iterável, tornando o processo mais rápido e eficiente em termos de memória.
Vamos comparar o desempenho da função sorted() e da função heapq.nsmallest() para obter os 10 menores números de uma lista:
1234567891011121314151617181920212223import heapq import os decorators = os.system('wget https://staging-content-media-cdn.codefinity.com/courses/8d21890f-d960-4129-bc88-096e24211d53/section_1/chapter_3/decorators.py 2>/dev/null') from decorators import timeit_decorator import random # Generate a large list of random integers numbers = [random.randint(1, 1000000) for _ in range(1000000)] @timeit_decorator(number=10) def partial_sort_heapq(): return heapq.nsmallest(10, numbers) @timeit_decorator(number=10) def partial_sort_sorted(): return sorted(numbers)[:10] # Compare performance heapq_result = partial_sort_heapq() sorted_result = partial_sort_sorted() # Ensure both methods give the same result print(heapq_result == sorted_result)
Como pode ser observado, em nosso exemplo específico, heapq.nsmallest() é aproximadamente 10 vezes mais rápido.
No entanto, se o número de maiores ou menores elementos (n) que você deseja recuperar for próximo ao número total de elementos na lista, heapq geralmente é mais lento do que utilizar a função sorted() ou o método .sort().
Por exemplo, agora vamos recuperar os 100000 menores elementos da lista:
1234567891011121314151617181920212223import heapq import os decorators = os.system('wget https://staging-content-media-cdn.codefinity.com/courses/8d21890f-d960-4129-bc88-096e24211d53/section_1/chapter_3/decorators.py 2>/dev/null') from decorators import timeit_decorator import random # Generate a large list of random integers numbers = [random.randint(1, 1000000) for _ in range(1000000)] @timeit_decorator(number=10) def partial_sort_heapq(): return heapq.nsmallest(100000, numbers) @timeit_decorator(number=10) def partial_sort_sorted(): return sorted(numbers)[:100000] # Compare performance heapq_result = partial_sort_heapq() sorted_result = partial_sort_sorted() # Ensure both methods give the same result print(heapq_result == sorted_result)
A função sorted() neste caso claramente supera o heapq.
1. É necessário ordenar uma lista inteira de números mantendo a lista original intacta. Qual função/método de ordenação deve ser utilizado?
2. Você está analisando um conjunto de dados com 500.000 registros de vendas. Para identificar as 20 transações com maior receita, qual abordagem tende a ser mais rápida e eficiente em termos de memória?
Obrigado pelo seu feedback!
