6

私は次の挿入ソートアルゴリズムを書きました

def insertionSort(L, reverse=False):
    for j in xrange(1,len(L)):
        valToInsert = L[j]
        i=j-1
        while i>=0 and L[i] > valToInsert:
            L[i+1] = L[i]
            i-=1
        L[i+1] = valToInsert
    return L

編集: 最後の > を < に変更して、逆に動作させるだけです。

しかし、ほとんどの人はこれらの状況で何をしますか? アルゴリズムを 2 つの if ステートメントで 2 回記述します。1 つは > で、もう 1 つは < です。変更がわずかであるが、ループ/コードの性質を完全に変更するだけのシナリオを通常処理する「正しい」方法は何ですか?

この質問は少し主観的であることは承知しています。

4

3 に答える 3

10

小なり演算子に変数を使用できます。

import operator
def insertionSort(L, reverse=False):       
    lt = operator.gt if reverse else operator.lt        
    for j in xrange(1,len(L)):
        valToInsert = L[j]
        i = j-1
        while 0 <= i and lt(valToInsert, L[i]):
            L[i+1] = L[i]
            i -= 1
        L[i+1] = valToInsert
    return L
于 2013-03-19T20:35:15.880 に答える
1

sortedandlist.sortおよびその他の、修飾される可能性のある処理を行うすべての関数にはkeyパラメーターがあり、特に順序付けを行う関数にもパラメーターがあることに気付くでしょうreverse。(これについては、 Sorting Mini-HOWTO で説明しています。)

したがって、それらがどのように実装されているかを見ることができます。残念ながら、CPython では、これらすべてが C で実装されています。さらに、「timsort」と呼ばれるカスタム アルゴリズムを使用します (「参考文献」をlistsort.txt参照)。しかし、ここで重要な部分を説明できると思います。これは非常に単純です。コードはコードlist.sortから分離されておりsorted、両方とも多数の機能に分散しています。しかし、最上位の functionlistsortを見るだけで、reverseフラグがどのように処理されるかがわかります。

1982     /* Reverse sort stability achieved by initially reversing the list,
1983     applying a stable forward sort, then reversing the final result. */
1984     if (reverse) {
1985         if (keys != NULL)
1986             reverse_slice(&keys[0], &keys[saved_ob_size]);
1987         reverse_slice(&saved_ob_item[0], &saved_ob_item[saved_ob_size]);
1988     }

最初と最後でリストを逆にするのはなぜですか? そもそもリストがほとんどソートされている場合、多くのソート アルゴリズム (timsort と挿入ソートの両方を含む) は、逆順よりも正しい順序で開始する方がはるかに優れています。はい、それは O(N)reverse呼び出しを無駄にしますが、あなたはすでにそれらの 1 つを行っています。また、ソートアルゴリズムは少なくとも O(N log N) であり、あなたのアルゴリズムは具体的には O(N^2) であるため、これはそうではありません。アルゴリズム的に悪化させないでください。もちろん、N が小さく、並べ替えが適切で、ランダムな順序のリストの場合、この無駄な 2N は N log N にかなり近いため、実際には違いが生じる可能性があります。N が大きくなるにつれて消えていく違いですがlist、いくつかの大きな s ではなく、何百万もの小さな s をソートしている場合は、心配する価値があるかもしれません。

2 番目に、逆スライスを作成して逆方向に実行していることに注意してください。これは、少なくとも潜在的に、元のlistオブジェクトを__getitem__逆の順序で参照することで最適化できます。つまり、2 つの反転は実際には O(1) です。これを行う最も簡単な方法は、文字通り逆スライスを作成することです: lst[::-1]. 残念ながら、これは実際には新しい reversed を作成するlistため、timsort には独自のカスタム reverse-slice オブジェクトが含まれます。ReversedListしかし、クラスを作成することで、Python でも同じことができます。

余分な関数呼び出しのコストがおそらく違いを圧倒するほど高いため、これはおそらく CPython では実際には高速ではありません。しかし、あなたは 2 つの呼び出しのアルゴリズムのコストについて不平を言っています。reverseこれにより、組み込みの並べ替え関数と同じ方法で問題が解決されます。

PyPy がどのようにそれを行うかを見ることもできます。で実装listされていlistobject.pyます。リストに含まれる内容に応じて、いくつかの異なる Strategy クラスの 1 つに委任されますが、すべての戦略 (何もしないものを除く) に目を通すと、それらは基本的に同じことを行います:sortリスト、次にreverseそれ。

したがって、CPython には十分であり、PyPy には十分です...おそらくあなたにとっては十分です。

于 2013-03-19T21:14:18.577 に答える
1

オプション1：

def insertionSort(L, reverse=False):
    # loop is the same...
    if reverse:
        L.reverse()
    return L

オプション 2:

def insertionSort(L, reverse=False):
    if reverse:
        cmpfunc = lambda a, b: cmp(b, a)
    else:
        cmpfunc = cmp
    for j in xrange(1,len(L)):
        valToInsert = L[j]
        i=j-1
        while i>=0 and cmpfunc(L[i], valToInsert) > 0:
            L[i+1] = L[i]
            i-=1
        L[i+1] = valToInsert
    return L
于 2013-03-19T20:36:41.307 に答える