fusionner des listes triées en python

Question

j'ai un tas de listes triées d'objets, et une fonction de comparaison

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

ce qui fait magic ressembler? Ma mise en œuvre actuelle est

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

mais cela est très inefficace. De meilleures réponses?

Answer 1

La bibliothèque standard Python offre une méthode pour cela: heapq.merge.
Comme le dit la documentation, il est très similaire à l'utilisation de itertools (mais avec plus de limitations); si vous ne pouvez pas vivre avec ces limites (ou si vous ne l'utilisez Python 2.6) vous pouvez faire quelque chose comme ceci:

sorted(itertools.chain(args), cmp) 

Cependant, je pense qu'il a la même complexité que votre propre solution, bien que l'utilisation d'itérateurs devraient donner une assez bonne optimisation et augmentation de la vitesse.

Answer 2

Je ne sais pas si ce serait une plus rapide, mais vous pouvez simplifier avec:

def GetObjKey(a): 
    return a.points 

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

Vous pouvez aussi, bien sûr, utiliser cmp plutôt que key si vous préférez.

Answer 3

Utilisez le module bisect. De la documentation: "Ce module fournit un support pour maintenir une liste dans l'ordre trié sans avoir à trier la liste après chaque insertion."

import bisect 

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

Answer 4

Au lieu d'utiliser une liste, vous pouvez utiliser un [tas] (http://en.wikipedia.org/wiki/Heap_(data_structure).

L'insertion est O (log (n)), la fusion de manière a, b et c sera O (n log (n))

en Python, vous pouvez utiliser le heapq module

Answer 5

Une solution de ligne à l'aide triée:..

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

OMI cette solution est très lisibleEn utilisant le module heapq, cela pourrait être plus efficace, mais je ne l'ai pas testé. Vous ne pouvez pas spécifier la fonction cmp/key dans heapq, vous devez donc implémenter Obj pour être implicitement trié.

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

Answer 6

vous allez ici: une sorte de fusion entièrement fonctionnel pour les listes (adapté de mon genre 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) 

appel comme ceci:

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

Pour faire bonne mesure, je Jetterai quelques modifications à votre 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 

• Derive de l'objet
• passe self-__init__()
• Faire __cmp__ une fonction membre
• Ajouter une fonction membre str() de présenter Obj sous forme de chaîne

Answer 7

J'aime la réponse de Roberto Liffredo. Je ne connaissais pas heapq.merge(). Hmmmph.

Voici ce que la solution complète ressemble à l'aide de fil 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 

Ou:

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

Answer 8

j'ai posé une question similaire et a obtenu d'excellentes réponses:

• Joining a set of ordered-integer yielding Python iterators

Les meilleures solutions de cette question sont des variantes de l'algorithme de fusion, que vous pouvez lire ici:

• Wikipedia: Merge Algorithm

Answer 9

Voici un exemple d'une fonction qui fonctionne dans les comparaisons de O (n) .

Vous pouvez accélérer cette opération en créant des a et b iterateurs et en les incrém ent.

J'ai simplement appelé la fonction à deux reprises pour fusionner les listes 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 

Cependant, heapq.merge utilise un mélange de cette méthode et entasser les éléments actuels de toutes les listes, devrait donc bien meilleurs résultats