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

def compareDate(obj1, obj2):
    if obj1.getDate() < obj2.getDate():
        return -1
    elif obj1.getDate() > obj2.getDate():
        return 1
    else:
        return 0



list = list1 + list2
list.sort(compareDate)

отсортирует список на месте. Определите свою собственную функцию для сравнения двух объектов и передачи, которые функционируют в созданный в функции вида.

НЕ используют пузырьковую сортировку, она имеет ужасную производительность.

Используйте шаг 'слияния' сортировки слиянием, он выполняет в O (n) время.

От Википедия (псевдокод):

function merge(left,right)
    var list result
    while length(left) > 0 and length(right) > 0
        if first(left) ≤ first(right)
            append first(left) to result
            left = rest(left)
        else
            append first(right) to result
            right = rest(right)
    end while
    while length(left) > 0 
        append left to result
    while length(right) > 0 
        append right to result
    return result

Ну, наивный подход (комбинируют 2 списка в большой и вид) будет O (N*log (N)) сложность. С другой стороны, если Вы реализуете слияние вручную (я не знаю ни о каком готовом коде в Python, освобождает для этого, но я не эксперт), сложность будет O (N), который ясно быстрее. Идея описана wery хорошо в сообщении Barry Kelly.

from datetime import datetime
from itertools import chain
from operator import attrgetter

class DT:
    def __init__(self, dt):
        self.dt = dt

list1 = [DT(datetime(2008, 12, 5, 2)),
         DT(datetime(2009, 1, 1, 13)),
         DT(datetime(2009, 1, 3, 5))]

list2 = [DT(datetime(2008, 12, 31, 23)),
         DT(datetime(2009, 1, 2, 12)),
         DT(datetime(2009, 1, 4, 15))]

list3 = sorted(chain(list1, list2), key=attrgetter('dt'))
for item in list3:
    print item.dt

вывод:

2008-12-05 02:00:00
2008-12-31 23:00:00
2009-01-01 13:00:00
2009-01-02 12:00:00
2009-01-03 05:00:00
2009-01-04 15:00:00

я держал пари, что это быстрее, чем любой из необычных алгоритмов слияния чистого Python, даже для больших данных. Python 2.6's heapq.merge является целым другая история.

Это - простое слияние двух отсортированных списков. Смотрите на пример кода ниже который слияния два отсортированных списка целых чисел.

#!/usr/bin/env python
## merge.py -- Merge two sorted lists -*- Python -*-
## Time-stamp: "2009-01-21 14:02:57 ghoseb"

l1 = [1, 3, 4, 7]
l2 = [0, 2, 5, 6, 8, 9]

def merge_sorted_lists(l1, l2):
    """Merge sort two sorted lists

    Arguments:
    - `l1`: First sorted list
    - `l2`: Second sorted list
    """
    sorted_list = []

    # Copy both the args to make sure the original lists are not
    # modified
    l1 = l1[:]
    l2 = l2[:]

    while (l1 and l2):
        if (l1[0] <= l2[0]): # Compare both heads
            item = l1.pop(0) # Pop from the head
            sorted_list.append(item)
        else:
            item = l2.pop(0)
            sorted_list.append(item)

    # Add the remaining of the lists
    sorted_list.extend(l1 if l1 else l2)

    return sorted_list

if __name__ == '__main__':
    print merge_sorted_lists(l1, l2)

Это должно хорошо работать с объектами даты и времени. Надежда это помогает.

Существует небольшой дефект в ghoseb's решение, делая его O (n ** 2), а не O (n).
проблема состоит в том, что это работает:

item = l1.pop(0)

Со связанными списками или двухсторонними очередями это было бы O (1) операция, так не будет влиять на сложность, но так как списки Python реализованы как векторы, это копирует остальную часть элементов l1 одно оставленное пространство, O (n) операция. Так как это сделано, каждый проходит через список, это поворачивает O (n) алгоритм в O (n ** 2) один. Это может быть исправлено при помощи метода, который не изменяет исходные списки, но просто отслеживает текущую позицию.

я испытал сравнительное тестирование исправленного алгоритма по сравнению с простым отсортированным (l1+l2), как предложено dbr

def merge(l1,l2):
    if not l1:  return list(l2)
    if not l2:  return list(l1)

    # l2 will contain last element.
    if l1[-1] > l2[-1]:
        l1,l2 = l2,l1

    it = iter(l2)
    y = it.next()
    result = []

    for x in l1:
        while y < x:
            result.append(y)
            y = it.next()
        result.append(x)
    result.append(y)
    result.extend(it)
    return result

, я протестировал их со списками, сгенерированными с [1 114]

l1 = sorted([random.random() for i in range(NITEMS)])
l2 = sorted([random.random() for i in range(NITEMS)])

Для различных размеров списка, я получаю следующие синхронизации (повторяющийся 100 раз):

# items:  1000   10000 100000 1000000
merge  :  0.079  0.798 9.763  109.044 
sort   :  0.020  0.217 5.948  106.882

Поэтому на самом деле, похоже, что dbr является правильным, просто использование отсортированного () предпочтительно, если Вы не ожидаете очень большие списки, хотя это действительно имеет худшую алгоритмическую сложность. Точка безубыточности, являющаяся приблизительно в миллионе объектов в каждом исходном списке (2 миллиона общих количеств).

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

[Редактирование] я повторил это с ситуацией ближе к вопросу - использование списка объектов, содержащих поле "date", которое является объектом даты и времени. Вышеупомянутый алгоритм был изменен для сравнения с .date вместо этого, и метод сортировки был изменен на:

return sorted(l1 + l2, key=operator.attrgetter('date'))

Это действительно изменяет вещи немного. Сравнение, являющееся более дорогим, означает, что число, которое мы выполняем, становится более важным относительно постоянно-разовой скорости реализации. Это означает, что слияние вернуло потерянные позиции, превосходя вид () метод в 100 000 объектов вместо этого. Сравнение на основе еще более сложного объекта (большие строки или списки, например), вероятно, сместило бы этот баланс еще больше.

# items:  1000   10000 100000  1000000[1]
merge  :  0.161  2.034 23.370  253.68
sort   :  0.111  1.523 25.223  313.20

[1]:Примечание: я на самом деле только сделал 10 повторений для 1 000 000 объектов и увеличился соответственно, поскольку это было довольно медленно.

Это просто объединяется. Рассматривайте каждый список, как будто это было стеком, и непрерывно выталкивает меньшие из двух голов стека, добавляя объект к списку результата, пока один из стеков не пуст. Тогда добавьте все остающиеся объекты к получающемуся списку.

Короче говоря, если len(l1 + l2) ~ 1000000 использование:

L = l1 + l2
L.sort()

Описание числа и исходного кода может быть найдено здесь .

число было сгенерировано следующей командой:

$ python make-figures.py --nsublists 2 --maxn=0x100000 -s merge_funcs.merge_26 -s merge_funcs.sort_builtin

там более умный способ сделать это в Python

, Это не было упомянуто, таким образом, я буду идти вперед - существует слияние stdlib функция в heapq модуле python 2.6 +. Если все, что Вы надеетесь делать, добивается цели, это могло бы быть лучшей идеей. Конечно, если Вы хотите реализовать свое собственное, слияние сортировки с объединением является способом пойти.

>>> list1 = [1, 5, 8, 10, 50]
>>> list2 = [3, 4, 29, 41, 45, 49]
>>> from heapq import merge
>>> list(merge(list1, list2))
[1, 3, 4, 5, 8, 10, 29, 41, 45, 49, 50]

Вот документация .