最新技術やプログラム、デザインなど様々な情報を提供するサイト

プログラミング
suzukiiichiro

Ｎクイーン問題（６６） Python-codonで高速化

N-Queens エイト・クイーン アルゴリズム 鈴木維一郎 python codon

Ｎクイーン問題（６６） Python-codonで高速化の画像

ソースコード

今回の連載 python/pypy/codonのソースコードディレクトリはこちら
https://github.com/suzukiiichiro/N-Queens/tree/master/10Bit_Python

Ｎクイーン問題 過去記事アーカイブ

【過去記事アーカイブ】Ｎクイーン問題 過去記事一覧
https://suzukiiichiro.github.io/search/?keyword=Ｎクイーン問題
【Github】エイト・クイーンのソース置き場 BashもJavaもPythonも！
https://github.com/suzukiiichiro/N-Queens

python/pypy/codon について

Pythonはとにかく遅いです。
でもコーディングをしていて楽しいし、きれいなソースを書かないと動かないので、誰が書いたpythonコードであっても読みやすいです。さらに広範なバリエーションのモジュールをインストールすればほとんど苦労せずにあらゆるアルゴリズムを使うことができます。ただ遅いんです。

そこで、python高速化を追求した人がいました。

Pythonの実行を高速化する方法を一覧でまとめてみた
https://qiita.com/yuki_2020/items/36da0281c8af5c2c745f

どうやらcodonなるものを使うと驚きの速さでpythonが実行できるようです。ではまずはPythonのインストールを済ませ、プログラミング協議会定番のpypyの構築、そして最終段階でcodonのインストールを説明していきます。

次回からはこれまでのN-QueeensのPyhonコードをcodon化していきます。
なぜpypyを飛ばすのか。。。それは、pypyはpythonのコードに全く手を入れることなく高速化できるから、特別奥義は必要ないのです。

# 通常のpythonコードの実行
$ python <filename.py>

# pypyのpythonコードの実行
$ pypy <filename.py>

pypyは１０倍程度の高速化が見込めます。
再帰に限定されますが、ソースの冒頭に以下の追記するとpypyコードはさらに高速化されます

# pypyで再帰が高速化できる
import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')

codonに関しては以下のリンクが参考になります。

あなたのPythonを100倍高速にする技術 / Codon入門
https://zenn.dev/turing_motors/articles/e23973714c3ecf

pythonのインストール

以下のwhichコマンドでpythonがインストールされていないようであれば、

$ which python

以下を参考にpythonをインストールします
pyenvでのインストールが慣例のようです。

git clone git://github.com/yyuu/pyenv.git ~/.pyenv
echo 'export PYENV_ROOT="$HOME/.pyenv"' >> ~/.bashrc
echo 'export PATH="$PYENV_ROOT/bin:$PATH"' >> ~/.bashrc
echo 'eval "$(pyenv init -)"' >> ~/.bashrc
source ~/.bashrc

Python環境のインストール. 共有ライブラリもインストールします

$ CONFIGURE_OPTS=--enable-shared pyenv install 3.10.10

pythonのversionsの確認

$ pyenv versions

* system (set by /home/suzuki/.pyenv/version)
  3.10.0

pyenvでは全ての環境（global）とローカル環境(local)それぞれにpythonのバージョンを指定してインストールすることができます。

3.10.0 をglobalのデフォルトにして確認

$ pyenv global 3.10.0
$ pyenv versions
  system
* 3.10.0 (set by /home/suzuki/Github/.python-version)

必要なモジュールはpipコマンドで追加インストールします

$ sudo python3 -m ensurepip
$ sudo python3 -m pip install psutil

pypy のインストール

PyPy（パイパイ）は、プログラミング言語Pythonの実装の1つで、CPython（通常のPython）よりも高速に動作する処理系です。

【特徴】
Pythonで記述されたPythonの処理系（セルフホスティング）
CPythonとの互換性に重点を置いている
Just-in-Time（JIT）コンパイルというシステムを使って高速化されている
競技プログラミング分野で目にすることが度々ある

【仕組み】
CPythonのサブセットであるRPythonを使って実装されている
RPythonは制限付きのCPythonで実装されたPython処理系
JITコンパイルは何度も使われるコードを最適化するため、Pythonのコードでもかなり早く動かすことができる

