高速化大好き、プログラミング歴30年のムンペイです。

プロファイリングを終え、アルゴリズム的な最適化も概ね問題ない状態で、実装方法による高速化に取り組む段階で、まず見直すところを４つ挙げてみます。
今回はソースコード例の作成を中心にChatGPTに手伝ってもらいました。

ループ内の無駄な処理の最適化

まずは冗長な処理の削減に取り組みます。
ループの中で各イテレーションで値が変わらない計算は、ループの外に移動させることで計算回数を減らすことができます。

改善前:

result = []
constant_factor = 2.5
for i in range(100):
    # 不要な計算: `constant_factor`の値は変わらないので、この乗算はループの外で行うべき
    adjusted_factor = constant_factor * 10
    result.append(i * adjusted_factor)

このコードでは、adjusted_factorの計算がループの各イテレーションで行われていますが、constant_factorは変わらないため、この乗算はループの外で一度だけ行うことが可能です。

改善後:

constant_factor = 2.5
# ループ外で一度だけ計算
adjusted_factor = constant_factor * 10

result = []
for i in range(100):
    result.append(i * adjusted_factor)

この改善により、constant_factor * 10という計算をループの外で一度だけ行い、その結果をループ内で使用することで、計算の回数を減らし、全体の実行効率を向上させることができます。

例は非常に些細な計算ですが、ループ回数がもっと多ければ、例えば100万回などとなれば効果は無視できません。また、関数呼び出しをループ外に出すことも同様の効果があります。

ループの外に出せるならループに依存しておらずループ内にある必要はないということでもあり、コードのリファクタリングのきっかけとしても考えられます。

データ局所性（キャッシュ効率）の最適化

記憶階層によって驚くほどアクセス時間が異なるという説明をしましたが、特にキャッシュメモリでなるべく多くの処理を実行することが重要です。これを実現するには、データの局所性を意識した改良を行います。データの局所性（Data Locality）とは、プログラムがメモリ上の情報にアクセスする際に、物理的に近い位置にあるデータを連続してアクセスする性質や技術を指します。

キャッシュ効率で改善できそうなデータ局所性は、詳しく言うと下記の２つがあります。

• 時間的局所性（Temporal Locality）: 一度アクセスしたデータに短時間のうちに再度アクセスする性質。

• 空間的局所性（Spatial Locality）: 物理的に近い位置にあるデータに順番にアクセスする性質。

どちらも、アクセス順やデータ配置の工夫によりキャッシュ上での作業時間を長くするという対策は変わりません。

以下に、データ局所性を意識したPythonコードの例を示します。

改善前:

# 行と列のサイズが同じ2次元配列（行列）を操作する例
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

# 列ごとの合計を計算
sum = 0
for i in range(3):  # 列のインデックス
    for j in range(3):  # 行のインデックス
        sum += matrix[j][i]

このコードでは、行のインデックスを内側のループで回していますが、このアクセスパターンは空間的局所性を損ないます。なぜなら、メモリ上で連続して配置されているはずの行の要素に対して、飛び飛びにアクセスしているからです。

改善後:

# 先ほどと同じマトリックス
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

# 行ごとの合計を計算
sum = 0
for i in range(3):  # 行のインデックス
    for j in range(3):  # 列のインデックス
        sum += matrix[i][j]

この改善例では、行がメモリ上で連続して配置されていることを活かし、空間的局所性を向上させます。行ごとにデータを連続してアクセスすることで、キャッシュヒット率が上がり、処理速度が向上する可能性があります。

この例のように３×３程度では、キャッシュ容量が大きい現代的なプロセッサでは時間的局所性の範囲に収まってしまって手作業で改善するほどのコスト対効果はないように見えますが、100×100などになってくれば差は出てきますし、確実に効率は上がっているので常に意識しておいた方がよいでしょう。

条件分岐の順序変更

条件分岐はプログラムの速度を低下させる主要な原因のひとつです。

コンピュータはメモリ上のアドレスを１つ１つ進めて命令を読み込んでは実行していますが、条件分岐が発生すると次に実行する命令を離れたアドレスから読み込んでこなければなりません。これはプログラム実行にとっての局所性を破壊する状況となります。
メモリのキャッシュミスはもちろんですが、現代的なプロセッサでは次に実行される命令を先行して実行し始める「投機的実行」という技術を採用しており、投機的実行していた命令もすべてキャンセルしなければなりません。その数は10～20にもなります。

効率的な条件分岐は、プログラムの実行速度を大幅に向上させるために重要です。

一例として、プログラム内で複数の条件分岐がある場合、最も発生確率が高い条件を先に評価することで、プログラムの実行効率を向上させることを意図したコードを挙げてみます。これは、プログラムが最も一般的なケースを先に処理し、レアなケースを後にすることで、投機的実行がうまくいく確率を高めるということです。

改善前

def process_data(data):
    if data < 10:
        # レアケース
        return data + 10
    elif data >= 10 and data <= 20:
        # より一般的なケース
        return data * 2
    else:
        # 最も一般的なケース
        return data - 5

# データの処理を行う
result = process_data(15)
print(result)

この例では、最も一般的な（最も頻繁に起こる）ケースが最後に評価されています。

改善後

def process_data_optimized(data):
    if data > 20:
        # 最も一般的なケースを先に
        return data - 5
    elif data >= 10:
        # 次に一般的なケース
        return data * 2
    else:
        # レアケースを最後に
        return data + 10

