Объединение двух отсортированных списков в Python
У меня есть два списка объектов. Каждый список уже отсортирован по свойству объекта, имеющего тип datetime. Я хотел бы объединить два списка в один отсортированный список. Это лучший способ просто сделать вид или есть более умный способ сделать это в Python?
Ответы
Ответ 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]
.. легко! Кроме того, он использует только две встроенные функции, поэтому, предполагая, что списки имеют разумный размер, он должен быть быстрее, чем реализация сортировки/слияния в цикле. Что еще более важно, это намного меньше кода и очень читаемо.
Если ваши списки большие (более нескольких сотен тысяч, я бы догадался), возможно, будет проще использовать альтернативный/пользовательский метод сортировки, но, скорее всего, будут сделаны другие оптимизации (например, не хранить миллионы 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]
Ответ 2
есть ли более умный способ сделать это в Python
Об этом не упоминалось, поэтому я продолжу - в модуле heapq в Python 2 есть функция слияния stdlib 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]
Здесь документация.
Ответ 3
Короче говоря, если len(l1 + l2) ~ 1000000 использовать:
L = l1 + l2
L.sort()
![merge vs. sort comparison]()
Описание рисунка и исходного кода можно найти здесь.
Рисунок был сгенерирован следующей командой:
$ python make-figures.py --nsublists 2 --maxn=0x100000 -s merge_funcs.merge_26 -s merge_funcs.sort_builtin
Ответ 4
Это просто слияние. Обработайте каждый список так, как если бы он был стеком, и постоянно наносите меньшую из двух головок стека, добавляя элемент в список результатов, пока один из стеков не будет пустым. Затем добавьте все остальные элементы в результирующий список.
Ответ 5
В 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
Я тестировал их со списками, созданными с помощью
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 элементов и увеличил их соответственно, поскольку это было довольно медленно.
Ответ 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. Надеюсь, это поможет.
Ответ 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 2.6 heapq.merge - это еще одна история.
Ответ 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() является верхней границей, то timsort, являющийся O (n log n) на произвольном входе, не противоречит его O (n), заданному отсортированным (L1) + отсортированным (L2).
Ответ 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
Ответ 10
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
Ответ 11
Реализация шага слияния в сортировке слиянием, которая проходит через оба списка:
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]
Я все еще изучаю алгоритмы, пожалуйста, дайте мне знать, если код может быть улучшен в любом аспекте, ваши отзывы приветствуются, спасибо!
Ответ 12
Ну, наивный подход (объединить 2 списка в большой и сортировать) будет сложностью O (N * log (N)). С другой стороны, если вы реализуете слияние вручную (я не знаю о каком-либо готовом коде в python libs для этого, но я не эксперт), сложность будет O (N), что явно быстрее.
Идея хорошо описана в посте Барри Келли.
Ответ 13
Используйте шаг 'merge' для сортировки слияния, он запускается в O (n) времени.
От wikipedia (псевдокод):
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
Ответ 14
Если вы хотите сделать это способом, более совместимым с тем, что происходит на итерации, попробуйте это
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 )
Ответ 15
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)
Ответ 16
Использовали операцию слияния сортировки слияния. Но я использовал генераторы. Временная сложность 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)
Ответ 17
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)
Будет сортировать список на месте. Определите свою собственную функцию для сравнения двух объектов и передайте эту функцию во встроенную функцию сортировки.
НЕ используйте сортировку пузырьков, она имеет ужасную производительность.
Ответ 18
Это мое решение за линейное время без редактирования 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:]
Ответ 19
Этот код имеет временную сложность 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
Ответ 20
Мой взгляд на эту проблему:
a = [2, 5, 7]
b = [1, 3, 6]
[i for p in zip(a,b) for i in (p if p[0] < p[1] else (p[1],p[0]))]
# Output: [1, 2, 3, 5, 6, 7]
Ответ 21
Надеюсь это поможет. Довольно просто и прямо:
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]
