Sortierte Listen in Python zusammenführen

Question

Ich habe eine Reihe von sortierten Listen von Objekten, und eine Vergleichsfunktion

class Obj :
    def __init__(p) :
        self.points = p
def cmp(a, b) :
    return a.points < b.points

a = [Obj(1), Obj(3), Obj(8), ...]
b = [Obj(1), Obj(2), Obj(3), ...]
c = [Obj(100), Obj(300), Obj(800), ...]

result = magic(a, b, c)
assert result == [Obj(1), Obj(1), Obj(2), Obj(3), Obj(3), Obj(8), ...]

Was bedeutet magic aussehen? Meine derzeitige Implementierung ist

def magic(*args) :
    r = []
    for a in args : r += a
    return sorted(r, cmp)

aber das ist ziemlich ineffizient. Bessere Antworten?

Answer 1

Die Python-Standardbibliothek bietet dafür eine Methode: heapq.merge .
Wie die Dokumentation sagt, ist es sehr ähnlich wie die Verwendung von itertools (aber mit mehr Einschränkungen); wenn Sie mit diesen Einschränkungen nicht leben können (oder wenn Sie Python 2.6 nicht verwenden), können Sie etwas wie dieses tun:

sorted(itertools.chain(args), cmp)

Ich denke jedoch, dass es die gleiche Komplexität wie Ihre eigene Lösung hat, obwohl die Verwendung von Iteratoren einige ziemlich gute Optimierungen und Geschwindigkeitssteigerungen ermöglichen sollte.

Answer 2

Mir gefällt die Antwort von Roberto Liffredo. Ich wusste nichts von heapq.merge(). Hmmm.

So sieht die vollständige Lösung nach Robertos Beispiel aus:

class Obj(object):
    def __init__(self, p) :
        self.points = p
    def __cmp__(self, b) :
        return cmp(self.points, b.points)
    def __str__(self):
        return "%d" % self.points

a = [Obj(1), Obj(3), Obj(8)]
b = [Obj(1), Obj(2), Obj(3)]
c = [Obj(100), Obj(300), Obj(800)]

import heapq

sorted = [item for item in heapq.merge(a,b,c)]
for item in sorted:
    print item

Oder:

for item in heapq.merge(a,b,c):
    print item

Answer 3

Verwenden Sie die bisect Modul. Aus der Dokumentation: "Dieses Modul bietet Unterstützung für die Verwaltung einer Liste in sortierter Reihenfolge, ohne dass die Liste nach jedem Einfügen sortiert werden muss."

import bisect

def magic(*args):
    r = []
    for a in args:
        for i in a:
            bisect.insort(r, i)
    return r

Answer 4

Statt einer Liste können Sie auch einen [heap]( http://en.wikipedia.org/wiki/Heap_(Daten_Struktur) .

Das Einfügen ist O(log(n)), das Zusammenführen von a, b und c ist also O(n log(n))

In Python können Sie die heapq Modul .

Answer 5

Ich weiß nicht, ob es schneller ginge, aber man könnte es mit vereinfachen:

def GetObjKey(a):
    return a.points

return sorted(a + b + c, key=GetObjKey)

Sie können natürlich auch Folgendes verwenden cmp statt key wenn Sie es vorziehen.