Kombinieren von zwei sortierten Listen in Python

77

Ich habe zwei Listen von Objekten. Jede Liste ist bereits nach einer Eigenschaft des Objekts vom Typ datetime sortiert. Ich möchte die beiden Listen zu einer sortierten Liste zusammenfassen. Ist der beste Weg, nur eine Sortierung durchzuführen, oder gibt es einen intelligenteren Weg, dies in Python zu tun?

Björn Tipling
quelle

Antworten:

116

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 datetimeObjekten 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]
dbr
quelle
5
Endlich eine vernünftige Antwort unter Berücksichtigung des tatsächlichen Benchmarking . :-) --- Auch 1 Zeile anstelle von 15-20 ist sehr zu bevorzugen.
Deestan
19
Das Sortieren einer sehr kurzen Liste, die durch Anhängen von zwei Listen erstellt wurde, ist in der Tat sehr schnell, da der konstante Overhead dominiert. Versuchen Sie dies für Listen mit mehreren Millionen Elementen oder Dateien auf der Festplatte mit mehreren Milliarden Elementen, und Sie werden bald herausfinden, warum das Zusammenführen vorzuziehen ist.
Barry Kelly
5
@Barry: Wenn Sie "mehrere Milliarden Gegenstände" und eine erforderliche Geschwindigkeit haben, ist alles in Python die falsche Antwort.
Deestan
10
@Deestan: Ich bin anderer Meinung - es gibt Zeiten, in denen die Geschwindigkeit von anderen Faktoren dominiert wird. Z.B. Wenn Sie Daten auf der Festplatte sortieren (2 Dateien zusammenführen), dominieren wahrscheinlich die E / A-Zeiten, und die Geschwindigkeit von Python spielt keine große Rolle, nur die Anzahl der von Ihnen ausgeführten Vorgänge (und damit der Algorithmus).
Brian
5
Ernsthaft? Benchmarking einer Sortierfunktion mit einer 10-Eintragsliste?
Seun Osewa
111

Gibt es eine intelligentere Möglichkeit, dies in Python zu tun?

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 .

Sykora
quelle
4
Ich habe einen Link zu heapq.py hinzugefügt. merge()ist als reine Python-Funktion implementiert, sodass es einfach ist, sie auf ältere Python-Versionen zu portieren.
JFS
Obwohl richtig, scheint diese Lösung eine Größenordnung langsamer zu sein als die sorted(l1+l2)Lösung.
Ale
1
@Ale: Das ist nicht ganz überraschend. list.sort(was sortedin 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 theoretisch O(n log n)in diesem Fall ist, ist es viel näher O(n), die Sortierung durchzuführen. Darüber hinaus ist CPython list.sortin C implementiert (Vermeidung von Interpreter-Overhead), während heapq.mergees hauptsächlich in Python implementiert ist, und optimiert für den Fall "viele iterable" auf eine Weise, die den Fall "zwei iterables" verlangsamt.
ShadowRanger
6
Das Verkaufsargument dafür heapq.mergeist, dass weder die Eingaben noch die Ausgaben erforderlich sind list. 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").
ShadowRanger
54

Lange Rede, kurzer Sinn, es sei denn len(l1 + l2) ~ 1000000:

L = l1 + l2
L.sort()

Vergleich von Zusammenführen und Sortieren

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
JF Sebastian
quelle
Sie vergleichen es mit einer Golflösung, nicht mit einer, die tatsächlich versucht, effizient zu sein.
OrangeDog
@OrangeDog Ich verstehe nicht, wovon du sprichst. Der Punkt der Antwort ist, dass das Hinzufügen und Sortieren von zwei Listen für kleine Eingaben schneller sein kann als heapq.merge () aus Python 2.6 (obwohl 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.
JFS
Diese Antwort hat nichts damit zu tun heapq.merge, Sie vergleichen sie mit sortder Code-Golf-Einreichung von jemandem.
OrangeDog
@OrangeDog falsch . merge_26()ist aus dem Python 2.6 Heapq-Modul.
JFS
Sie sind derjenige, der sagte "der Quellcode kann hier gefunden werden" und mit einer Code-Golf-Antwort verknüpft ist. Machen Sie die Leute nicht dafür verantwortlich, dass der Code, der dort zu finden ist, der von Ihnen getestete ist.
OrangeDog
25

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.

Barry Kelly
quelle
Eine Zusammenführungssortierung ist in der Tat die optimale Lösung.
Ignacio Vazquez-Abrams
3
Aber ist es schneller als die integrierte Sortierung von Python?
Akaihola
9
Dies ist einfach eine Zusammenführung, keine Zusammenführungssorte.
Glenn Maynard
2
@akaihola: Wenn len(L1 + L2) < 1000000dann sorted(L1 + L2)schneller ist stackoverflow.com/questions/464342/…
jfs
17

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 .datestattdessen 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.

Brian
quelle
Danke für die Fehlerbehebung. Wäre toll, wenn Sie genau auf den Fehler und Ihre Lösung
hinweisen können
@ghoseb: Ich habe eine kurze Beschreibung als Kommentar zu Ihrem Beitrag gegeben, aber jetzt habe ich die Antwort aktualisiert, um weitere Details zu erhalten - im Wesentlichen ist l.pop () eine O (n) -Operation für Listen. Es kann repariert werden, indem die Position auf eine andere Weise verfolgt wird (alternativ indem man stattdessen vom Schwanz abspringt und am Ende umkehrt)
Brian
Können Sie dieselben Tests vergleichen, aber die Daten vergleichen, die für die Frage erforderlich sind? Ich vermute, dass diese zusätzliche Methode relativ viel Zeit in Anspruch nehmen wird.
Josh Smeaton
Ich würde sagen, der Unterschied liegt in der Tatsache begründet, dass sort () in c / c ++ implementiert und kompiliert ist und unsere merge () interpretiert wird. merge () sollte zu gleichen Bedingungen schneller sein.
Drakosha
Guter Punkt Drakosha. Zeigen Sie, dass Benchmarking in der Tat der einzige Weg ist, dies mit Sicherheit zu wissen.
Josh Smeaton
6

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.

Baishampayan Ghose
quelle
3
Leider ist dies kontraproduktiv - normalerweise wäre das Zusammenführen O (n), aber da Sie links von jeder Liste auftauchen (eine O (n) -Operation), machen Sie es tatsächlich zu einem O (n ** 2) -Prozess - schlimmer als die naive sortiert (l1 + l2)
Brian
@Brian Ich denke tatsächlich, dass diese Lösung die sauberste von allen ist, und ich glaube, Sie haben Recht mit der O (n) -Komplexität, das erste Element aus der Liste zu entfernen. Sie können dieses Problem beseitigen, indem Sie deque aus Sammlungen verwenden, wodurch Sie O (1) erhalten, wenn Sie einen Gegenstand von beiden Seiten platzen lassen. docs.python.org/2/library/collections.html#collections.deque
mohi666
@Brian, head, tail = l[0], l[1:]wird auch O (n ** 2) Komplexität haben?
Nikolay Fominyh
2
@ Brian: Als Alternative zu collections.deque, sondern auch durch die Schaffung gelöst werden könnte l1und l2in umgekehrter Reihenfolge ( l1 = l1[::-1], l2 = l2[::-1]) arbeitet, dann von der rechten Seite eher als die linken, ersetzt if l1[0] <= l2[0]:mit if l1[-1] <= l2[-1]:, ersetzt pop(0)mit pop()und Wechsel sorted_list.extend(l1 if l1 else l2)zusorted_list.extend(reversed(l1 if l1 else l2))
ShadowRanger
4
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.mergeist eine ganz andere Geschichte.

Akaihola
quelle
3

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!).

Darauf würde ich mich jedoch nie verlassen. - Daniel Nadasi

Ich glaube, die Python-Entwickler sind entschlossen, Timsort beizubehalten oder zumindest eine Sorte beizubehalten, die in diesem Fall O (n) ist.

Eine verallgemeinerte Sortierung (dh das Auslassen von Radix-Sortierungen von Domänen mit begrenztem Wert)
kann auf einem seriellen Computer nicht in weniger als O (n log n) durchgeführt werden. - Barry Kelly

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).

