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

Ответ 1

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

sorted(itertools.chain(args), cmp)

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

Ответ 2

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

import bisect

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

Ответ 3

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

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

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

Ответ 4

Мне нравится ответ Роберто Лифредо. Я не знал о 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

Ответ 5

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

def GetObjKey(a):
    return a.points

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

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

Ответ 6

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

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)

Ответ 7

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

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 в виде строки

Ответ 8

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

• Объединение набора упорядоченных целых чисел, дающих итераторы Python

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

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

Ответ 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 использует сочетание этого метода и купирует текущие элементы всех списков, поэтому должен работать намного лучше