Contenu du cours
Techniques d'Optimisation en Python
Techniques d'Optimisation en Python
Maximiser l'Efficacité du Tri
Tri intégré
Chaque fois que vous avez besoin de trier une liste, sauf dans de rares cas particuliers, il est presque toujours préférable d'utiliser l'un de ses 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 qui combine le tri par fusion et le tri par insertion pour plus d'efficacité.
sorted() est idéal pour le tri à usage général lorsque vous devez trier n'importe quel itérable sans modifier les données d'origine. D'autre part, sort() est mieux adapté aux listes lorsque la modification sur place est acceptable.
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, utilisez sorted() si vous devez conserver la liste d'origine intacte.
Tri partiel avec heapq
Dans les cas où vous n'avez besoin que des plus petits ou plus grands éléments d'un ensemble de données, trier l'ensemble des données est inutile. Le module heapq fournit des méthodes efficaces comme heapq.nsmallest() et heapq.nlargest() pour extraire ces éléments sans trier complètement l'itérable, ce qui le rend plus rapide et plus économe en mémoire.
Comparons les performances de la fonction sorted() et de la fonction heapq.nsmallest() pour récupérer les 10 plus petits nombres d'une liste :
import 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 voir, dans notre exemple particulier, heapq.nsmallest() est environ 10 fois plus rapide.
Cependant, si le nombre des plus grands ou plus petits éléments (n) que vous souhaitez récupérer est proche du nombre total d'éléments dans la liste, heapq est souvent plus lent que l'utilisation de la fonction sorted() ou de la méthode .sort().
Par exemple, récupérons maintenant 100000 plus petits éléments de la liste :
import 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() dans ce cas surpasse clairement heapq.
1. Vous devez trier une liste entière de nombres tout en gardant la liste originale intacte. Quelle fonction/méthode de tri devriez-vous utiliser ?
2. Vous examinez 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 est susceptible d'être plus rapide et plus économe en mémoire ?
Merci pour vos commentaires !
