在 Python 中合并两个已排序列表-IT科技

摘要：问题描述：我有两个对象列表。每个列表都已按日期时间类型的对象的属性排序。我想将两个列表合并为一个排序列表。最好的方法是只进行排序，还是有更聪明的方法在 Python 中执行此操作？解决方案 1：有没有更聪明的方法在 Python 中做到这一点还没有人提到这一点，所以我继续说 - python 2.6+ 的 h...

问题描述：

我有两个对象列表。每个列表都已按日期时间类型的对象的属性排序。我想将两个列表合并为一个排序列表。最好的方法是只进行排序，还是有更聪明的方法在 Python 中执行此操作？

解决方案 1：

有没有更聪明的方法在 Python 中做到这一点

还没有人提到这一点，所以我继续说 - python 2.6+ 的 heapq 模块中有一个合并 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]

这是文档。

解决方案 2：

人们似乎把这件事复杂化了。只需合并两个列表，然后对它们进行排序：

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

解决方案 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

解决方案 4：

这只是合并。将每个列表视为一个堆栈，并不断弹出两个堆栈头中较小的一个，将项目添加到结果列表中，直到其中一个堆栈为空。然后将所有剩余项目添加到结果列表中。

res = []
while l1 and l2:
    if l1[0] < l2[0]:
        res.append(l1.pop(0))
    else:
        res.append(l2.pop(0))

res += l1
res += l2

解决方案 5：

ghoseb 的解决方案存在一个小缺陷，使其复杂度为 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()，尽管它的算法复杂度确实更差。盈亏平衡点在每个源列表中约为一百万个项目（总共 200 万个）。

合并方法的一个优点是，它可以很容易地重写为生成器，从而使用更少的内存（不需要中间列表）。

[编辑]
我重新尝试了更接近问题的情况 - 使用包含字段“ ”的对象列表，date该字段是日期时间对象。上面的算法改为比较.date，排序方法改为：

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

这确实改变了一些事情。比较成本更高意味着我们执行的数字变得更加重要，相对于实现的恒定时间速度。这意味着合并弥补了失地，在 100,000 个项目时超过了 sort() 方法。基于更复杂的对象（例如大字符串或列表）进行比较可能会进一步改变这种平衡。

# 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]：注意：实际上，我只对 1,000,000 个项目进行了 10 次重复，然后相应地扩大了规模，因为它非常慢。

解决方案 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)

这应该可以很好地与日期时间对象配合使用。希望这能有所帮助。

解决方案 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完全是另一回事。

解决方案 8：

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

解决方案 9：

Python 的排序实现“timsort”专门针对包含有序部分的列表进行了优化。此外，它是用 C 编写的。

http://bugs.python.org/file4451/timsort.txt

http://en.wikipedia.org/wiki/Timsort

正如人们所提到的，它可能会通过某个常数因子多次调用比较函数（但在很多情况下，可能会在更短的时间内调用更多次！）。

然而，我永远不会依赖这个。 – Daniel Nadasi

我相信 Python 开发人员致力于保留 timsort，或者至少在这种情况下保留 O(n) 的排序。

广义排序（即，将有限值域中的基数排序分开）
在串行机器上不能以小于 O(n log n) 的速度完成。– Barry Kelly

是的，一般情况下排序不可能比这更快。但由于 O() 是上限，timsort 在任意输入上为 O(n log n) 并不与给定 sorted(L1) + sorted(L2) 时为 O(n) 矛盾。

解决方案 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]

我仍在学习算法，如果代码可以在任何方面改进，请告诉我，非常感谢您的反馈，谢谢！

解决方案 11：

使用合并排序的“合并”步骤，它在 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

解决方案 12：

下面是递归实现。平均性能为 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

解决方案 13：

这是我在线性时间内无需编辑 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:]

解决方案 14：

我同意以下答案。

from math import floor

def merge_sort(l):
    if len(l) < 2:
        return l
    left = merge_sort(l[:floor(len(l)/2)])
    right = merge_sort(l[floor(len(l)/2):])
    return merge(left, right)

def merge(a, b):
    i, j = 0, 0
    a_len, b_len = len(a), len(b)
    output_length = a_len + b_len
    out = list()
    for _ in range(output_length):
        if i < a_len and j < b_len and a[i] < b[j]:
            out.append(a[i])
            i = i + 1
        elif j < b_len:
            out.append(b[j])
            j = j + 1
    
    while (i < a_len):
        out.append(a[i])
        i += 1
    
    while (j < b_len):
        out.append(b[j])
        j += 1
        
    return out


if __name__ == '__main__':
    print(merge_sort([7, 8, 9, 4, 5, 6]))

解决方案 15：

好吧，简单的方法（将 2 个列表合并为一个大列表并进行排序）的复杂度将是 O(N*log(N))。另一方面，如果您手动实现合并（我不知道 python 库中是否有现成的代码，但我不是专家），复杂度将是 O(N)，这显然更快。这个想法在 Barry Kelly 的帖子中描述得很好。

解决方案 16：

如果你想以一种更符合学习迭代过程的方式来做这件事，可以尝试一下

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 )

解决方案 17：

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)

解决方案 18：

使用了归并排序的归并步骤。但我使用了生成器。 时间复杂度为 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)

解决方案 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：

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

解决方案 21：

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)

将就地对列表进行排序。定义您自己的函数来比较两个对象，并将该函数传递给内置排序函数。

不要使用冒泡排序，它的性能很差。

解决方案 22：

希望这能有所帮助。非常简单直接：

l1 = [1, 3, 4, 7]

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

l3=l1+l2

l3.排序()

打印 (l3)

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