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

Question

У меня есть два списка объектов. Каждый список уже отсортирован по свойству объекта типа datetime. Я хотел бы объединить два списка в один отсортированный список. Это лучший способ просто сделать сортировку или есть более умный способ сделать это в Python?

Answer 1

Люди, кажется, слишком усложняют это. Просто объедините два списка, а затем сортируйте их:

>>> l1 = [1, 3, 4, 7]
>>> l2 = [0, 2, 5, 6, 8, 9]
>>> l1.extend(l2)
>>> sorted(l1)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

.. или короче (и без изменения l1):

>>> sorted(l1 + l2)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

.. легко! Кроме того, он использует только две встроенные функции, поэтому при условии, что списки имеют разумный размер, это должно быть быстрее, чем реализация сортировки / объединения в цикле. Что еще более важно, вышеприведенный код намного меньше кода и очень удобочитаем.

Если ваши списки велики (я думаю, их будет несколько сотен тысяч), может быть быстрее использовать альтернативный / пользовательский метод сортировки, но, скорее всего, сначала нужно сделать другие оптимизации (например, не хранить миллионы *). 1010 * объекты)

Используя timeit.Timer().repeat() (который повторяет функции 1000000 раз), я свободно сравнил его с решением ghoseb , и sorted(l1+l2) значительно быстрее:

merge_sorted_lists взял ..

[9.7439379692077637, 9.8844599723815918, 9.552299976348877]

sorted(l1+l2) взял ..

[2.860386848449707, 2.7589840888977051, 2.7682540416717529]

Answer 2

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

Об этом не упоминалось, поэтому я продолжу - в модуле heapq в Python 2.6+ есть функция merge stdlib . Если все, что вы хотите сделать, это добиться своей цели, это может быть лучшей идеей. Конечно, если вы хотите реализовать свой собственный способ, сортировка слиянием - это путь.

>>> 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]

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

Answer 3

Короче говоря, если 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

Answer 4

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

Answer 5

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

item = l1.pop(0)

Со связанными списками или запросами это будет операция O (1), поэтому не будет влиять на сложность, но так как списки python реализованы как векторы, это копирует остальные элементы l1 на один пробел слева, O ( н) операция. Поскольку это делается при каждом прохождении списка, алгоритм 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

Я протестировал их со списками, созданными с помощью

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 - это правильно, просто использование sorted () предпочтительнее, если только вы не ожидаете очень больших списков, хотя у него действительно хуже алгоритмическая сложность. Точка безубыточности составляет около миллиона элементов в каждом списке источников (всего 2 миллиона).

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

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

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

Это немного меняет дело. Сравнение более дорогое означает, что число, которое мы выполняем, становится более важным по сравнению с постоянной скоростью реализации. Это означает, что слияние компенсирует потерянные позиции, превосходя метод sort () на 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 элементов и соответственно увеличил его, поскольку это было довольно медленно.

Answer 6

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

#!/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)

Это должно хорошо работать с объектами datetime. Надеюсь, это поможет.

Answer 7

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 heapq.merge это совсем другая история.

Answer 8

Реализация сортировки Python "timsort" специально оптимизирована для списков, содержащих упорядоченные разделы. Плюс, это написано на C.

http://bugs.python.org/file4451/timsort.txt
http://en.wikipedia.org/wiki/Timsort

Как уже упоминалось, она может вызывать функцию сравнения несколько раз с помощью некоторого постоянного фактора (но, возможно, во многих случаях она вызывается чаще в более короткий период времени!).

Однако я бы никогда не стал полагаться на это. - Даниэль Надаси

Я полагаю, что разработчики Python стремятся сохранить timsort или, по крайней мере, сохранить сортировку, которая в этом случае будет O (n).

Обобщенная сортировка (т. Е. Исключая радикальные сортировки из областей с ограниченными значениями)
не может быть сделано меньше, чем O (n log n) на последовательном компьютере. - Барри Келли

Правильно, сортировка в общем случае не может быть быстрее, чем это. Но так как O () является верхней границей, тимсорт, являющийся O (n log n) на произвольном входе, не противоречит тому, что O (n) задан sorted (L1) + sorted (L2).

Answer 9

Рекурсивная реализация приведена ниже. Средняя производительность O (n).

def merge_sorted_lists(A, B, sorted_list = None):
    if sorted_list == None:
        sorted_list = []

    slice_index = 0
    for element in A:
        if element <= B[0]:
            sorted_list.append(element)
            slice_index += 1
        else:
            return merge_sorted_lists(B, A[slice_index:], sorted_list)

    return sorted_list + B

или генератор с улучшенной пространственной сложностью:

def merge_sorted_lists_as_generator(A, B):
    slice_index = 0
    for element in A:
        if element <= B[0]:
            slice_index += 1
            yield element       
        else:
            for sorted_element in merge_sorted_lists_as_generator(B, A[slice_index:]):
                yield sorted_element
            return        

    for element in B:
        yield element

Answer 10

Реализация шага слияния в сортировке слиянием, которая повторяет оба списка:

def merge_lists(L1, L2):
    """
    L1, L2: sorted lists of numbers, one of them could be empty.

    returns a merged and sorted list of L1 and L2.
    """

    # When one of them is an empty list, returns the other list
    if not L1:
        return L2
    elif not L2:
        return L1

    result = []
    i = 0
    j = 0

    for k in range(len(L1) + len(L2)):
        if L1[i] <= L2[j]:
            result.append(L1[i])
            if i < len(L1) - 1:
                i += 1
            else:
                result += L2[j:]  # When the last element in L1 is reached,
                break             # append the rest of L2 to result.
        else:
            result.append(L2[j])
            if j < len(L2) - 1:
                j += 1
            else:
                result += L1[i:]  # When the last element in L2 is reached,
                break             # append the rest of L1 to result.

    return result

L1 = [1, 3, 5]
L2 = [2, 4, 6, 8]
merge_lists(L1, L2)               # Should return [1, 2, 3, 4, 5, 6, 8]
merge_lists([], L1)               # Should return [1, 3, 5]

Я все еще изучаю алгоритмы, пожалуйста, дайте мне знать, если код может быть улучшен в любом аспекте, ваши отзывы приветствуются, спасибо!