Skip to content

README.md

Latest commit

 

History

History
273 lines (202 loc) · 11.9 KB

README.md

File metadata and controls

273 lines (202 loc) · 11.9 KB

Python vs Rust パフォーマンス比較検証

English version: README_EN.md

このプロジェクトが答える問い

問い 答え
なぜPythonは遅いのか？ Pythonインタプリタが「ループ1周ごと」「関数呼び出し1回ごと」に動的型チェックとバイトコードディスパッチを行うから。同じロジックでRustの24〜84倍かかる。
外部ライブラリを使っても遅いのか？ いいえ。 NumPy等のネイティブライブラリに重い処理を委譲すれば、Rustと同等かそれ以上の速度が出る。Pythonの「遅さ」はインタプリタのループ/関数呼び出しに限定された問題であり、計算本体をC/Fortran層に渡せば解消する。

「Pythonは遅い」と言われる理由を、同一アルゴリズムの実行時間比較で定量的に検証するプロジェクト。

フェーズ一覧

フェーズ テーマ 状態
1 フィボナッチ数列（再帰） ✅ 完了
2 素数計算（エラトステネスの篩） ✅ 完了
3 行列積（N×N） ✅ 完了
4 文字列処理（回文判定） ✅ 完了

前提条件

  • Python 3.10以上
  • Rust (rustup経由でインストール): https://rustup.rs/
  • Visual Studio Build Tools 2022（MSVCリンカー）

セットアップ

# Python依存パッケージの一括インストール
pip install -r requirements.txt

実行方法

一括実行（推奨）

# PowerShellから実行
powershell -ExecutionPolicy Bypass -File run_benchmark.ps1

# または run.bat をダブルクリック
run.bat

個別実行

# Pure Python（純粋Python版）
python python/fibonacci.py
python python/sieve.py
python python/matrix.py
python python/palindrome.py

# Python + 最適化版（fix版）
python python/fix/fibonacci_lru.py
python python/fix/sieve_numpy.py
python python/fix/matrix_numpy.py
python python/fix/palindrome_regex.py
python python/fix/comparison_all.py    # 統合比較

# Rust（ワークスペース一括ビルド）
cd rust
cargo build --release
./target/release/fibonacci.exe
./target/release/sieve.exe
./target/release/matrix.exe
./target/release/palindrome.exe

プロジェクト構成

Python検証/
├── docs/
│   ├── 要件定義書.md
│   └── environment/
│       └── DxDiag.txt              # 実行環境のハードウェア情報
├── python/
│   ├── fibonacci.py                # フェーズ1: フィボナッチ（再帰）
│   ├── sieve.py                    # フェーズ2: エラトステネスの篩
│   ├── matrix.py                   # フェーズ3: 行列積
│   ├── palindrome.py               # フェーズ4: 回文判定
│   └── fix/                        # 最適化版（高速化手法の証明）
│       ├── comparison_all.py       # 統合比較ベンチマーク
│       ├── fibonacci_lru.py        # lru_cache版
│       ├── sieve_numpy.py          # NumPy版
│       ├── matrix_numpy.py         # NumPy版
│       └── palindrome_regex.py     # スライス版
├── rust/
│   ├── Cargo.toml                  # ワークスペース定義
│   ├── fibonacci/                  # フェーズ1
│   ├── sieve/                      # フェーズ2
│   ├── matrix/                     # フェーズ3
│   └── palindrome/                 # フェーズ4
├── results/                        # ベンチマーク結果ログ保存用
├── requirements.txt                # Python依存パッケージ
├── run_benchmark.ps1               # 一括実行スクリプト（PowerShell）
├── run.bat                         # ダブルクリックで実行できるバッチファイル
└── README.md

各ベンチマークの解説

フェーズ1: フィボナッチ数列（再帰）

フィボナッチ数列とは、前の2つの数を足して次の数を作る数列（0, 1, 1, 2, 3, 5, 8, 13...）。 N番目の値を求めるために「自分自身を2回呼び出す」再帰関数を使う。 N=40では約3.3億回の関数呼び出しが発生するため、関数を呼ぶコストそのものが計測できる。

fib(5) = fib(4) + fib(3)
       = (fib(3) + fib(2)) + (fib(2) + fib(1))
       = ... 爆発的に呼び出しが増える

何を測っているか: 関数呼び出し1回あたりのオーバーヘッド（フレーム生成・スタック操作）

フェーズ2: 素数計算（エラトステネスの篩）

素数とは、1と自分自身でしか割り切れない2以上の自然数のこと（2, 3, 5, 7, 11, 13...）。

エラトステネスの篩（ふるい） は、古代ギリシャの数学者エラトステネスが考案した、素数を高速に列挙するアルゴリズム。 「ふるい」の名前の通り、合成数（素数でない数）をふるい落として残ったものが素数、という仕組み。

アルゴリズムの流れ

  1. 2〜N までの数を全て「素数かもしれない」リストに入れる
  2. 最小の数（2）は素数確定 → 2の倍数（4, 6, 8...）を全て消す
  3. 次に残っている数（3）は素数確定 → 3の倍数（9, 12, 15...）を全て消す
  4. 次に残っている数（5）は素数確定 → 5の倍数（25, 30, 35...）を全て消す
  5. √N まで繰り返せば、残った数が全て素数
初期状態: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15...]

2の倍数を消す: [2, 3, ×, 5, ×, 7, ×, 9, ×, 11, ×, 13, ×, 15...]
3の倍数を消す: [2, 3, ×, 5, ×, 7, ×, ×, ×, 11, ×, 13, ×, ×...]
5の倍数を消す: [2, 3, ×, 5, ×, 7, ×, ×, ×, 11, ×, 13, ×, ×...]
→ 残り: 2, 3, 5, 7, 11, 13... が素数

