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

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

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

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

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

#!/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. Надеюсь это поможет.

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

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

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

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

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

merge_sorted_lists взял ..

[9.7439379692077637, 9.8844599723815918, 9.552299976348877]

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

[2.860386848449707, 2.7589840888977051, 2.7682540416717529]

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

item = l1.pop(0)

Со связанными списками или deques это будет операция 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

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

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 элементов и соответственно увеличил масштаб, так как это было довольно медленно.

is there a smarter way to do this in Python

Об этом не упоминалось, поэтому я продолжу - в модуле heapq Python 2.6+ есть функция слияния 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]

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

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, даже для больших данных. heapq.merge Python 2.6 - это совсем другая история.

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

Рекурсивная реализация ниже. Средняя производительность - 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

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

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

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

I would never rely on this, however. – Daniel Nadasi

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

Generalized sorting (i.e. leaving apart radix sorts from limited value domains)
cannot be done in less than O(n log n) on a serial machine. – Barry Kelly

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

Если вы хотите сделать это более согласованным с изучением того, что происходит в итерации, попробуйте это

def merge_arrays(a, b):
    l= []

    while len(a) > 0 and len(b)>0:
        if a[0] < b[0]: l.append(a.pop(0))    
        else:l.append(b.pop(0))

    l.extend(a+b)
    print( l )

import random

    n=int(input("Enter size of table 1")); #size of list 1
    m=int(input("Enter size of table 2")); # size of list 2
    tb1=[random.randrange(1,101,1) for _ in range(n)] # filling the list with random
    tb2=[random.randrange(1,101,1) for _ in range(m)] # numbers between 1 and 100
    tb1.sort(); #sort the list 1 
    tb2.sort(); # sort the list 2
    fus=[]; # creat an empty list
    print(tb1); # print the list 1
    print('------------------------------------');
    print(tb2); # print the list 2
    print('------------------------------------');
    i=0;j=0;  # varialbles to cross the list
    while(i<n and j<m):
        if (tb1[i]<tb2[j]):
            fus.append(tb1[i]); 
            i+=1;
        else:
            fus.append(tb2[j]);
            j+=1;

    if (i<n):
        fus+=tb1[i:n];
    if (j<m):
        fus+=tb2[j:m];

    print(fus);

  # this code is used to merge two sorted lists in one sorted list (FUS) without
  #sorting the (FUS)

Использовали шаг слияния сортировки слияния. Но я использовал генераторы. Сложность времениНа)

def merge(lst1,lst2):
    len1=len(lst1)
    len2=len(lst2)
    i,j=0,0
    while(i<len1 and j<len2):
        if (lst1[i]<lst2[j]):
                yield lst1[i]
                i+=1
        else:
                yield lst2[j]
                j+=1
    if (i==len1):
        while(j<len2):
                yield lst2[j]
                j+=1
    elif (j==len2):
        while(i<len1):
                yield lst1[i]
                i+=1
l1=[1,3,5,7]
l2=[2,4,6,8,9]
mergelst=(val for val in merge(l1,l2))
print(*mergelst)

def merge_sort(a,b):

    pa = 0
    pb = 0
    result = []

    while pa < len(a) and pb < len(b):
        if a[pa] <= b[pb]:
            result.append(a[pa])
            pa += 1
        else:
            result.append(b[pb])
            pb += 1

    remained = a[pa:] + b[pb:]
    result.extend(remained)


return result

Реализация этапа слияния в сортировке слиянием, который выполняет итерацию по обоим спискам:

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]

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

Это мое решение в линейное время без редактирования l1 и l2:

def merge(l1, l2):
  m, m2 = len(l1), len(l2)
  newList = []
  l, r = 0, 0
  while l < m and r < m2:
    if l1[l] < l2[r]:
      newList.append(l1[l])
      l += 1
    else:
      newList.append(l2[r])
      r += 1
  return newList + l1[l:] + l2[r:]

Надеюсь это поможет. Довольно просто и понятно:

l1 = [1, 3, 4, 7]

l2 = [0, 2, 5, 6, 8, 9]

l3 = l1 + l2

l3.sort ()

печать (l3)

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

Этот код имеет временную сложность O (n) и может объединять списки любого типа данных, учитывая количественную функцию в качестве параметра func. Он создает новый объединенный список и не изменяет ни один из списков, переданных в качестве аргументов.

def merge_sorted_lists(listA,listB,func):
    merged = list()
    iA = 0
    iB = 0
    while True:
        hasA = iA < len(listA)
        hasB = iB < len(listB)
        if not hasA and not hasB:
            break
        valA = None if not hasA else listA[iA]
        valB = None if not hasB else listB[iB]
        a = None if not hasA else func(valA)
        b = None if not hasB else func(valB)
        if (not hasB or a<b) and hasA:
            merged.append(valA)
            iA += 1
        elif hasB:
            merged.append(valB)
            iB += 1
    return merged

в сложности O(m+n)

def merge_sorted_list(nums1: list, nums2:list) -> list:
        m = len(nums1)
        n = len(nums2)
        
        nums1 = nums1.copy()
        nums2 = nums2.copy()
        nums1.extend([0 for i in range(n)])
        while m > 0 and n > 0:
            if nums1[m-1] >= nums2[n-1]:
                nums1[m+n-1] = nums1[m-1]
                m -= 1
            else:
                nums1[m+n-1] = nums2[n-1]
                n -= 1
        if n > 0:
            nums1[:n] = nums2[:n]
        return nums1

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

выход

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

если у вас небольшой список, просто объедините их и отсортируйте с помощью встроенной функции, например:

def in_built_sort(list1, list2):
    // time complexity : O(nlog n) 
    return sorted(list1 + list2)

но если у вас есть МИЛЛИАРД или МИЛЛИАРД элементов в обоих списках, используйте этот метод:

def custom_sort(list1, list2):
    // time complexity : O(n)
    merged_list_size = len(list1) + len(list2)
    merged_list = [None] * merged_list_size

    current_index_list1 = 0
    current_index_list2 = 0
    current_index_merged = 0
    while current_index_merged < merged_list_size:
        if (not current_index_list1 >= len(list1) and (current_index_list2 >= len(list2) or list1[current_index_list1] < list2[current_index_list2])):
            merged_list[current_index_merged] = list1[current_index_list1]
            current_index_list1 += 1
        else:
            merged_list[current_index_merged] = list2[current_index_list2]
            current_index_list2 += 1

        current_index_merged += 1
    return merged_list

Тест производительности: протестировано против 10 миллионов случайных элементов в обоих списках и повторено 10 раз.

print(timeit.timeit(stmt=in_built_sort, number=10))  // 250.44088469999997  O(nlog n)   
print(timeit.timeit(stmt=custom_sort, number=10)) // 125.82338159999999  O(n)