比较合并两个排序列表的不同方法

假设我们有两个列表（为了简化整数），每个列表都已排序。我们希望将它们合并为一个列表，还必须对其进行排序。该任务可能是每个人都熟悉的；例如，在合并排序中使用它。

有很多实现方式（尤其是在python中）。让我们看一下其中的一些，并比较不同输入的经过时间。

该算法的主要思想是，通过在每个列表的开头放置一个标签，我们将比较标记的元素，取较小的元素并将其列表中的标签移动到下一个数字。当列表之一结束时，您需要将第二个列表的其余部分添加到末尾。

输入数据不变

设两个列表list1和list2。

让我们从最简单的算法开始：让我们为i和标记标签，j并选择较小的标签list1[i]，list2[j]然后将其标签增加1，直到标签之一超出列表的边界。

在第一个比较中，我们将在列表中的两个最小元素中选择最小元素，然后移至下一个元素，因此，两个列表中的最小元素将位于结果一个元素的零位置。此外，不难通过归纳证明进一步的合并将正确进行。

让我们继续执行代码：

def simple_merge(list1, list2):
    i, j = 0, 0
    res = []
    while i < len(list1) and j < len(list2):
        if list1[i] < list2[j]:
            res.append(list1[i])
            i += 1
        else:
            res.append(list2[j])
            j += 1
    res += list1[i:]
    res += list2[j:] 
    #   list1[i:]  list2[j:]   ,     
    return res

请注意，此代码仅在列表中使用前移。因此，使用迭代器就足够了。让我们使用迭代器重写算法。

我们还将更改列表结尾的处理方式，因为现在我们无法直接复制到结尾。我们将处理这些元素，直到两个迭代器都到达末尾为止；如果一个迭代器已经在末尾，那么我们将简单地从第二个开始。

def iter_merge(list1, list2):
    result, it1, it2 = [], iter(list1), iter(list2)
    el1 = next(it1, None)
    el2 = next(it2, None)
    while el1 is not None or el2 is not None:
        if el1 is None or (el2 is not None and el2 < el1):
            result.append(el2)
            el2 = next(it2, None)
        else:
            result.append(el1)
            el1 = next(it1, None)
    return result

(result.append()) , . , , .

def gen_merge_inner(it1, it2):
    el1 = next(it1, None)
    el2 = next(it2, None)
    while el1 is not None or el2 is not None:
        if el1 is None or (el2 is not None and el2 < el1):
            yield el2
            el2 = next(it2, None)
        else:
            yield el1
            el1 = next(it1, None)

def gen_merge(list1, list2):
    return list(gen_merge_inner(iter(list1), iter(list2))) #    

python .

• merge heapq. , , , : , , .

  
  
  

  :

  
  
  

  from heapq import merge
  
  def heapq_merge(list1, list2):
  return list(merge(list1, list2)) #   

  
  
  

• Counter collections. Counter , , , , (, ).

  
  
  

  gen_merge_inner Counter(list1) Counter(list2):

  
  
  

  def counter_merge(list1, list2):
  return list(gen_merge_inner(Counter(list1).elements(), Counter(list2).elements()))

  
  
  

• , , . .

  
  
  

  def sort_merge(list1, list2):
  return sorted(list1 + list2)

  
  
  

, ( ). . pop(0) , .

def pop_merge(list1, list2):
    result = []
    while list1 and list2:
        result.append((list1 if list1[0] < list2[0] else list2).pop(0))
    return result + list1 + list2

4 , . , , . , . , , .

def reverse_pop_merge(list1, list2):
    result = []
    while list1 and list2:
        result.append((list1 if list1[-1] > list2[-1] else list2).pop(-1))
    return (result + list1[-1::-1] + list2[-1::-1])[-1::-1]

.

, :

• simple_merge
• iter_merge
• gen_merge
• heapq_merge
• counter_merge
• sort_merge
• pop_merge
• reverse_pop_merge

timeit. .

: , , , , . .

, $$$1$ $$$10^5$, $$$1$ $$$10^6$.

pop reverse_pop:

pop_merge , .

pop_merge, :

reverse_pop_merge heapq_merge.

, , , .

,

$$$[50x, 50(x+1))$, $$$x$ , $$$1$. $$$50$.

pop_merge heapq_merge, .

, ,

$$$x$, $$$10^4 + 100x$.

( ) reverse_pop_merge , sort_merge, .

,

, $$$5$, $$$1$.

, counter_merge reverse_pop_merge heapq_merge, .

sort_merge! , .

其次，在绝大多数情况下是gen_merge，其次是iter_merge。

其余方法使用的时间甚至更多，但是在某些极端情况下，可以达到2-3位的结果。

聚苯乙烯

可以在gitlab上找到代码，测试，带有图形的jupyter笔记本。

也许这种分析是不完整的，建议我将您的选择添加到比较中。