Die Leute scheinen dies zu komplizieren. Kombinieren Sie einfach die beiden Listen und sortieren Sie sie dann:
>>> 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]
..oder kürzer (und ohne Änderung l1
):
>>> sorted(l1 + l2)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
..einfach! Außerdem werden nur zwei integrierte Funktionen verwendet. Unter der Annahme, dass die Listen eine angemessene Größe haben, sollte dies schneller sein als das Implementieren des Sortierens / Zusammenführens in einer Schleife. Noch wichtiger ist, dass der oben genannte Code viel weniger Code enthält und sehr gut lesbar ist.
Wenn Ihre Listen groß sind (über ein paar hunderttausend, würde ich vermuten), ist es möglicherweise schneller, eine alternative / benutzerdefinierte Sortiermethode zu verwenden, aber es müssen wahrscheinlich zuerst andere Optimierungen vorgenommen werden (z. B. nicht Millionen von datetime
Objekten speichern ).
Mit dem timeit.Timer().repeat()
(das die Funktionen 1000000 Mal wiederholt) habe ich es lose mit der Lösung von Ghoseb verglichen und es sorted(l1+l2)
ist wesentlich schneller:
merge_sorted_lists
dauerte..
[9.7439379692077637, 9.8844599723815918, 9.552299976348877]
sorted(l1+l2)
dauerte..
[2.860386848449707, 2.7589840888977051, 2.7682540416717529]
Dies wurde nicht erwähnt, also werde ich fortfahren - es gibt eine Funktion zum Zusammenführen von stdlib im heapq-Modul von Python 2.6+. Wenn Sie nur Dinge erledigen möchten, ist dies möglicherweise eine bessere Idee. Wenn Sie Ihre eigenen implementieren möchten, ist die Zusammenführung von Zusammenführungssortierung natürlich der richtige Weg.
>>> 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]
Hier ist die Dokumentation .
quelle
merge()
ist als reine Python-Funktion implementiert, sodass es einfach ist, sie auf ältere Python-Versionen zu portieren.sorted(l1+l2)
Lösung.list.sort
(wassorted
in Bezug auf implementiert ist) verwendet TimSort , das optimiert ist, um die vorhandene Reihenfolge (oder umgekehrte Reihenfolge) in der zugrunde liegenden Sequenz zu nutzen. Obwohl es theoretischO(n log n)
in diesem Fall ist, ist es viel näherO(n)
, die Sortierung durchzuführen. Darüber hinaus ist CPythonlist.sort
in C implementiert (Vermeidung von Interpreter-Overhead), währendheapq.merge
es hauptsächlich in Python implementiert ist, und optimiert für den Fall "viele iterable" auf eine Weise, die den Fall "zwei iterables" verlangsamt.heapq.merge
ist, dass weder die Eingaben noch die Ausgaben erforderlich sindlist
. Es kann Iteratoren / Generatoren verbrauchen und erzeugt einen Generator, so dass riesige Ein- / Ausgänge (nicht sofort im RAM gespeichert) kombiniert werden können, ohne dass ein Swap-Thrashing erforderlich ist. Es behandelt auch das Zusammenführen einer beliebigen Anzahl von Eingabe-Iterables mit geringerem Overhead als erwartet (es verwendet einen Heap, um das Zusammenführen zu koordinieren, sodass der Overhead mit dem Protokoll der Anzahl der Iterables skaliert, nicht linear, aber wie erwähnt, das nicht ' t wichtig für den Fall "zwei iterable").Lange Rede, kurzer Sinn, es sei denn
len(l1 + l2) ~ 1000000
:Eine Beschreibung der Abbildung und des Quellcodes finden Sie hier .
Die Abbildung wurde mit dem folgenden Befehl generiert:
$ python make-figures.py --nsublists 2 --maxn=0x100000 -s merge_funcs.merge_26 -s merge_funcs.sort_builtin
quelle
merge()
O (n) in der Zeit O (1) im Raum ist und die Sortierung O (ist) n log n) in der Zeit, und der gesamte Algorithmus ist hier O (n) im Raum) ¶ Der Vergleich hat jetzt nur noch einen historischen Wert.heapq.merge
, Sie vergleichen sie mitsort
der Code-Golf-Einreichung von jemandem.merge_26()
ist aus dem Python 2.6 Heapq-Modul.Dies verschmilzt einfach. Behandeln Sie jede Liste wie einen Stapel und platzieren Sie den kleineren der beiden Stapelköpfe kontinuierlich, indem Sie das Element zur Ergebnisliste hinzufügen, bis einer der Stapel leer ist. Fügen Sie dann alle verbleibenden Elemente zur resultierenden Liste hinzu.
quelle
len(L1 + L2) < 1000000
dannsorted(L1 + L2)
schneller ist stackoverflow.com/questions/464342/…Es gibt einen kleinen Fehler in der Ghoseb- Lösung, der sie zu O (n ** 2) und nicht zu O (n) macht.
Das Problem ist, dass dies funktioniert:
item = l1.pop(0)
Bei verknüpften Listen oder Deques wäre dies eine O (1) -Operation, würde also die Komplexität nicht beeinträchtigen. Da Python-Listen jedoch als Vektoren implementiert sind, kopiert dies den Rest der Elemente von l1 um ein Leerzeichen, eine O (n) -Operation . Da dies bei jedem Durchlauf durch die Liste erfolgt, wird ein O (n) -Algorithmus in einen O (n ** 2) -Algorithmus umgewandelt. Dies kann mithilfe einer Methode korrigiert werden, die die Quelllisten nicht ändert, sondern nur die aktuelle Position verfolgt.
Ich habe versucht, einen korrigierten Algorithmus mit einem einfachen sortierten (l1 + l2) zu vergleichen, wie von dbr vorgeschlagen
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
Ich habe diese mit Listen getestet, die mit generiert wurden
l1 = sorted([random.random() for i in range(NITEMS)]) l2 = sorted([random.random() for i in range(NITEMS)])
Für verschiedene Listengrößen erhalte ich die folgenden Timings (100-mal wiederholen):
# items: 1000 10000 100000 1000000 merge : 0.079 0.798 9.763 109.044 sort : 0.020 0.217 5.948 106.882
Tatsächlich sieht es so aus, als ob dbr richtig ist. Die Verwendung von sorted () ist vorzuziehen, es sei denn, Sie erwarten sehr große Listen, obwohl die algorithmische Komplexität schlechter ist. Die Gewinnschwelle liegt bei rund einer Million Artikeln in jeder Quellenliste (insgesamt 2 Millionen).
Ein Vorteil des Zusammenführungsansatzes besteht jedoch darin, dass das Umschreiben als Generator trivial ist, wodurch wesentlich weniger Speicher benötigt wird (keine Zwischenliste erforderlich).
[Bearbeiten] Ich habe dies mit einer Situation wiederholt, die näher an der Frage liegt - unter Verwendung einer Liste von Objekten, die ein Feld "
date
" enthalten, das ein Datum / Uhrzeit-Objekt ist. Der obige Algorithmus wurde geändert, um ihn.date
stattdessen zu vergleichen , und die Sortiermethode wurde geändert in:return sorted(l1 + l2, key=operator.attrgetter('date'))
Das ändert die Dinge ein bisschen. Da der Vergleich teurer ist, wird die Anzahl, die wir durchführen, im Verhältnis zur zeitkonstanten Geschwindigkeit der Implementierung wichtiger. Dies bedeutet, dass das Zusammenführen verlorenen Boden ausmacht und stattdessen die sort () -Methode bei 100.000 Elementen übertrifft. Ein Vergleich anhand eines noch komplexeren Objekts (z. B. große Zeichenfolgen oder Listen) würde dieses Gleichgewicht wahrscheinlich noch mehr verschieben.
# 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]: Hinweis: Ich habe tatsächlich nur 10 Wiederholungen für 1.000.000 Elemente durchgeführt und entsprechend skaliert, da es ziemlich langsam war.
quelle
Dies ist das einfache Zusammenführen von zwei sortierten Listen. Schauen Sie sich den folgenden Beispielcode an, in dem zwei sortierte Listen von Ganzzahlen zusammengeführt werden.
#!/usr/bin/env python ## merge.py -- Merge two sorted lists -*- Python -*- ## Time-stamp: "2009-01-21 14:02:57 ghoseb" l1 = [1, 3, 4, 7] l2 = [0, 2, 5, 6, 8, 9] def merge_sorted_lists(l1, l2): """Merge sort two sorted lists Arguments: - `l1`: First sorted list - `l2`: Second sorted list """ sorted_list = [] # Copy both the args to make sure the original lists are not # modified l1 = l1[:] l2 = l2[:] while (l1 and l2): if (l1[0] <= l2[0]): # Compare both heads item = l1.pop(0) # Pop from the head sorted_list.append(item) else: item = l2.pop(0) sorted_list.append(item) # Add the remaining of the lists sorted_list.extend(l1 if l1 else l2) return sorted_list if __name__ == '__main__': print merge_sorted_lists(l1, l2)
Dies sollte mit datetime-Objekten gut funktionieren. Hoffe das hilft.
quelle
head, tail = l[0], l[1:]
wird auch O (n ** 2) Komplexität haben?collections.deque
, sondern auch durch die Schaffung gelöst werden könntel1
undl2
in umgekehrter Reihenfolge (l1 = l1[::-1]
,l2 = l2[::-1]
) arbeitet, dann von der rechten Seite eher als die linken, ersetztif l1[0] <= l2[0]:
mitif l1[-1] <= l2[-1]:
, ersetztpop(0)
mitpop()
und Wechselsorted_list.extend(l1 if l1 else l2)
zusorted_list.extend(reversed(l1 if l1 else l2))
from datetime import datetime from itertools import chain from operator import attrgetter class DT: def __init__(self, dt): self.dt = dt list1 = [DT(datetime(2008, 12, 5, 2)), DT(datetime(2009, 1, 1, 13)), DT(datetime(2009, 1, 3, 5))] list2 = [DT(datetime(2008, 12, 31, 23)), DT(datetime(2009, 1, 2, 12)), DT(datetime(2009, 1, 4, 15))] list3 = sorted(chain(list1, list2), key=attrgetter('dt')) for item in list3: print item.dt
Die Ausgabe:
2008-12-05 02:00:00 2008-12-31 23:00:00 2009-01-01 13:00:00 2009-01-02 12:00:00 2009-01-03 05:00:00 2009-01-04 15:00:00
Ich wette, dies ist schneller als jeder der ausgefallenen Pure-Python-Merge-Algorithmen, selbst für große Datenmengen. Python 2.6
heapq.merge
ist eine ganz andere Geschichte.quelle
Die Sortierimplementierung "timsort" von Python ist speziell für Listen optimiert, die geordnete Abschnitte enthalten. Außerdem ist es in C geschrieben.
http://bugs.python.org/file4451/timsort.txt
http://en.wikipedia.org/wiki/Timsort
Wie bereits erwähnt, wird die Vergleichsfunktion möglicherweise mehrmals um einen konstanten Faktor aufgerufen (in vielen Fällen jedoch mehrmals in kürzerer Zeit!).
Ich glaube, die Python-Entwickler sind entschlossen, Timsort beizubehalten oder zumindest eine Sorte beizubehalten, die in diesem Fall O (n) ist.
Richtig, das Sortieren im allgemeinen Fall kann nicht schneller sein. Da O () eine Obergrenze ist, widerspricht Timsort O (n log n) bei beliebiger Eingabe nicht dem O (n) bei sortierter (L1) + sortierter (L2).
quelle
def merge_sort(a,b): pa = 0 pb = 0 result = [] while pa < len(a) and pb < len(b): if a[pa] <= b[pb]: result.append(a[pa]) pa += 1 else: result.append(b[pb]) pb += 1 remained = a[pa:] + b[pb:] result.extend(remained) return result
quelle
Eine Implementierung des Zusammenführungsschritts in Merge Sort, die beide Listen durchläuft:
def merge_lists(L1, L2): """ L1, L2: sorted lists of numbers, one of them could be empty. returns a merged and sorted list of L1 and L2. """ # When one of them is an empty list, returns the other list if not L1: return L2 elif not L2: return L1 result = [] i = 0 j = 0 for k in range(len(L1) + len(L2)): if L1[i] <= L2[j]: result.append(L1[i]) if i < len(L1) - 1: i += 1 else: result += L2[j:] # When the last element in L1 is reached, break # append the rest of L2 to result. else: result.append(L2[j]) if j < len(L2) - 1: j += 1 else: result += L1[i:] # When the last element in L2 is reached, break # append the rest of L1 to result. return result L1 = [1, 3, 5] L2 = [2, 4, 6, 8] merge_lists(L1, L2) # Should return [1, 2, 3, 4, 5, 6, 8] merge_lists([], L1) # Should return [1, 3, 5]
Ich lerne immer noch über Algorithmen. Bitte lassen Sie mich wissen, ob der Code in irgendeiner Hinsicht verbessert werden könnte. Ihr Feedback wird geschätzt, danke!
quelle
Verwenden Sie den Schritt 'Zusammenführen' der Zusammenführungssortierung, er wird in O (n) Zeit ausgeführt.
Aus Wikipedia (Pseudocode):
function merge(left,right) var list result while length(left) > 0 and length(right) > 0 if first(left) ≤ first(right) append first(left) to result left = rest(left) else append first(right) to result right = rest(right) end while while length(left) > 0 append left to result while length(right) > 0 append right to result return result
quelle
Die rekursive Implementierung ist unten. Die durchschnittliche Leistung beträgt O (n).
def merge_sorted_lists(A, B, sorted_list = None): if sorted_list == None: sorted_list = [] slice_index = 0 for element in A: if element <= B[0]: sorted_list.append(element) slice_index += 1 else: return merge_sorted_lists(B, A[slice_index:], sorted_list) return sorted_list + B
oder Generator mit verbesserter Raumkomplexität:
def merge_sorted_lists_as_generator(A, B): slice_index = 0 for element in A: if element <= B[0]: slice_index += 1 yield element else: for sorted_element in merge_sorted_lists_as_generator(B, A[slice_index:]): yield sorted_element return for element in B: yield element
quelle
Dies ist meine Lösung in linearer Zeit ohne Bearbeitung von l1 und l2:
def merge(l1, l2): m, m2 = len(l1), len(l2) newList = [] l, r = 0, 0 while l < m and r < m2: if l1[l] < l2[r]: newList.append(l1[l]) l += 1 else: newList.append(l2[r]) r += 1 return newList + l1[l:] + l2[r:]
quelle
Nun, der naive Ansatz (kombiniere 2 Listen zu einer großen und sortiere) wird O (N * log (N)) Komplexität sein. Wenn Sie dagegen die Zusammenführung manuell implementieren (ich kenne keinen fertigen Code in Python-Bibliotheken dafür, aber ich bin kein Experte), ist die Komplexität O (N), was deutlich schneller ist. Die Idee wird sehr gut in der Post von Barry Kelly beschrieben.
quelle
Wenn Sie dies auf eine Weise tun möchten, die dem Lernen der Vorgänge in der Iteration besser entspricht, versuchen Sie dies
def merge_arrays(a, b): l= [] while len(a) > 0 and len(b)>0: if a[0] < b[0]: l.append(a.pop(0)) else:l.append(b.pop(0)) l.extend(a+b) print( l )
quelle
import random n=int(input("Enter size of table 1")); #size of list 1 m=int(input("Enter size of table 2")); # size of list 2 tb1=[random.randrange(1,101,1) for _ in range(n)] # filling the list with random tb2=[random.randrange(1,101,1) for _ in range(m)] # numbers between 1 and 100 tb1.sort(); #sort the list 1 tb2.sort(); # sort the list 2 fus=[]; # creat an empty list print(tb1); # print the list 1 print('------------------------------------'); print(tb2); # print the list 2 print('------------------------------------'); i=0;j=0; # varialbles to cross the list while(i<n and j<m): if(tb1[i]<tb2[j]): fus.append(tb1[i]); i+=1; else: fus.append(tb2[j]); j+=1; if(i<n): fus+=tb1[i:n]; if(j<m): fus+=tb2[j:m]; print(fus); # this code is used to merge two sorted lists in one sorted list (FUS) without #sorting the (FUS)
quelle
Habe den Zusammenführungsschritt der Zusammenführungssorte verwendet. Aber ich habe Generatoren benutzt . Zeitkomplexität O (n)
def merge(lst1,lst2): len1=len(lst1) len2=len(lst2) i,j=0,0 while(i<len1 and j<len2): if(lst1[i]<lst2[j]): yield lst1[i] i+=1 else: yield lst2[j] j+=1 if(i==len1): while(j<len2): yield lst2[j] j+=1 elif(j==len2): while(i<len1): yield lst1[i] i+=1 l1=[1,3,5,7] l2=[2,4,6,8,9] mergelst=(val for val in merge(l1,l2)) print(*mergelst)
quelle
def compareDate(obj1, obj2): if obj1.getDate() < obj2.getDate(): return -1 elif obj1.getDate() > obj2.getDate(): return 1 else: return 0 list = list1 + list2 list.sort(compareDate)
Sortiert die Liste an Ort und Stelle. Definieren Sie Ihre eigene Funktion zum Vergleichen zweier Objekte und übergeben Sie diese Funktion an die integrierte Sortierfunktion.
Verwenden Sie KEINE Blasensortierung, sie hat eine schreckliche Leistung.
quelle
Dieser Code hat die Zeitkomplexität O (n) und kann Listen eines beliebigen Datentyps zusammenführen, wenn eine Quantifizierungsfunktion als Parameter gegeben ist
func
. Es wird eine neue zusammengeführte Liste erstellt und keine der als Argumente übergebenen Listen geändert.def merge_sorted_lists(listA,listB,func): merged = list() iA = 0 iB = 0 while True: hasA = iA < len(listA) hasB = iB < len(listB) if not hasA and not hasB: break valA = None if not hasA else listA[iA] valB = None if not hasB else listB[iB] a = None if not hasA else func(valA) b = None if not hasB else func(valB) if (not hasB or a<b) and hasA: merged.append(valA) iA += 1 elif hasB: merged.append(valB) iB += 1 return merged
quelle
Hoffe das hilft. Ziemlich einfach und unkompliziert:
l1 = [1, 3, 4, 7]
l2 = [0, 2, 5, 6, 8, 9]
l3 = l1 + l2
l3.sort ()
drucken (l3)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
quelle