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.