fondere le liste ordinate in python

Question

Ho un sacco di liste ordinate di oggetti, e una funzione di confronto

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

che cosa fa magic assomigliare? Il mio attuale implementazione è

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

ma che è abbastanza inefficiente. Risposte migliori?

Answer 1

La libreria standard Python offre un metodo per questo: heapq.merge.
Come dice la documentazione, è molto simile all'utilizzo di itertools (ma con più limitazioni); se non si può vivere con queste limitazioni (o se non si utilizza Python 2.6) si può fare qualcosa di simile:

sorted(itertools.chain(args), cmp) 

Tuttavia, penso che abbia la stessa complessità la propria soluzione, anche se utilizzando iteratori dovrebbero dare alcuni buoni ottimizzazione e aumento della velocità.

Answer 2

Non so se sia più veloce qualsiasi, ma si potrebbe semplificare con:

def GetObjKey(a): 
    return a.points 

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

Si potrebbe anche, ovviamente, utilizzare cmp piuttosto che key, se si preferisce.

Answer 3

Utilizzare il modulo bisect. Dalla documentazione: "Questo modulo fornisce supporto per mantenere un elenco in ordine ordinato senza dover ordinare l'elenco dopo ogni inserimento."

import bisect 

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

Answer 4

Invece di usare una lista, è possibile utilizzare un [mucchio] (http://en.wikipedia.org/wiki/Heap_(data_structure).

L'inserimento è O (log (n)), quindi la fusione a, b e c sarà O (n log (n))

In Python, è possibile utilizzare il heapq module

Answer 5

una soluzione line utilizzando allineati:..

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

IMO questa soluzione è molto leggibile

Utilizzando il modulo heapq, potrebbe essere più efficiente, ma non l'ho provato. Non è possibile specificare la funzione cmp/chiave in heapq, quindi è necessario implementare Obj per essere ordinato in modo implicito.

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

Answer 6

Qui si va: un pienamente funzionante merge sort per le liste (adattato da mio genere here):

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) 

chiamare in questo modo:

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

Per buona misura, mi inserirò un paio di modifiche alla classe Obj:

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 

• derivare da oggetto
• Passo self-__init__()
• Fai __cmp__ una funzione di membro
• Aggiungere una funzione str() membro di presentare Obj come stringa

Answer 7

mi piace la risposta di Roberto Liffredo. Non sapevo di heapq.merge(). Hmmmph.

Ecco cosa la soluzione completa assomiglia usando l'esempio di Roberto:

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 

Oppure:

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

Answer 8

ho fatto una domanda simile e ottenuto alcune risposte eccellenti:

• Joining a set of ordered-integer yielding Python iterators

Le migliori soluzioni da questa domanda sono varianti dell'algoritmo merge, che potete leggere qui:

• Wikipedia: Merge Algorithm

Answer 9

Di seguito è un esempio di una funzione che viene eseguito in O (n) confronti .

Si potrebbe rendere più veloce effettuando iteratori eb e incrementandoli.

ho chiamato semplicemente la funzione due volte per unire le 3 liste:

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 

Tuttavia, heapq.merge utilizza un mix di questo metodo e colmo gli elementi attuali di tutte le liste, in modo opportuno eseguire molto meglio