FutureNerd
quelle
3
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
krezaeim
quelle
3

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!

timokratia
quelle
2

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
Mungo
quelle
2

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
Pavel Paulau
quelle
2

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:]
ndsvw
quelle
1

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.

Drakosha
quelle
Interessanterweise ist der Python-Sortieralgorithmus sehr gut, sodass die Leistung wahrscheinlich besser als O (n log n) ist, da der Algorithmus häufig Regelmäßigkeiten in den Eingabedaten ausnutzt. Darauf würde ich mich jedoch nie verlassen.
Daniel Nadasi
Eine allgemeine Sortierung (dh das Auslassen von Radix-Sortierungen aus Domänen mit begrenztem Wert) kann auf einem seriellen Computer nicht in weniger als O (n log n) durchgeführt werden.
Barry Kelly
1

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 )
Leon
quelle
pop (0) ist linear, also ist diese Version versehentlich quadratisch
Allen Downey
1
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)
Oussama Ďj Sbaa
quelle
Es ist nicht klar, ob dies eine Antwort auf die Frage ist, geschweige denn, ob dies tatsächlich der Fall ist. Können Sie eine Erklärung geben?
Ben
Sory, aber ich habe nicht verstanden, was du willst!
Oussama Ďj Sbaa
Sie werden feststellen, dass die Antworten mit den höheren Stimmen (und die meisten anderen) einen Text enthalten, der erklärt, was in der Antwort passiert und warum diese Antwort eine Antwort auf die Frage ist.
Ben
weil es zwei Listen in einer sortierten Liste zusammenführt und dies die Antwort auf die Frage ist
Oussama Ďj Sbaa
1

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)
Atul
quelle
0
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.

Josh Smeaton
quelle
Die Zusammenführungssortierung ist definitiv schneller, aber etwas komplizierter, wenn Sie sie selbst implementieren müssen. Ich denke, Python verwendet Quicksort.
Josh Smeaton
3
Nein, Python verwendet Timsort.
Ignacio Vazquez-Abrams
0

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
Daniel
quelle
-1

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]

J_man
quelle
1
OP fragte nicht, wie man Listen hinzufügt und sortiert, sondern ob es eine bessere oder mehr "Python" -Methode in ihrem Kontext gibt.
ForeverZer0