本ベンチマークでは上限を1000万に設定し、664,579個の素数を列挙する。 このアルゴリズムは配列への大量の読み書きとループで構成されるため、 ループ1回ごとのインタプリタのオーバーヘッドと配列アクセスのコストが明確に現れる。

何を測っているか: ループ1周あたりのコスト、配列の読み書きパフォーマンス

フェーズ3: 行列積（N×N）

200×200の行列（数値の表）同士の掛け算。三重ループ（i, j, k）で8,000,000回の浮動小数点演算を行う。 科学計算や機械学習の基本となる処理で、最もCPUに負荷がかかるタイプの計算。

C[i][j] = A[i][0]*B[0][j] + A[i][1]*B[1][j] + ... + A[i][199]*B[199][j]
→ これを200×200 = 40,000要素すべてについて計算

何を測っているか: 数値演算の生スループット、ネストループでの累積オーバーヘッド

フェーズ4: 文字列処理（回文判定）

100文字の文字列が回文（前から読んでも後ろから読んでも同じ）かどうかを100万回判定する。 文字列の先頭と末尾から1文字ずつ比較するシンプルなロジック。

"abcba" → a==a, b==b → 回文
"abcde" → a!=e → 回文ではない

何を測っているか: 文字列オブジェクトの生成・アクセスコスト、GC（ガベージコレクション）の影響

検証結果

総合比較（3者）

フェーズ テーマ Pure Python 最適化版 Rust Pure→Rust
1 フィボナッチ（N=40） 12,000 ms 0.05 ms (lru_cache) 216 ms 55x
2 素数計算（上限1000万） 903 ms 20 ms (NumPy) 21 ms 43x
3 行列積（200×200） 478 ms 0.77 ms (NumPy) 6 ms 84x
4 回文判定（100万回） 1,021 ms 171 ms (slice) 43 ms 24x

考察

フェーズ1: フィボナッチ（55倍差）

  • 主因: 関数呼び出しのオーバーヘッド
  • Pythonは再帰のたびにフレームオブジェクトを生成し、動的型チェックを行う
  • Rustはスタック操作のみで関数呼び出しが完了する

フェーズ2: 素数計算（48倍差）

  • 主因: ループ処理のインタプリタオーバーヘッド
  • Pythonはバイトコード1命令ごとにディスパッチコストが発生する
  • 配列（リスト）アクセスもPythonではオブジェクト参照経由

フェーズ3: 行列積（84倍差）- 最大差

  • 主因: CPU密な数値計算での累積コスト
  • 三重ループで8,000,000回の浮動小数点演算、毎回型チェックが走る
  • Rustはコンパイラが自動ベクトル化（SIMD）を適用する可能性あり

フェーズ4: 回文判定（24倍差）- 最小差

  • 主因: 文字列アクセスとオブジェクト操作
  • Pythonの文字列インデックスアクセスは比較的最適化されている
  • それでも24倍の差がある（GC・参照カウントのオーバーヘッド）

結論

Pythonは同一ロジックで24〜84倍遅い。特にCPU密な計算やループが多いほど差が大きくなる。 これはPythonの動的型付け・インタプリタ実行モデルの本質的な特性であり、 NumPy等のネイティブライブラリを使わない純粋なPythonコードでは避けられないコストである。

補足検証: 純粋Python vs 最適化版

「Pythonが遅い」のは純粋なPythonコードに限った話であり、NumPyやlru_cache等の最適化手法を活用すれば劇的に高速化できることを証明する追加検証。

実行方法

pip install numpy
python python/fix/comparison_all.py

結果

テーマ 純粋Python 最適化版 高速化 使用したもの
フィボナッチ 11,809 ms 0.03 ms 468,595x functools.lru_cache
素数計算 894 ms 19 ms 47x NumPy配列スライス
行列積 465 ms 12 ms 39x numpy.matmul (BLAS)
回文判定 1,003 ms 143 ms 7x 文字列スライス s[::-1]

Rust vs Python（最適化版）の比較

テーマ Rust 最適化版 差 備考
フィボナッチ 216 ms 0.05 ms 最適化版が4,000倍速い ※アルゴリズム変更（メモ化）による高速化。純粋な言語性能比較ではない
素数計算 19 ms 19 ms ほぼ同等 NumPy配列スライスでループをC層に委譲
行列積 6 ms 0.77 ms 最適化版が8倍速い NumPy内部のBLAS（OpenBLAS）がSIMD+マルチスレッドで最適化
回文判定 43 ms 143 ms Rust が3倍速い スライスでもPythonのforループが残るため

⚠️ フィボナッチの注意点: lru_cache版は計算量がO(2^n)→O(n)に変わるアルゴリズム改善であり、 「最適化ライブラリだから速い」のではなく「メモ化で重複計算を排除したから速い」。 Rust側でも同じメモ化を実装すれば同等の速度になる。他の3つは同一アルゴリズムでの純粋な比較。

結論

  • 純粋Pythonは確かに遅い（Rustの24〜84倍遅い）
  • しかし適切な最適化手法を活用すれば、Rustとほぼ同等の性能が出るケースもある
  • 特にNumPyの行列演算はBLAS（C/Fortran実装）を内部で呼ぶため、Rustの素朴な実装と同等以上
  • 「Pythonが遅い」の正体はPythonインタプリタのループ・関数呼び出しが遅いのであって、重い処理をネイティブライブラリに委譲すれば問題にならない

実行環境

  • OS: Windows 11 Pro
  • CPU: AMD Ryzen 7 7735HS with Radeon Graphics
  • RAM: 30 GB
  • Python: 3.13.12
  • Rust: 1.96.0 (ac68faa20 2026-05-25)
  • ビルド: cargo build --release（最適化あり）