81 votes

Combinaison de deux listes triées en Python

J'ai deux listes d'objets. Chaque liste est déjà triée par une propriété de l'objet qui est du type datetime. Je voudrais combiner les deux listes en une seule liste triée. La meilleure solution consiste-t-elle à effectuer un tri ou existe-t-il un moyen plus intelligent de le faire en Python ?

123voto

sykora Points 30290

Existe-t-il une façon plus intelligente de faire cela en Python ?

Cela n'a pas été mentionné, alors je vais le faire - il y a un fusionner une fonction stdlib dans le module heapq de python 2.6+. Si tout ce que vous cherchez à faire est de faire avancer les choses, cela pourrait être une meilleure idée. Bien sûr, si vous voulez mettre en œuvre votre propre méthode, la fusion de merge-sort est la meilleure solution.

>>> list1 = [1, 5, 8, 10, 50]
>>> list2 = [3, 4, 29, 41, 45, 49]
>>> from heapq import merge
>>> list(merge(list1, list2))
[1, 3, 4, 5, 8, 10, 29, 41, 45, 49, 50]

Voici la documentation .

5 votes

J'ai ajouté le lien vers heapq.py. merge() est implémenté comme une fonction purement python, il est donc facile de le porter vers des versions plus anciennes de Python.

1 votes

Bien que correcte, cette solution semble être plus lente d'un ordre de grandeur que la solution sorted(l1+l2) solution.

2 votes

@Ale : Ce n'est pas vraiment surprenant. list.sort (qui sorted est mis en œuvre en termes de) utilisations TimSort qui est optimisé pour tirer parti de l'ordre existant (ou de l'ordre inverse) dans la séquence sous-jacente. O(n log n) dans ce cas, c'est beaucoup plus proche de O(n) pour effectuer le tri. Au-delà de cela, la fonction list.sort est implémenté en C (ce qui évite la surcharge de l'interpréteur), alors que heapq.merge est principalement implémenté en Python, et optimise le cas des "nombreux itérables" d'une manière qui ralentit le cas des "deux itérables".

120voto

dbr Points 66401

Les gens semblent trop compliquer les choses Il suffit de combiner les deux listes, puis de les trier :

>>> l1 = [1, 3, 4, 7]
>>> l2 = [0, 2, 5, 6, 8, 9]
>>> l1.extend(l2)
>>> sorted(l1)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

ou plus court (et sans modifier l1 ):

>>> sorted(l1 + l2)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

facile ! De plus, il n'utilise que deux fonctions intégrées, donc en supposant que les listes sont d'une taille raisonnable, cela devrait être plus rapide que d'implémenter le tri/fusion dans une boucle. Plus important encore, ce qui précède est beaucoup moins de code, et très lisible.

Si vos listes sont volumineuses (plus de quelques centaines de milliers, je suppose), il peut être plus rapide d'utiliser une méthode de tri alternative/personnalisée, mais il y a probablement d'autres optimisations à faire d'abord (par exemple ne pas stocker des millions de datetime objets)

Utilisation de la timeit.Timer().repeat() (qui répète les fonctions 1000000 fois), je l'ai vaguement étalonné par rapport à de ghoseb solution, et sorted(l1+l2) est nettement plus rapide :

merge_sorted_lists pris

[9.7439379692077637, 9.8844599723815918, 9.552299976348877]

sorted(l1+l2) pris

[2.860386848449707, 2.7589840888977051, 2.7682540416717529]

0 votes

Ceci est principalement dû à un défaut dans la solution de ghoseb - elle est en fait O(n**2), et sera donc moins performante que le tri O(n lg(n)). Une fusion O(n) sera probablement plus rapide que le tri, au moins pour une liste d'entrée suffisamment grande (le tri pourrait bien être meilleur pour les listes courtes).

5 votes

Enfin une réponse sensée, prenant en compte les benchmarking en compte :-) --- De plus, il est préférable d'avoir une ligne à maintenir au lieu de 15-20.

24 votes

Le tri d'une liste très courte créée par l'addition de deux listes sera en effet très rapide, car les frais généraux constants seront dominants. Essayez de faire cela pour des listes de plusieurs millions d'éléments, ou des fichiers sur disque de plusieurs milliards d'éléments, et vous comprendrez vite pourquoi la fusion est préférable.

54voto

J.F. Sebastian Points 102961

Pour faire court, à moins que len(l1 + l2) ~ 1000000 utiliser :

L = l1 + l2
L.sort()

merge vs. sort comparison

La description de la figure et le code source peuvent être trouvés aquí .

La figure a été générée par la commande suivante :

$ python make-figures.py --nsublists 2 --maxn=0x100000 -s merge_funcs.merge_26 -s merge_funcs.sort_builtin

0 votes

Vous la comparez à une solution de golf, et non à une solution qui cherche réellement à être efficace.

0 votes

@OrangeDog Je ne comprends pas ce dont vous parlez. Le point de la réponse est que l'addition de deux listes et leur tri peut être plus rapide pour une petite entrée que heapq.merge() de Python 2.6 (malgré merge() étant O(n) en temps, O(1) en espace et le tri est O(n log n) en temps, et l'algorithme entier est O(n) en espace ici)¶ La comparaison n'a plus qu'une valeur historique.