# データの処理を行う
result_optimized = process_data_optimized(15)
print(result_optimized)

この最適化後の例では、最も一般的なケースを先に評価するように条件分岐の順序を変更しています。これにより、プログラムが最も頻繁に実行するパスを高速化し、全体の実行速度を改善します。

実はこのコードはあまり効果を感じないかもしれません。
現代のプロセッサには高度な分岐予測アルゴリズムが組み込まれており、これによって分岐（条件分岐）の結果を事前に予測し、予測先の命令を投機的実行するためです。分岐予測が成功すれば、無駄な待ち時間を削減し、プログラムの実行速度を向上させることが可能になっています。

しかし、条件分岐の順序変更による最適化の効果は、分岐予測の効率に依存します。分岐予測の精度向上を意識したプログラム上の工夫を組み合わせれば、条件分岐の順序を最適化することは依然として有効な場合があります。特に、以下のような工夫が有効になる可能性があります：

• 分岐の確率を偏らせる：条件AとBが50％ずつの割合で成立する場合、分岐予測は難しくなります。しかし、条件Aは90％、条件Bは10％で成立するように書き換えることができたら、分岐予測の成功率を高めることができます。ループ処理は分岐確率が偏っている典型的なケースです。

• 分岐の数を減らす：分岐が非常に多く、分岐予測アルゴリズムのキャッシュ容量を超える場合、予測ミスが増加する可能性があります。このような場合、条件分岐を単純化しましょう。複数条件にせず、if-else の２条件でできないか、などです。複数条件の場合は、次のテーブルルックアップを検討します。

• 分岐を計算に変える：分岐が少ないアルゴリズムはないか検討します。また再計算すれば分岐が減らせるケースもあります。ループ内の無駄な処理の最適化と矛盾しますが、計算が単純で分岐のペナルティの方が重い場合はトータルでは高速化されることもあります。

テーブルルックアップによる最適化

テーブルルックアップによる最適化は、個人的にはもっと活用されるべきだと思っている手法です。
この手法は、複雑な条件分岐の代わりに、キーと値のペアを持つデータ構造（例えば、Pythonの辞書）を使用して、条件に応じた結果やアクションを迅速に検索することに基づいています。特に状態や条件に基づいて異なるアクションを選択する必要がある場合に有効です。

以下に、テーブルルックアップによる最適化の例を示します。

以下の例では、ユーザーからの入力に基づいて異なる数学的オペレーションを実行する簡単なプログラムを考えます。テーブルルックアップを使用することで、複数のif-elif-else分岐の代わりに、オペレーションを効率的に選択できます。

# オペレーションのテーブルルックアップを定義
operations = {
    'add': lambda x, y: x + y,
    'subtract': lambda x, y: x - y,
    'multiply': lambda x, y: x * y,
    'divide': lambda x, y: x / y if y != 0 else 'Error: Division by zero'
}

# ユーザー入力を処理する関数
def perform_operation(operation, x, y):
    # 指定されたオペレーションをテーブルから検索し、実行する
    if operation in operations:
        result = operations[operation](x, y)
        return result
    else:
        return "Error: Unknown operation"

# オペレーションの実行例
print(perform_operation('add', 10, 5))  # 出力: 15
print(perform_operation('subtract', 10, 5))  # 出力: 5
print(perform_operation('multiply', 10, 5))  # 出力: 50
print(perform_operation('divide', 10, 0))  # 出力: Error: Division by zero

この例では、operationsという辞書を使用して、各演算子（'add', 'subtract', 'multiply', 'divide'）に対応する関数（lambda式）をマッピングしています。ユーザーが操作を指定すると、その操作名をキーとしてoperations辞書を検索し、対応する関数を呼び出して結果を返します。これにより、複雑なif-elif-else構造を使用する代わりに、コードの可読性を向上させ、実行効率を高めることができます。

テーブルルックアップでなぜ高速化されるのでしょう。それは、辞書のアクセスは条件分岐を使わず、平均的な時間計算量が低いハッシュ関数を用いた、効率的な方法だからです。

しかし、辞書の検索操作は平均的にはO(1)の時間計算量で効率的です。これは、キーからハッシュ値を計算し、そのハッシュ値を使用して値が格納されている場所を直接参照することで実現されます。
対照的に、複数のif-elif-else条件分岐を使用する場合、プログラムは条件を一つずつ評価し一致するまで進める必要があります。最悪のシナリオではO(n)の時間計算量になります（nは条件の数）。

前節の言い方で言うと「分岐を計算に変える」ことによる高速化ともいえます。

テーブルルックアップは特に条件数が多いときに力を発揮します。高速化だけでなく、プログラムの構造を簡素化し、メンテナンスを容易にすることにも効果がありますので、まだ使ったことがない方は一度お試しください。

やり過ぎに注意

高速化によりパフォーマンスが改善されてくると次も次もやりたくなってきます。しかし、これらのテクニックを適用する際は、常にプログラムの可読性とメンテナンス性を考慮し、パフォーマンス改善のためにコードの明確さを犠牲にしすぎないよう注意しましょう。常にパフォーマンスを測定して必要性を検討しながら進めることもお忘れなく。

また、コード変更が楽しくなってしまい次々とテクニックを投入したものの、実際にこれらの最適化を行う効果はなかった、なんて経験もありますが、この話はまたの機会に。

これにて御免！

（見出し画像は Canva で作ってみました）