python - 连接两个排序的整数列表的更好方法

Question

假设我有一个列表和另一个元组，它们都已排序:

A = [10, 20, 30, 40]
B = (20, 60, 81, 90)

我需要的是将 B 中的所有元素添加到 A 中，使 A 保持排序。

我可以提出的解决方案是:

for item in B:
    for i in range(0, len(A)):
        if item > A[i]:
            i += 1
        else: 
            A.insert(i, item)

假设A大小为m，B大小为n；这个解决方案在最坏的情况下需要 O(mxn)，我怎样才能让它表现得更好？

Answer 1

一个简单的方法是 heapq.merge :

A = [10, 20, 30, 40]

B = (20, 60, 81, 90)

from heapq import merge

for ele in merge(A,B):
    print(ele)

输出:

10
20
20
30
40
60
81
90

使用其他 O(n) 解决方案的一些计时:

In [53]: A = list(range(10000))

In [54]: B = list(range(1,20000,10))

In [55]: timeit list(merge(A,B))
100 loops, best of 3: 2.52 ms per loop

In [56]: %%timeit
C = []
i = j = 0
while i < len(A) and j < len(B):
    if A[i] < B[j]:
        C.append(A[i])
        i += 1
    else:
        C.append(B[j])
        j += 1
C += A[i:] + B[j:]
   ....: 
100 loops, best of 3: 4.29 ms per loop
In [58]: m =list(merge(A,B))
In [59]: m == C
Out[59]: True

如果你想推出自己的，这比合并快一点:

def merger_try(a, b):
    if not a or not b:
        yield chain(a, b)
    iter_a, iter_b = iter(a), iter(b)
    prev_a, prev_b = next(iter_a), next(iter_b)
    while True:
        if prev_a >= prev_b:
            yield prev_b
            try:
                prev_b = next(iter_b)
            except StopIteration:
                yield prev_a
                break
        else:
            yield prev_a
            try:
                prev_a = next(iter_a)
            except StopIteration:
                yield prev_b
                break
    for ele in chain(iter_b, iter_a):
        yield ele

一些时间:

In [128]: timeit list(merge(A,B))
1 loops, best of 3: 771 ms per loop

In [129]: timeit list(merger_try(A,B))
1 loops, best of 3: 581 ms per loop

In [130]: list(merger_try(A,B))  == list(merge(A,B))
Out[130]: True

In [131]: %%timeit                                 
C = []
i = j = 0
while i < len(A) and j < len(B):
    if A[i] < B[j]:
        C.append(A[i])
        i += 1
    else:
        C.append(B[j])
        j += 1
C += A[i:] + B[j:]
   .....: 
1 loops, best of 3: 919 ms per loop