0 votes

Cette réponse n'a rien à voir avec heapq.merge vous comparez sort contre la soumission d'un code-golf.

29voto

Barry Kelly Points 30330

Il s'agit simplement d'une fusion. Traitez chaque liste comme s'il s'agissait d'une pile, et ouvrez continuellement la plus petite des deux têtes de pile, en ajoutant l'élément à la liste résultante, jusqu'à ce qu'une des piles soit vide. Ensuite, ajoutez tous les éléments restants à la liste résultante.

res = []
while l1 and l2:
    if l1[0] < l2[0]:
        res.append(l1.pop(0))
    else:
        res.append(l2.pop(0))

res += l1
res += l2

0 votes

Un tri par fusion est en effet la solution optimale.

3 votes

Mais est-ce plus rapide que d'utiliser le tri intégré de Python ?

17voto

Brian Points 48423

Il y a un léger défaut dans de ghoseb ce qui la rend O(n**2), plutôt que O(n).
Le problème est qu'il s'agit d'un spectacle :

item = l1.pop(0)

Avec des listes liées ou des déques, ce serait une opération O(1), donc n'affecterait pas la complexité, mais comme les listes python sont implémentées comme des vecteurs, cela copie le reste des éléments de l1 un espace à gauche, une opération O(n). Comme cela est fait à chaque passage dans la liste, cela transforme un algorithme O(n) en un algorithme O(n**2). Ceci peut être corrigé en utilisant une méthode qui ne modifie pas les listes sources, mais qui garde simplement la trace de la position actuelle.

J'ai essayé d'évaluer un algorithme corrigé par rapport à un simple sorted(l1+l2) comme suggéré par dbr

def merge(l1,l2):
    if not l1:  return list(l2)
    if not l2:  return list(l1)

    # l2 will contain last element.
    if l1[-1] > l2[-1]:
        l1,l2 = l2,l1

    it = iter(l2)
    y = it.next()
    result = []

    for x in l1:
        while y < x:
            result.append(y)
            y = it.next()
        result.append(x)
    result.append(y)
    result.extend(it)
    return result

Je les ai testées avec des listes générées avec

l1 = sorted([random.random() for i in range(NITEMS)])
l2 = sorted([random.random() for i in range(NITEMS)])

Pour différentes tailles de liste, j'obtiens les temps suivants (en répétant 100 fois) :

# items:  1000   10000 100000 1000000
merge  :  0.079  0.798 9.763  109.044 
sort   :  0.020  0.217 5.948  106.882

Donc, en fait, il semble que dbr ait raison, l'utilisation de sorted() est préférable à moins que vous vous attendiez à des listes très grandes, bien qu'elle ait une complexité algorithmique pire. Le point d'équilibre se situe à environ un million d'éléments dans chaque liste source (2 millions au total).

L'un des avantages de l'approche par fusion est qu'il est trivial de la réécrire comme un générateur, qui utilisera beaucoup moins de mémoire (pas besoin d'une liste intermédiaire).

[Edit] J'ai réessayé avec une situation plus proche de la question - en utilisant une liste d'objets contenant un champ " date "qui est un objet de type datetime. L'algorithme ci-dessus a été modifié pour comparer avec .date à la place, et la méthode de tri a été modifiée en :

return sorted(l1 + l2, key=operator.attrgetter('date'))

Cela change un peu les choses. La comparaison étant plus coûteuse, le nombre d'opérations que nous effectuons devient plus important, par rapport à la vitesse de l'implémentation en temps constant. Cela signifie que la fusion rattrape le terrain perdu, dépassant la méthode sort() à 100 000 éléments plutôt. Une comparaison basée sur un objet encore plus complexe (de grandes chaînes de caractères ou des listes, par exemple) modifierait probablement encore plus cet équilibre.

# items:  1000   10000 100000  1000000[1]
merge  :  0.161  2.034 23.370  253.68
sort   :  0.111  1.523 25.223  313.20

[1] : Note : Je n'ai fait que 10 répétitions pour 1 000 000 d'objets et j'ai augmenté l'échelle en conséquence car c'était assez lent.

0 votes

Merci pour la réparation. Ce serait bien si vous pouviez indiquer exactement le défaut et votre solution :)

0 votes

@ghoseb : J'ai donné une brève description en commentaire de votre post, mais j'ai maintenant mis à jour la réponse pour donner plus de détails - essentiellement l.pop() est une opération O(n) pour les listes. Il est possible d'y remédier en suivant la position d'une autre manière (ou bien en faisant le pop à partir de la queue, et en inversant à la fin).

0 votes

Pouvez-vous évaluer ces mêmes tests mais en comparant les dates comme le demande la question ? Je suppose que cette méthode supplémentaire prendra relativement beaucoup de temps.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X