Pythonでのマージソート

Question

私のマージソートの実装は現在非常に長い時間がかかります。100万の要素を持つリストの場合、リストをソートするのに130秒以上かかります。

• 誰かが私のコードを見て、それを改善するために何ができるかを提案してもらえますか？

• 私のコードにかなり時間がかかっている特別なものはありますか？

コード

def splitlist(L): #splits the list to a list of individual listed elements (e.g. [1,2] to [[1],[2]])
    envelop = lambda x: [x]
    return(list(map(envelop,L)))


def merge(L_1,L_2): #merges two (already sorted) lists to one sorted list
    N = []
    while len(L_1) > 0 and len(L_2) > 0:
        if L_1[0] > L_2[0]:
            N += [L_2.pop(0)]
        else:
            N += [L_1.pop(0)]
    if len(L_1) == 0:
        N += L_2
    else:
        N += L_1
        
    return(N)


#performs one round of pairwise merges (e.g. [[2],[1],[4],[3]] to [[1,2],[3,4]]), or [[5,10],[1,8],[2,3]] to [[1,2,3,5,8,10]])   
def mergelist(L): 
    N = []
    if len(L) % 2 == 0:
        for i in range(0,len(L)//2):
            N += [merge(L[2*i],L[2*i + 1])]
    else:
        for i in range(0,len(L)//2 - 1):
            N += [merge(L[2*i],L[2*i + 1])]
        N += [merge(merge(L[-3],L[-2]),L[-1])]
    
    return(N)

def mergesort(L): #recursively performs mergelist until there is only 1 sorted list remaining
    L = splitlist(L)
    while len(L) > 1:
        L = mergelist(L)
    return(L[0])

百万の要素を生成するための私のコードは次のとおりです。

rlist = random.sample(range(0,2000000),1000000)

Answer 1

pop(0)線形時間がかかります。O（1）時間で、別の方法で行います。標準的な方法では、インデックス変数を使用します。よりPython的な方法については、この質問の回答を参照してください。または、を使用して右から左にマージpop()し、最終的reverse()に結果をマージすることもできます。

後者を行う1つの方法：

def merge(L1, L2):
    """Merges two (already sorted) lists to one sorted list."""
    N = []
    while L1 and L2:
        L = L1 if L1[-1] > L2[-1] else L2
        N.append(L.pop())
    N.reverse()
    N[:0] = L1 or L2
    return N

私が行ったその他の変更で、コードの他の部分にも適用できます。

• 変数から下線を削除しました。読みやすくなっていると思います。私はそれらを大文字のままにしました。なぜならL、それがPEP8が言っていることだからです。そして、私はN一貫性を保ちました。通常、私は使用するresultか、多分merged。なぜ選んだのかわからないN。「n」で始まる意味のある単語がある場合は、それを使用することをお勧めします。
• 関数パラメーター間のスペース。
• コメントの代わりに適切なdocstring形式。
• len(L_1) > 0通常L1の空でないチェックに置き換えられました。
• N += [x]通常のに置き換えられましたN.append(x)。

別の方法として、その1つの「長い」行を置き換えてL、より明確で遅い方法で決定します。

def merge(L1, L2):
    """Merges two (already sorted) lists to one sorted list."""
    N = []
    def last(L):
        return L[-1]
    while L1 and L2:
        L = max(L2, L1, key=last)
        N.append(L.pop())
    N.reverse()
    N[:0] = L1 or L2
    return N

いくつかの楽しみのために、2つのリスト内包ハック：

def merge(L1, L2):
    """Merges two (already sorted) lists to one sorted list."""
    def end(L):
        return L[-1:]
    return [max(L2, L1, key=end).pop() for _ in L1 + L2][::-1]

def merge(L, R):
    """Merges two (already sorted) lists to one sorted list."""
    return [(R, L)[L[-1:] > R[-1:]].pop() for _ in L + R][::-1]

そして、私ははるかに速い方法なしで去りたくありません：

def merge(L1, L2):
    """Merges two (already sorted) lists to one sorted list."""
    return sorted(L1 + L2)

ティムソートのおかげでそれはO（n）です。そして、Cコードのために高速O（n）。sortedマージソート内で強力なものを使用すると、そもそもマージソートを作成する目的が損なわれると思われる場合：マージソートを実行しているだけではない場合でも、それでも意味があります。少なくとも一度は、何かのカウントを埋め込んだマージソートを作成しましたが、実際sortedにはマージのためだけに使用しました。それが私のソリューションをより速く/より短く/よりシンプルにしたからです。

さらに効率的（空間と時間の両方）：

def merge(L1, L2):
    """Merges two (already sorted) lists to one sorted list."""
    L1 += L2
    L1.sort()
    return L1

（L2より長くL1なる可能性がある場合は、代わりにに挿入L1すると有利な場合がありますL2。）