Combinar listas ordenadas en Python

Question

que tienen un montón de listas ordenadas de objetos, y una función de comparación

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

lo que hace magic parece? Mi implementación actual es

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

pero eso es bastante ineficiente. Mejores respuestas?

Answer 1

La biblioteca estándar de Python ofrece un método para ello: heapq.merge. Como dice la documentación, es muy similar al uso de itertools (pero con más limitaciones); si no se puede vivir con esas limitaciones (o si usted no usa Python 2.6) se puede hacer algo como esto:

sorted(itertools.chain(args), cmp) 

Sin embargo, creo que tiene la misma complejidad que su propia solución, aunque utilizando iteradores deben dar algunos bastante buena optimización y aumento de velocidad.

Answer 2

No sé si sería mayor rapidez, pero se puede simplificar con:

def GetObjKey(a): 
    return a.points 

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

Se podría también, por supuesto, utilizar en lugar de cmpkey si lo prefiere.

Answer 3

Utilice el módulo bisect. De la documentación: "Este módulo proporciona soporte para mantener una lista ordenada sin tener que ordenar la lista después de cada inserción".

import bisect 

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

Answer 4

En lugar de utilizar una lista, se puede utilizar un [montón] (http://en.wikipedia.org/wiki/Heap_(data_structure).

La inserción es O (log (n)), por lo que la fusión de a, b y c será O (n log (n))

En Python, se puede utilizar el heapq module

Answer 5

Una solución línea utilizando ordenadas:..

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

OMI esta solución es muy fácil de leer

Usando el módulo heapq, podría ser más eficiente, pero no lo he probado. No puede especificar la función cmp/key en heapq, por lo que debe implementar Obj para que esté implícitamente ordenada.

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

Answer 6

Aquí van: una especie de combinación en pleno funcionamiento para las listas (una adaptación de mi especie 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) 

llamada así:

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

Por si fuera poco, me Lanzaremos un par de cambios a tu clase 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 

• derivan de objeto
• Pass self a __init__()
• Hacer __cmp__ una función miembro
• Añadir una función str() miembro de presentar Obj como cadena

Answer 7

me gusta la respuesta de Roberto Liffredo. No sabía sobre heapq.merge(). Hmmmph.

Esto es lo que la solución completa se ve como el uso de plomo de 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 

O:

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

Answer 8

me hizo una pregunta similar y tiene unas excelentes respuestas:

• Joining a set of ordered-integer yielding Python iterators

Las mejores soluciones de esa pregunta son variantes del algoritmo de fusión, que se puede leer aquí:

• Wikipedia: Merge Algorithm

Answer 9

A continuación se muestra un ejemplo de una función que se ejecuta en O comparaciones (n) .

Puede hacer esto más rápido haciendo iteradores ayb e incrementándolos.

he llamado simplemente la función dos veces para fusionar listas: 3

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 

Sin embargo, heapq.merge utiliza una mezcla de este método y colmadas los elementos actuales de todas las listas, por lo que debería llevar a cabo mucho mejor