【利点】
速度、メモリ使用量、サンドボックス、並列性で優れている
Pythonの標準ライブラリやサードパーティライブラリと互換性がある

pyenvでPyPyをインストールする
https://zenn.dev/3w36zj6/scraps/2b32292c31aec2

pypyのインストール
$ wget https://pypy.org/download.html
https://downloads.python.org/pypy/pypy3.11-v7.3.18-linux64.tar.bz2
bunzip2 -d pypy3.11-v7.3.18-linux64.tar bz2
tar xvf pypy3.11-v7.3.18-linux64.tar
$ sudo mv pypy3.11-v7.3.18-linux64 /usr/local/
$ cd /usr/local/pypy3.11-v7.3.18-linux64/bin
$ sudo ln -s /usr/local/pypy3.11-v7.3.18-linux64/bin/pypy /usr/bin/pypy

現在のpythonを確認

[suzuki@ip-172-31-14-193 Github]$ pyenv versions
  system
* 3.10.0 (set by /home/suzuki/Github/.python-version)
  pypy3.10-7.3.17

デフォルトのpythonをpypyにする

[suzuki@ip-172-31-14-193 Github]$ pyenv local pypy3.10-7.3.17
[suzuki@ip-172-31-14-193 Github]$ pyenv versions
  system
  3.10.0
* pypy3.10-7.3.17 (set by /home/suzuki/Github/.python-version)

確認

[suzuki@ip-172-31-14-193 Github]$ pypy -V
Python 3.10.14 (39dc8d3c85a7, Aug 27 2024, 14:32:27)
[PyPy 7.3.17 with GCC 10.2.1 20210130 (Red Hat 10.2.1-11)]
[suzuki@ip-172-31-14-193 Github]$

codon のインストール

codonの関連リンクを紹介しながら説明していきます。

あなたのPythonを100倍高速にする技術 / Codon入門
https://zenn.dev/turing_motors/articles/e23973714c3ecf

３行まとめ
高性能で簡単に扱えるPythonコンパイラ「Codon」
CodonはPythonコードをネイティブなマシンコードにコンパイル
Pythonとの互換性がありながら、CやC++に匹敵する高速化を実現
実際にPythonコードが100倍速くなることを検証
Codonの開発はGithub上で行われている

Github: codon
https://github.com/exaloop/codon

# codonのインストール
$ /bin/bash -c "$(curl -fsSL https://exaloop.io/install.sh)"
$ echo 'export PATH="$HOME/.codon/bin:$PATH"' >> ~/.bashrc

# 共有ライブラリを環境変数に設定します
$ echo 'export CODON_PYTHON=$PYENV_ROOT/versions/3.10.10/lib/libpython3.10.so' >> ~/.bashrc
$ source ~/.bashrc

codonの実行

元のpythonコード

def fib(n):
  # n未満のフィボナッチ数列を全てprintします
  a, b = 0, 1
  while a < n:
    print(a, end=' ')
    a, b = b, a+b
  print()
fib(1000)

２種類の実行方法があります。
runで実行すると実行ファイルを生成することなく実行します。

$ codon run fib.py
# 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987

build で実行すると実行ファイルを生成します。実行するには./で実行します。

$ codon build fib.py
$ ./fib

さらに
-release で実行するとコードを最適化してコンパイルします。
結果高速化されます。

$ codon build  -release fib.py && ./fib
# 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987

ここまではソースコードに全く手を入れることなく実行してきました。
pypyと同様に、codonも手を入れることなく動きますが、手を入れることによってもっともっと高速に実行することができます。

手を入れることなく動くのは、厳格なpythonコード表記で書かれている場合です。pythonは曖昧な言語なので、多少の間違いは良いように解釈して実行してくれます。codonはそういった曖昧さを厳格なソースに書き換えることで、ほぼC言語/C++言語と同等の速度でPythonコードを実行することができます。

次回からは実際のN-Queensソースコードを次から次へとcodon化して行きます。

ソースコード

今回の連載 python/pypy/codonのソースコードディレクトリはこちら
https://github.com/suzukiiichiro/N-Queens/tree/master/10Bit_Python

Ｎクイーン問題 過去記事アーカイブ

【過去記事アーカイブ】Ｎクイーン問題 過去記事一覧
https://suzukiiichiro.github.io/search/?keyword=Ｎクイーン問題
【Github】エイト・クイーンのソース置き場 BashもJavaもPythonも！
https://github.com/suzukiiichiro/N-Queens

