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

Einzeilige Lösung mit sortiert:

def magic(*args):
  return sorted(sum(args,[]), key: lambda x: x.points)

IMO ist diese Lösung sehr gut lesbar.

Mit dem Heapq-Modul könnte es effizienter sein, aber ich habe es nicht getestet. Sie können keine cmp/key-Funktion in heapq angeben, also müssen Sie Obj implementieren, um implizit sortiert zu werden.

import heapq
def magic(*args):
  h = []
  for a in args:
    heapq.heappush(h,a)
  return [i for i in heapq.heappop(h)

Answer 2

Hier ist sie: eine voll funktionierende Mischsortierung für Listen (angepasst an meine Sortierung aquí ):

def merge(*args):
    import copy
    def merge_lists(left, right):
        result = []
        while left and right:
            which_list = (left if left[0] <= right[0] else right)
            result.append(which_list.pop(0))
        return result + left + right
    lists = list(args)
    while len(lists) > 1:
        left, right = copy.copy(lists.pop(0)), copy.copy(lists.pop(0))
        result = merge_lists(left, right)
        lists.append(result)
    return lists.pop(0)

Sagen wir es so:

merged_list = merge(a, b, c)
for item in merged_list:
    print item

Um das Ganze abzurunden, füge ich noch ein paar Änderungen an Ihrer Obj-Klasse hinzu:

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

• Von Objekt ableiten
• Pass self a __init__()
• Machen Sie __cmp__ eine Mitgliedsfunktion
• Hinzufügen einer str() Mitgliedsfunktion zu präsentieren Obj als String

Answer 3

Ich habe eine ähnliche Frage gestellt und einige ausgezeichnete Antworten erhalten:

• Zusammenfügen einer Menge von Python-Iteratoren, die eine ganze Zahl ergeben

Die besten Lösungen für diese Frage sind Varianten des Merge-Algorithmus, über den Sie hier lesen können:

• Wikipedia: Verschmelzungsalgorithmus

Answer 4

Im Folgenden finden Sie ein Beispiel für eine Funktion, die in O(n) Vergleichen ausgeführt wird.

Sie könnten dies schneller machen, indem Sie a und b Iteratoren machen und sie inkrementieren.

Ich habe die Funktion einfach zweimal aufgerufen, um 3 Listen zusammenzuführen:

def zip_sorted(a, b):
    '''
    zips two iterables, assuming they are already sorted
    '''
    i = 0
    j = 0
    result = []
    while i < len(a) and j < len(b):
        if a[i] < b[j]:
            result.append(a[i])
            i += 1
        else:
            result.append(b[j])
            j += 1
    if i < len(a):
        result.extend(a[i:])
    else:
        result.extend(b[j:])
    return result

def genSortedList(num,seed):
    result = [] 
    for i in range(num):
        result.append(i*seed)
    return result

if __name__ == '__main__':
    a = genSortedList(10000,2.0)
    b = genSortedList(6666,3.0)
    c = genSortedList(5000,4.0)
    d = zip_sorted(zip_sorted(a,b),c)
    print d

しかし heapq.merge verwendet eine Mischung aus dieser Methode und dem Anhäufen der aktuellen Elemente aller Listen und sollte daher viel besser funktionieren