Объединить упорядоченные списки в Python

Question

У меня есть куча отсортированных списков объектов, а также функция сравнения

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

что делает magic выглядеть? Моей текущей реализацией является

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

но это довольно неэффективно. Лучшие ответы?

Answer 1

стандартной библиотеки Python предлагает метод для этого: heapq.merge.
Как указано в документации, оно очень похоже на использование itertools (но с большим количеством ограничений); если вы не можете жить с этими ограничениями (или, если вы не используете Python 2.6) вы можете сделать что-то вроде этого:

sorted(itertools.chain(args), cmp) 

Однако, я думаю, что он имеет такую ​​же сложность, как ваше собственное решение, хотя, используя итераторы должны дать довольно неплохая оптимизация и увеличение скорости.

Answer 2

Я не знаю, будет ли это какой-либо быстрее, но вы могли бы упростить его:

def GetObjKey(a): 
    return a.points 

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

Вы также можете, конечно, использовать cmp, а не key, если вы предпочитаете.

Answer 3

Используйте модуль bisect. Из документации: «Этот модуль обеспечивает поддержку для ведения списка в отсортированном порядке без сортировки списка после каждой вставки».

import bisect 

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

Answer 4

Вместо того чтобы использовать список, вы можете использовать [кучного] (http://en.wikipedia.org/wiki/Heap_(data_structure).

Вставка представляет собой О (журнал (п)), так что слияние а, б и будет О (п log (п))

В Python, вы можете использовать heapq module

Answer 5

Одно из решений линии с использованием отсортированы:..

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

ИМ это решение очень читаемый

Используя модуль heapq, он может быть более эффективным, но я его не тестировал. Вы не можете указать функцию cmp/key в heapq, поэтому вам нужно реализовать Obj для неявной сортировки.

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

Answer 6

Здесь вы идете: полностью функционирующая сортировка слияния для списков (адаптирована из моего рода 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) 

вызовов это так:

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

Для хорошей меры, я введя несколько изменений в ваш класс 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 

• Выведите из объекта
• Pass self в __init__()
• Сделать __cmp__ функцию члена
• Добавить функцию в str() члена представить Obj в виде строки

Answer 7

Мне нравится ответ Роберто Liffredo в. Я не знал о heapq.merge(). Hmmmph.

Вот что полное решение выглядит как с помощью свинца Роберто:

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 

Или:

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

Answer 8

Я задавал подобный вопрос и получил отличные ответы:

• Joining a set of ordered-integer yielding Python iterators

Лучшие решения от этого вопроса являются варианты алгоритма слияния, который вы можете прочитать о здесь:

• Wikipedia: Merge Algorithm

Answer 9

Ниже приведен пример функции, которая работает в O (N) сравнений ,

Вы можете сделать это быстрее, выполнив итераторы a и b и увеличив их.

Я просто назвал функцию дважды, чтобы объединить 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 

Однако heapq.merge использует сочетание этого метода и обрушивая текущие элементы всех списков, так должна работать гораздо лучше