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

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

15 Solutions collect form web for “Объединение двух отсортированных списков в Python”

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

>>> 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 , а sorted(l1+l2) значительно быстрее:

merge_sorted_lists взял ..

 [9.7439379692077637, 9.8844599723815918, 9.552299976348877] 

sorted(l1+l2) .

 [2.860386848449707, 2.7589840888977051, 2.7682540416717529] 

есть ли более разумный способ сделать это в 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] 

Вот документация https://docs.python.org/2/library/heapq.html

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

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

 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 миллиона).

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

[Edit] Я повторил это с ситуацией, более близкой к вопросу – с использованием списка объектов, содержащих поле « 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 предметов и увеличил их соответственно, поскольку это было довольно медленно.

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

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

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

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

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

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

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

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

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

Используйте шаг 'merge' сортировки слияния, он работает в 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 

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

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

 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) 

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

 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(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(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) 

Наилучшим образом, наивный подход (объединить 2 списка в большой и сортировать) будет сложностью O (N * log (N)). С другой стороны, если вы реализуете слияние вручную (я не знаю о каком-либо готовом коде в python libs для этого, но я не эксперт), сложность будет 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) 

Будет сортировать список на месте. Определите свою собственную функцию для сравнения двух объектов и передайте эту функцию во встроенную функцию сортировки.

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

  • Преобразование списка в * args в Python
  • Можно ли превратить список в вложенный ключ ключей * без * рекурсии?
  • Метод списка для удаления последнего элемента в списке, а также всех элементов
  • Замораживание в Python?
  • Удалить дубликат dict в списке в Python
  • На месте способа применить перестановку к списку? (инвертирует сортировку по ключу)
  • Python берет последний номер каждой строки в текстовом файле и превращает его в список
  • Python преобразует список пар в словарь
  • Сортировка на разных уровнях в Python
  • Найти начальные и конечные индексы подсписок в списке
  • Python как взять список в качестве параметра и изменить его значения?
  •  
    Interesting Posts for Van-Lav

    Расширение STARTTLS не поддерживается сервером. Получение этой ошибки при попытке отправить электронное письмо через Django и частный адрес электронной почты

    Загрузите и распакуйте файл с помощью Python

    Изменение глобальной переменной с тем же именем, что и локальная переменная

    Как я могу упростить это преобразование с подчеркивания на camelcase в Python?

    Можно ли добавить новый метод в класс Thread Python?

    Найти словарные ключи с повторяющимися значениями

    использование или API tf.app.flags

    Тестирование скрипта python в определенной версии

    Хотелось бы использовать PubNub для отправки обновлений в реальном времени в веб-браузер пользователя

    Jupyter Notebook: интерактивный сюжет с виджетами

    Установка Twisted through pip на одном сервере

    Отслеживание * максимального использования памяти с помощью функции Python

    Установка Pygame на Mac в сборку Enthought

    Не удалось запустить сервер devlopment – BindError: невозможно найти согласованный порт localhost

    Как функции numpy работают внутри объектов панды?

    Python - лучший язык программирования в мире.