Объедините отсортированные списки в Python

Мне нравится ответ Роберто Лиффредо. Я не знал о heapq.merge (). Хммм.

Вот как выглядит полное решение с использованием руководства Роберто:

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

Я не знаю, будет ли это быстрее, но вы можете упростить это с помощью:

def GetObjKey(a):
    return a.points

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

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

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

import bisect

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

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

Это вставка O (log (n)), поэтому слияние a, b и c будет O (n log (n))

В Python вы можете использовать модуль heapq .

Вот и все: полностью функционирующая сортировка слиянием для списков (адаптированная из моей сортировки здесь ):

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

• Наследовать от объекта
• Передать self в __ init __ ()
• Сделать __ cmp __ функцией-членом
• Добавить str () , чтобы представить Obj в виде строки

Однострочное решение с использованием сортировки:

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

IMO это решение очень читабельно.

Используя модуль 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)

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

• Присоединение к набору упорядоченных целочисленных значений дает Итераторы Python

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

• Википедия: Алгоритм слияния