2つのソートされたリストをマージするさまざまな方法の比較

（整数を簡単にするために）2つのリストがあり、それぞれがソートされているとします。それらを1つのリストにまとめたいので、これも並べ替える必要があります。このタスクはおそらく誰もが知っているでしょう。たとえば、マージソートで使用されます。

実装には多くの方法があります（特にpythonで）。それらのいくつかを見て、さまざまな入力の経過時間を比較してみましょう。

アルゴリズムの主なアイデアは、各リストの先頭に1つのラベルを配置することで、マークされた要素を比較し、小さい方の要素を取得して、リスト内のラベルを次の番号に移動することです。リストの1つが終了したら、残りの2番目を最後に追加する必要があります。

入力データは変更されません

2つのリスト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か所の結果が得られる方法もあります。

PS

コード、テスト、グラフ付きのジュピターノートブックはgitlabにあります。

おそらくこの分析は不完全です、私はあなたのオプションを比較に追加してうれしいです、提案します。