Ｎクイーン問題（６９）Python-codonで高速化 03Python_backTracking
https://suzukiiichiro.github.io/posts/2025-03-06-01-n-queens-suzuki/
Ｎクイーン問題（６８）Python-codonで高速化 02Python_postFlag
https://suzukiiichiro.github.io/posts/2025-03-05-03-n-queens-suzuki/
Ｎクイーン問題（６７）Python-codonで高速化 01Python_bluteForce"
https://suzukiiichiro.github.io/posts/2025-03-05-02-n-queens-suzuki/
Ｎクイーン問題（６６）Python-codonで高速化
https://suzukiiichiro.github.io/posts/2025-03-05-01-n-queens-suzuki/
Ｎクイーン問題（６５） Ｎ２５を解決！事実上の日本一に
https://suzukiiichiro.github.io/posts/2024-04-25-01-n-queens-suzuki/
Ｎクイーン問題（６４）第七章 並列処理 キャリーチェーン ＮＶＩＤＩＡ ＣＵＤＡ編
https://suzukiiichiro.github.io/posts/2023-08-01-05-n-queens-suzuki/
Ｎクイーン問題（６３）第七章 並列処理 キャリーチェーン ＮＶＩＤＩＡ ＣＵＤＡ編
https://suzukiiichiro.github.io/posts/2023-08-01-05-n-queens-suzuki/
Ｎクイーン問題（６２）第七章 並列処理 対称解除法 ビットボード ＮＶＩＤＩＡ ＣＵＤＡ編
https://suzukiiichiro.github.io/posts/2023-08-01-04-n-queens-suzuki/
Ｎクイーン問題（６１）第七章 並列処理 対称解除法 ノードレイヤー ＮＶＩＤＩＡ ＣＵＤＡ編
https://suzukiiichiro.github.io/posts/2023-08-01-03-n-queens-suzuki/
Ｎクイーン問題（６０）第七章 並列処理 ミラー ＮＶＩＤＩＡ ＣＵＤＡ編
https://suzukiiichiro.github.io/posts/2023-08-01-02-n-queens-suzuki/
Ｎクイーン問題（５９）第七章 並列処理 ビットマップ ＮＶＩＤＩＡ ＣＵＤＡ編
https://suzukiiichiro.github.io/posts/2023-08-01-01-n-queens-suzuki/
Ｎクイーン問題（５８）第六章 並列処理 pthread C言語編
https://suzukiiichiro.github.io/posts/2023-06-28-09-n-queens-suzuki/
Ｎクイーン問題（５７）第八章 キャリーチェーン C言語編
https://suzukiiichiro.github.io/posts/2023-06-28-08-n-queens-suzuki/
Ｎクイーン問題（５６）第八章 ミラー C言語編
https://suzukiiichiro.github.io/posts/2023-06-28-06-n-queens-suzuki/
Ｎクイーン問題（５５）第八章 ビットマップ C言語編
https://suzukiiichiro.github.io/posts/2023-06-28-05-n-queens-suzuki/
Ｎクイーン問題（５４）第八章 ビットマップ C言語編
https://suzukiiichiro.github.io/posts/2023-06-28-04-n-queens-suzuki/
Ｎクイーン問題（５３）第八章 配置フラグ C言語編
https://suzukiiichiro.github.io/posts/2023-06-28-03-n-queens-suzuki/
Ｎクイーン問題（５２）第八章 バックトラック C言語編
https://suzukiiichiro.github.io/posts/2023-06-28-02-n-queens-suzuki/
Ｎクイーン問題（５１）第八章 ブルートフォース C言語編
https://suzukiiichiro.github.io/posts/2023-06-28-01-n-queens-suzuki/
Ｎクイーン問題（５０）第七章 マルチプロセス Python編
https://suzukiiichiro.github.io/posts/2023-06-21-04-n-queens-suzuki/
Ｎクイーン問題（４９）第七章 マルチスレッド Python編
https://suzukiiichiro.github.io/posts/2023-06-21-03-n-queens-suzuki/
Ｎクイーン問題（４８）第七章 シングルスレッド Python編
https://suzukiiichiro.github.io/posts/2023-06-21-02-n-queens-suzuki/
Ｎクイーン問題（４７）第七章 クラス Python編
https://suzukiiichiro.github.io/posts/2023-06-21-01-n-queens-suzuki/
Ｎクイーン問題（４６）第七章 ステップＮの実装 Python編
https://suzukiiichiro.github.io/posts/2023-06-16-02-n-queens-suzuki/
Ｎクイーン問題（４５）第七章 キャリーチェーン Python編
https://suzukiiichiro.github.io/posts/2023-06-16-01-n-queens-suzuki/
Ｎクイーン問題（４４）第七章　対象解除法 Python編
https://suzukiiichiro.github.io/posts/2023-06-14-02-n-queens-suzuki/
Ｎクイーン問題（４３）第七章　ミラー Python編
https://suzukiiichiro.github.io/posts/2023-06-14-01-n-queens-suzuki/
Ｎクイーン問題（４２）第七章　ビットマップ Python編
https://suzukiiichiro.github.io/posts/2023-06-13-05-n-queens-suzuki/
Ｎクイーン問題（４１）第七章　配置フラグ Python編
https://suzukiiichiro.github.io/posts/2023-06-13-04-n-queens-suzuki/
Ｎクイーン問題（４０）第七章　バックトラック Python編
https://suzukiiichiro.github.io/posts/2023-06-13-03-n-queens-suzuki/
Ｎクイーン問題（３９）第七章　バックトラック準備編 Python編
https://suzukiiichiro.github.io/posts/2023-06-13-02-n-queens-suzuki/
Ｎクイーン問題（３８）第七章　ブルートフォース Python編
https://suzukiiichiro.github.io/posts/2023-06-13-01-n-queens-suzuki/
Ｎクイーン問題（３７）第六章 C言語移植 その１７ pthread並列処理完成
https://suzukiiichiro.github.io/posts/2023-05-30-17-n-queens-suzuki/
Ｎクイーン問題（３６）第六章 C言語移植 その１６ pthreadの実装
https://suzukiiichiro.github.io/posts/2023-05-30-16-n-queens-suzuki/
Ｎクイーン問題（３５）第六章 C言語移植 その１５ pthread実装直前版完成
https://suzukiiichiro.github.io/posts/2023-05-30-15-n-queens-suzuki/
Ｎクイーン問題（３４）第六章 C言語移植 その１４
https://suzukiiichiro.github.io/posts/2023-05-30-14-n-queens-suzuki/
Ｎクイーン問題（３３）第六章 C言語移植 その１３
https://suzukiiichiro.github.io/posts/2023-05-30-13-n-queens-suzuki/
Ｎクイーン問題（３２）第六章 C言語移植 その１２
https://suzukiiichiro.github.io/posts/2023-05-30-12-n-queens-suzuki/
Ｎクイーン問題（３１）第六章 C言語移植 その１１
https://suzukiiichiro.github.io/posts/2023-05-30-11-n-queens-suzuki/
Ｎクイーン問題（３０）第六章 C言語移植 その１０
https://suzukiiichiro.github.io/posts/2023-05-30-10-n-queens-suzuki/
Ｎクイーン問題（２９）第六章 C言語移植 その９
https://suzukiiichiro.github.io/posts/2023-05-30-09-n-queens-suzuki/
Ｎクイーン問題（２８）第六章 C言語移植 その８
https://suzukiiichiro.github.io/posts/2023-05-30-08-n-queens-suzuki/
Ｎクイーン問題（２７）第六章 C言語移植 その７
https://suzukiiichiro.github.io/posts/2023-05-30-07-n-queens-suzuki/
Ｎクイーン問題（２６）第六章 C言語移植 その６
https://suzukiiichiro.github.io/posts/2023-05-30-06-n-queens-suzuki/
Ｎクイーン問題（２５）第六章 C言語移植 その５
https://suzukiiichiro.github.io/posts/2023-05-30-05-n-queens-suzuki/
Ｎクイーン問題（２４）第六章 C言語移植 その４
https://suzukiiichiro.github.io/posts/2023-05-30-04-n-queens-suzuki/
Ｎクイーン問題（２３）第六章 C言語移植 その３
https://suzukiiichiro.github.io/posts/2023-05-30-03-n-queens-suzuki/
Ｎクイーン問題（２２）第六章 C言語移植 その２
https://suzukiiichiro.github.io/posts/2023-05-30-02-n-queens-suzuki/
Ｎクイーン問題（２１）第六章 C言語移植 その１
N-Queens問://suzukiiichiro.github.io/posts/2023-05-30-01-n-queens-suzuki/
Ｎクイーン問題（２０）第五章 並列処理
https://suzukiiichiro.github.io/posts/2023-05-23-02-n-queens-suzuki/
Ｎクイーン問題（１９）第五章 キャリーチェーン
https://suzukiiichiro.github.io/posts/2023-05-23-01-n-queens-suzuki/
Ｎクイーン問題（１８）第四章 エイト・クイーンノスタルジー
https://suzukiiichiro.github.io/posts/2023-04-25-01-n-queens-suzuki/
Ｎクイーン問題（１７）第四章　偉人のソースを読む「Ｎ２４を発見 Ｊｅｆｆ Ｓｏｍｅｒｓ」
https://suzukiiichiro.github.io/posts/2023-04-21-01-n-queens-suzuki/
Ｎクイーン問題（１６）第三章　対象解除法 ソース解説
https://suzukiiichiro.github.io/posts/2023-04-18-01-n-queens-suzuki/
Ｎクイーン問題（１５）第三章　対象解除法 ロジック解説
https://suzukiiichiro.github.io/posts/2023-04-13-02-nqueens-suzuki/
Ｎクイーン問題（１４）第三章　ミラー
https://suzukiiichiro.github.io/posts/2023-04-13-01-nqueens-suzuki/
Ｎクイーン問題（１３）第三章　ビットマップ
https://suzukiiichiro.github.io/posts/2023-04-05-01-nqueens-suzuki/
Ｎクイーン問題（１２）第二章　まとめ
https://suzukiiichiro.github.io/posts/2023-03-17-02-n-queens-suzuki/
Ｎクイーン問題（１１）第二章　配置フラグの再帰・非再帰
https://suzukiiichiro.github.io/posts/2023-03-17-01-n-queens-suzuki/
Ｎクイーン問題（１０）第二章　バックトラックの再帰・非再帰
https://suzukiiichiro.github.io/posts/2023-03-16-01-n-queens-suzuki/
Ｎクイーン問題（９）第二章　ブルートフォースの再帰・非再帰
https://suzukiiichiro.github.io/posts/2023-03-14-01-n-queens-suzuki/
Ｎクイーン問題（８）第一章　まとめ
https://suzukiiichiro.github.io/posts/2023-03-09-01-n-queens-suzuki/
Ｎクイーン問題（７）第一章　ブルートフォース再び
https://suzukiiichiro.github.io/posts/2023-03-08-01-n-queens-suzuki/
Ｎクイーン問題（６）第一章　配置フラグ
https://suzukiiichiro.github.io/posts/2023-03-07-01-n-queens-suzuki/
Ｎクイーン問題（５）第一章　進捗表示テーブルの作成
https://suzukiiichiro.github.io/posts/2023-03-06-01-n-queens-suzuki/
Ｎクイーン問題（４）第一章　バックトラック
https://suzukiiichiro.github.io/posts/2023-02-21-01-n-queens-suzuki/
Ｎクイーン問題（３）第一章　バックトラック準備編
https://suzukiiichiro.github.io/posts/2023-02-14-03-n-queens-suzuki/
Ｎクイーン問題（２）第一章　ブルートフォース
https://suzukiiichiro.github.io/posts/2023-02-14-02-n-queens-suzuki/
Ｎクイーン問題（１）第一章　エイトクイーンについて
https://suzukiiichiro.github.io/posts/2023-02-14-01-n-queens-suzuki/

書籍の紹介

Ｎクイーン問題（６７）Python-codonで高速化 01Python_bluteForce

Ｎクイーン問題（６７）Python-codonで高速化 01Python_bluteForce
Ｎクイーン問題（６５） Ｎ２５を解決！事実上の日本一に

Ｎクイーン問題（６５） Ｎ２５を解決！事実上の日本一に

suzukiiichiro

鈴木維一郎 /慶應義塾大学大学院特別研究講師(常勤) /RPG Rogue日本語版開発者 /遠隔操作リモートデスクトップ特許発明者 /離散数学研究開発者 /自然言語処理研究開発者/ 人工知能学会/情報処理学会

「suzukiiichiro」のコンテンツ一覧

サイト内検索