Aprenda Maximizando a Eficiência da Ordenação | Aperfeiçoando o Desempenho com Ferramentas Integradas

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:


              1234567891011121314151617181920212223
            
import heapq
import os
decorators = os.system('wget https://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:


              1234567891011121314151617181920212223
            
import heapq
import os
decorators = os.system('wget https://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?

Tudo estava claro?

Obrigado pelo seu feedback!

Seção 3. Capítulo 3

Pergunte à IA

Pergunte o que quiser ou experimente uma das perguntas sugeridas para iniciar nosso bate-papo

Seção 3. Capítulo 3