0

アルゴリズム ロジックの簡潔な表現は、長い表現よりも直感的であると感じることがあります。例として、次のような単純な Python 実装を使用したバイナリ検索 ( wikipedia ) があります。

def binary_search(A, L, R, T):
    while L != R:
        M = (L + R + 1) // 2
        if A[M] > T:
            R = M - 1
        else:
            L = M
    if A[L] == T:
        return L
    else:
        return -1

(注:ウィキペディアのページの疑似コードにある asの長さの引数を使用するのではなく、ソートされた配列引数内の間隔の最初と最後のインデックスとなる引数Lと引数を導入しました。)RAnA

条件式と代入式 (セイウチ演算子) に依存する短い実装は次のとおりです。

def binary_search(A, L, R, T):
    while L != R:
        L, R = (L, M - 1) if A[M := (L + R + 1) // 2] > T else (M, R)
    return L if A[L] == T else -1

私にとっては、単一行のループ本体は簡潔であり、厳密には、従来の if/else ブロックで展開されたループ本体よりも多くの操作が必要になる可能性がありますが、目を上下に移動する必要がない程度に好ましいです。コードを通して何が起こっているのかを把握します。M最初に現在の検索間隔の中間点になるように更新した後L, R、その間隔を縮小して、左側が同じで右側が減少するか、またはその逆になることを示しています。ソートされた入力配列の中点値Aとターゲット値T

実際、正直に言うと、私が本当にやりたいことは次のとおりです。

def binary_search(A, L, R, T):
    while L != R:
        (L, R := M - 1) if A[M := (L + R + 1) // 2] > T else (L := M, R)
    return L if A[L] == T else -1

上記の 2 番目と 3 番目のコード サンプルにスタイル ガイドに基づく禁止事項があるかどうか疑問に思っています。

4

0 に答える 0