入門者が、Python プログラムの高速化に挑戦する。

以前 Python3 で数独のプログラムを作りました。
https://blog.goo.ne.jp/espiya/e/31cfcafc2c57e4b98612fbe10b9266ad

しかし、Raspberry Piなので非常に実行時間がかかってしまいました。そこで、このプログラムを Cython に直して実行してみることにしました。
Python3 プログラムの中から、関数定義部分を取り出して Cython に変換すると思うのですが、ここで生成AIを利用することにします。

プロンプトは単純で、
「以下のPythonプログラムを高速化するために、Cythonプログラムに変換してください。
　（以下、import itertools　と　関数定義をいれました。） 」

Google　Gemini　と Microsoft Copilot で試してみましたが、うまく行きませんでした。
詳しくは書きませんが、今回のプログラムのように関数の引数にリストを使うと変換されたCythonプログラムが何故かエラーになってしまうのです。

そこで　プログラムの中で１から９までの数字が重複無く含まれているかを判定する関数に狙いをつけてPythonプログラムを修正することにしました。

つまり、

def check_list(b):
  """
  リストbの要素が重複なく1から9まで含まれているかを判定する関数
  Args:
    b: 判定対象のリスト
  Returns:
    bool: 条件を満たす場合はTrue、満たさない場合はFalse
"""

  # 要素数が9でない場合、Falseを返す
  if len(b) != 9:
    return False

  # 要素が1から9の範囲に含まれていないか、重複があるかを確認
  return set(b) == set(range(1, 10))

の関数を高速化すれば、プログラムが高速化できそうです。
やはり、set()が遅いのかもしれません。そこで、引数のリストの長さは９に固定なので判定は省略して、
VAL　という「タプル」を用意（２のi乗にしてみました。０番目（値が入っていない状態）だけ０にしました。タプルを作るときに括弧で囲っていません。
これで、すべての要素を加えて 511 になるかどうかをチェックすることにしました。
ちょっと怪しいアルゴリズムのような気がしますが、可能性のある解はすべて出力するので、その中で正しいものを選べるので大丈夫です。

def check_list(b):
  VAL = 0, 1, 2, 4, 8, 16, 32, 64, 128, 256
  check_v = VAL[b[0]] + VAL[b[1]] + VAL[b[2]] + VAL[b[3]] + VAL[b[4]] + VAL[b[5]] + VAL[b[6]] + VAL[b[7]] + VAL[b[8]]

  # 要素が1から9の範囲に含まれていないか、重複があるかを確認
  return check_v == 511

プログラムの速度を比較してみます。が、以前の問題は遅いので、もう少し簡単な３分ぐらいで解ける問題を探してそれに変更しました。

$ time python3 sudoku.py
Question:
0 6 0 | 0 9 0 | 0 8 0
3 0 0 | 0 5 0 | 0 9 4
0 9 4 | 0 6 0 | 5 7 0
------+-------+-------
0 0 7 | 0 0 0 | 9 0 0
9 0 0 | 1 0 5 | 0 2 6
0 5 0 | 9 2 0 | 4 0 0
------+-------+-------
7 0 5 | 4 0 9 | 2 0 1
8 2 9 | 0 1 0 | 0 4 7
4 0 0 | 3 7 2 | 0 0 9

..........　途中省略　................

5 6 2 | 7 9 4 | 1 8 3
3 7 8 | 2 5 1 | 6 9 4
1 9 4 | 8 6 3 | 5 7 2
------+-------+-------
2 4 7 | 6 3 8 | 9 1 5
9 8 3 | 1 4 5 | 7 2 6
6 5 1 | 9 2 7 | 4 3 8
------+-------+-------
7 3 5 | 4 8 9 | 2 6 1
8 2 9 | 5 1 6 | 3 4 7
4 1 6 | 3 7 2 | 8 5 9
=== END ===

real 2m58.681s
user 2m58.445s
sys 0m0.128s

$ time python3 sudoku-mod.py
Question:
,,,,,,,,,,　途中省略　,,,,,,,,,,,,,,,,,,,,,,,

------+-------+-------
7 3 5 | 4 8 9 | 2 6 1
8 2 9 | 5 1 6 | 3 4 7
4 1 6 | 3 7 2 | 8 5 9
=== END ===

real 1m12.566s
user 1m12.377s
sys 0m0.093s

大体、２倍ぐらい速くなっています。やはり、縦とブロックが条件を満たしているかの判定が高速化の鍵を握っていますね。
この例では答えも一つで、一応修正はうまくいきました。

Pythonプログラム入門の一環なので、タプルを使ってみることができて良かったです。

まもなく、Python 3.13 のアップデートがあるので、その話題にも触れたいと思います。