Maximisation de l'Efficacité du Tri
Tri intégrée
Chaque fois qu'il est nécessaire de trier une liste, sauf dans de rares cas particuliers, il est presque toujours préférable d'utiliser l'un des deux outils de tri hautement optimisés : la fonction sorted() ou la méthode sort(). Les deux sont implémentés en C et utilisent Timsort, un algorithme hybride combinant le tri fusion et le tri par insertion pour une efficacité accrue.
sorted() est idéal pour un tri général lorsque l'on souhaite trier n'importe quel itérable sans modifier les données d'origine. À l'inverse, sort() convient mieux aux listes lorsque la modification sur place est acceptable.
sorted_list = sorted(some_list) # Returns a new sorted list
some_list.sort() # Sorts the list in place
Les deux méthodes sont efficaces, mais list.sort() peut être légèrement plus rapide pour les très grandes listes car elle évite de créer une nouvelle liste. Cependant, il est recommandé d'utiliser sorted() si l'on souhaite conserver la liste d'origine intacte.
Tri partiel avec heapq
Dans les cas où seuls les plus petits ou plus grands éléments d'un ensemble de données sont nécessaires, il n'est pas utile de trier l'ensemble des données. Le module heapq propose des méthodes efficaces telles que heapq.nsmallest() et heapq.nlargest() pour extraire ces éléments sans trier complètement l'itérable, ce qui est plus rapide et plus économe en mémoire.
Comparaison des performances entre la fonction sorted() et la fonction heapq.nsmallest() pour récupérer les 10 plus petits nombres d'une liste :
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)
Comme vous pouvez le constater, dans notre exemple particulier, heapq.nsmallest() est environ 10 fois plus rapide.
Cependant, si le nombre d’éléments les plus grands ou les plus petits (n) que vous souhaitez extraire est proche du nombre total d’éléments dans la liste, heapq est souvent plus lent que la fonction sorted() ou la méthode .sort().
Par exemple, extrayons maintenant les 100000 plus petits éléments de la liste :
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)
La fonction sorted() surpasse clairement heapq dans ce cas.
1. Vous devez trier une liste entière de nombres tout en conservant la liste d'origine intacte. Quelle fonction/méthode de tri devez-vous utiliser ?
2. Vous analysez un ensemble de données de 500 000 enregistrements de ventes. Pour identifier les 20 transactions générant le plus de revenus, quelle approche sera probablement la plus rapide et la plus économe en mémoire ?
Merci pour vos commentaires !
Demandez à l'IA
Demandez à l'IA
Posez n'importe quelle question ou essayez l'une des questions suggérées pour commencer notre discussion
Can you explain why heapq is faster for small n but slower for large n?
When should I use heapq over sorted() in practice?
Are there other efficient ways to partially sort data in Python?
Génial!
Completion taux amélioré à 7.69Maximisation de l'Efficacité du Tri
Glissez pour afficher le menu
Tri intégrée
Chaque fois qu'il est nécessaire de trier une liste, sauf dans de rares cas particuliers, il est presque toujours préférable d'utiliser l'un des deux outils de tri hautement optimisés : la fonction sorted() ou la méthode sort(). Les deux sont implémentés en C et utilisent Timsort, un algorithme hybride combinant le tri fusion et le tri par insertion pour une efficacité accrue.
sorted() est idéal pour un tri général lorsque l'on souhaite trier n'importe quel itérable sans modifier les données d'origine. À l'inverse, sort() convient mieux aux listes lorsque la modification sur place est acceptable.
sorted_list = sorted(some_list) # Returns a new sorted list
some_list.sort() # Sorts the list in place
Les deux méthodes sont efficaces, mais list.sort() peut être légèrement plus rapide pour les très grandes listes car elle évite de créer une nouvelle liste. Cependant, il est recommandé d'utiliser sorted() si l'on souhaite conserver la liste d'origine intacte.
Tri partiel avec heapq
Dans les cas où seuls les plus petits ou plus grands éléments d'un ensemble de données sont nécessaires, il n'est pas utile de trier l'ensemble des données. Le module heapq propose des méthodes efficaces telles que heapq.nsmallest() et heapq.nlargest() pour extraire ces éléments sans trier complètement l'itérable, ce qui est plus rapide et plus économe en mémoire.
Comparaison des performances entre la fonction sorted() et la fonction heapq.nsmallest() pour récupérer les 10 plus petits nombres d'une liste :
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)
Comme vous pouvez le constater, dans notre exemple particulier, heapq.nsmallest() est environ 10 fois plus rapide.
Cependant, si le nombre d’éléments les plus grands ou les plus petits (n) que vous souhaitez extraire est proche du nombre total d’éléments dans la liste, heapq est souvent plus lent que la fonction sorted() ou la méthode .sort().
Par exemple, extrayons maintenant les 100000 plus petits éléments de la liste :
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)
La fonction sorted() surpasse clairement heapq dans ce cas.
1. Vous devez trier une liste entière de nombres tout en conservant la liste d'origine intacte. Quelle fonction/méthode de tri devez-vous utiliser ?
2. Vous analysez un ensemble de données de 500 000 enregistrements de ventes. Pour identifier les 20 transactions générant le plus de revenus, quelle approche sera probablement la plus rapide et la plus économe en mémoire ?
Merci pour vos commentaires !
