Quel est le moyen le plus efficace de combiner des listes triées en Python ?

Combiner efficacement des listes triées en Python

Combiner plusieurs listes triées en une seule liste ordonnée est une tâche courante dans la programmation Python. Pour y parvenir, on peut généralement envisager d’utiliser la fonction intégrée sort(). Cependant, il existe une approche plus efficace connue sous le nom d'algorithme de fusion.

L'algorithme de fusion

L'algorithme de fusion fonctionne en divisant de manière récursive les listes d'entrée en sous-ensembles plus petits, en les triant, puis en fusionnant les résultats. Cette approche a une complexité de calcul de O(n log n), où n est le nombre total d'éléments dans la liste combinée.

La mise en œuvre de l'algorithme de fusion en Python implique les étapes suivantes :

<code class="python">def merge(list1, list2):
    """Merge two sorted lists into a single sorted list."""
    result = []
    while list1 and list2:
        if list1[0] < list2[0]:
            result.append(list1[0])
            del list1[0]
        else:
            result.append(list2[0])
            del list2[0]
    result.extend(list1)
    result.extend(list2)
    return result</code>

Une approche alternative : le module Heapq

Une autre solution efficace pour combiner des listes triées en Python consiste à utiliser la fonction de fusion du module heapq. Cette fonction a été conçue spécifiquement pour fusionner des itérables triés et a une complexité temporelle de O(n), où n est le nombre total d'éléments.

Le code suivant montre comment utiliser la fonction heapq.merge() :

<code class="python">import heapq

list1 = [1, 5, 8, 10, 50]
list2 = [3, 4, 29, 41, 45, 49]
result = list(heapq.merge(list1, list2))
print(result)  # Output: [1, 3, 4, 5, 8, 10, 29, 41, 45, 49, 50]</code>

Conclusion

Qu'il implémente l'algorithme de fusion ou utilise la fonction heapq.merge(), Python fournit des solutions efficaces pour combiner des listes triées avec une complexité de calcul minimale.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!