puzzle-generator-cy

本ソースコード公開の方針

方針

元々Javaのナンプレの問題の自動生成プログラムを公開していた。 このところ、Pythonが著しく普及してきたので、Python版を用意した。 しかし、Pythonは非常に遅くて、スピードが必要なプログラムには向かない。 それで、Pythonにちょっと手を加えるだけで100倍ほど高速にすることができるCythonというものがあり、ここで紹介する。

Python + C 　→　Cython

PythonをちょっとC的にしたもので、限りなくPythonのままと言ってもよい。 変更しているのは、遅さの原因になっているナンプレの問題を解く部分（ソルバー）のところだけで、その他は同じである。 そのため、Pythonのところで詳しく説明したことは省略するので、Pythonのところの説明を読んで欲しい。

Cythonのプログラムを理解する前に、PythonをCythonにするだけで100倍程高速になることを、まず体感して欲しい。

説明しないこと

Python版で説明してあることは省略する。 違いの部分についてだけ説明する。

---

プログラムについて

ナンプレ(数独)の問題をCythonで自動生成するためのプログラムの小さなセット

以下、Linuxの場合について説明する。

Python(Cython)プログラム

237 NP.py
168 generator.py
  9 parameter.py
 62 solution.py
  5 setup.py
299 solver.pyx
 78 合計

solver.pyをCythonに書き直したものがsolver.pyxで、60行だけ長くなっているが、たったそれだけで100倍高速になっている。 solver.py も含まれているが、Cythonのソースのsolver.pyxが含まれていると、Cythonが優先されて、solver.pyは無視される。

setup.pyは、Cythonのプログラムをコンパイルするために利用する。

メインモジュールはNP.pyです。Pythonのときと同じ。

Problem500.txt	問題サンプル500問
Pattern500.txt		問題ヒントパターン500問分

HeartQ.txt		ハートの形の問題
HeartP.txt		ハートの形のヒントパターン

18P.txt			ヒント数18のパターン数種
17P.txt			ヒント数17のパターン数種

Cythonのインストール

Cython$ pip install cython

Cythonプログラムのコンパイル

Cython$ python3 setup.py build_ext --inplace

コンパイルすると、solver.cppとsolver.cpython-38-x86_64-linux-gnu.soができる。

Cythonのインストールとコンパイルについては、 「実行するだけ」で、やや詳しく説明する。 「ナンプレ自動生成説明書」で、もっと詳しく説明する。

実行

Cython$ python3 NP.py
===== arguments input error =====
python3  NP.py  -s  problem_file   [answer_file]
python3  NP.py  -g  pattern_file   [problem_file]

-sで問題を解く、-gで問題を作ることを指示する。 その直後のファイルが、問題ファイルまたは問題パターンファイルとなる。 問題を解いた結果の解、あるいは作成された問題をファイルに出力したい場合には、出力ファイルを指定する。 画面上には、解あるいは問題の表示と、途中経過が示される。

詳細はドキュメントを参照のこと。

実行するだけの場合は、「実行するだけ」を参照のこと。

---

実行するだけ Cython版

とりあえず、動かしてみたい人のため説明です。 実行環境は、Linux/Ubuntuとして説明します。 その他の場合は、自分で調べてください。（頑張って！）

準備

CythonはPythonのコンパイル版で、そのため若干の準備が必要です。 既にPythonが実行できるものとします。 Pythonのバージョンは３とし、コマンドは python3 を用います。

まず、cythonのインストールが必要です。

以下でCythonをインストールできます。 $ pip install cython

インストールできていたら、Cythonのバージョンを確認しましょう。

$ cython -V
Cython version 0.29.24

GitHub

GitHubから、Cython版のソースとデータをダウンロードしてください。 一応、Cythonというフォルダの下にソースを置き、そこにデータのフォルダを置いてください。

Cython$ tree
.
├── NP.py
├── data
│   ├── 17P.txt
│   ├── 18P.txt
│   ├── 20P.txt
│   ├── 22P.txt
│   ├── 24P.txt
│   ├── HeartP.txt
│   ├── HeartQ.txt
│   ├── Pattern500.txt
│   └── Problem500.txt
├── generator.c(*)
├── generator.py
├── parameter.py
├── setup.py
├── solution.py
├── solver.cpp(*)
├── solver.cpython-38-x86_64-linux-gnu.so(*)
├── solver.py
└── solver.pyx

(*)ファイルは、最初は無いけれど、Cythonのコンパイルによりできます。

C:\Users\fuji\Desktop\ナンプレ>java -jar NP.jar
===== arguments input error =====
java -jar NP.jar  -s  problem_file	[answer_file]
java -jar NP.jar  -g  pattern_file	[problem_file]

パラメータなしでNP.pyを起動すると、上記のように入力形式を表示します。 パラメータにエラーがある場合も、上記の表示になります。

データを、GitHubの配置と同じで、dataフォルダに置いた状態になっているとします。

コンパイル

Cythonのソースファイル solver.pyx は、Pythonの solver.py を書き直し（書き加え）したものです。とりあえず、このファイルをコンパイルし、使えるようにします。

コンパイルでいちいちCythonのソースファイルを指定するのは面倒なので、setup.py にコンパイル時にあれこれ指定しなくて良いようにしておきました。

Cython$ cat setup.py
from distutils.core import setup
from Cython.Build import cythonize

setup(ext_modules=cythonize(['solver.pyx']))

コンパイルは、常に次の１行で実行できます。

Cython$ python3 setup.py build_ext --inplace

あれこれ表示されますが、問題なければ次の２つのファイルができていれば準備完了です。

solver.cpp
solver.cpython-38-x86_64-linux-gnu.so

問題を解く

パラメータ −s は問題を解く(solve)指示です。 −gは問題を生成する(generate)指示です。 -sに引き続いて、問題ファイルを与えると、問題を解きます。

正常な問題を解く

Cython$ python3 NP.py -s data/HeartQ.txt
Heart   H 20
- - - - - - - - -
- 1 6 - - - 5 9 -
4 - - 3 - 7 - - 2
7 - - - 5 - - - 1
8 - - - - - - - 9
- 6 - - - - - 7 -
- - 5 - - - 6 - -
- - - 2 - 3 - - -
- - - - 7 - - - -
0
2 8 7 5 1 9 4 3 6
3 1 6 4 2 8 5 9 7
4 5 9 3 6 7 1 8 2
7 9 4 8 5 2 3 6 1
8 3 1 7 4 6 2 5 9
5 6 2 9 3 1 8 7 4
9 7 5 1 8 4 6 2 3
6 4 8 2 9 3 7 1 5
1 2 3 6 7 5 9 4 8

Total 1	Success 1
Time    0.000248 sec

最後に

• 与えられた問題数
• きちんと解けた問題数
• 全体の計算時間（秒単位）

を表示します。

問題と答えの間にある数字（この場合は０）は、解けきれなかったマス数を示します。 きちんと解ければ、０になります。 正の数になった場合は、解けきれなかったマス（空白ます「−」）の数を示し、多重解の問題になってしまったことが分かります。

解ききれない問題（多重解の問題）を解く

次の例は、正しい問題の数字を一箇所だけ変更したものです。 すると、残りマス数が23になり、最後の成功数が0になっています。

Python$ python3 NP.py -s data/Heart1Q.txt
Heart   H 20
- - - - - - - - -
- 1 6 - - - 5 9 -
4 - - 1 - 7 - - 2
7 - - - 5 - - - 1
8 - - - - - - - 9
- 6 - - - - - 7 -
- - 5 - - - 6 - -
- - - 2 - 3 - - -
- - - - 7 - - - -
23
- 8 7 5 - 9 1 4 6
- 1 6 - - - 5 9 7
4 5 9 1 6 7 8 3 2
7 9 - - 5 - - 6 1
8 - - 7 - 6 - 5 9
5 6 - 9 - - - 7 8
9 7 5 - - - 6 2 3
6 4 8 2 9 3 7 1 5
1 - - 6 7 5 9 8 4

Total 1	Success 0
Time    0.000239 sec

エラーの場合

さらに、問題の同じマスの値を変更してみます。

Cython$ cat data/Heart2Q.txt
Heart   H 20
- - - - - - - - -
- 1 6 - - - 5 9 -
4 - - 8 - 7 - - 2
7 - - - 5 - - - 1
8 - - - - - - - 9
- 6 - - - - - 7 -
- - 5 - - - 6 - -
- - - 2 - 3 - - -
- - - - 7 - - - -

これで実行すると、以下のようになりました。 現バージョンでは、エラーの場合は、問題を表示しません。ちょっと不親切ですね。

Cython$ python3 NP.py -s data/Heart2Q.txt
Heart   H 20
ERROR
Total 1	Success 0
Time    0.000064 sec

問題を作る

−gオプション付きでパターンファイルを与えると、パターンを表示後、*を次々と表示します。 *１つが、試行錯誤(TRY)1回を示します。

Python$ python3 NP.py -g data/HeartP.txt
No.1   H 20
- - - - - - - - -
- X X - - - X X -
X - - X - X - - X
X - - - X - - - X
X - - - - - - - X
- X - - - - - X -
- - X - - - X - -
- - - X - X - - -
- - - - X - - - -
******************************************************************************************SUCCESS  TRY 89
- - - - - - - - -
- 9 1 - - - 6 3 -
8 - - 1 - 5 - - 2
5 - - - 6 - - - 7
7 - - - - - - - 8
- 8 - - - - - 1 -
- - 3 - - - 5 - -
- - - 8 - 2 - - -
- - - - 7 - - - -

total 1  failure 0
Time    8.757475 sec

この例では、89回の再トライで成功しました。 最も少ない場合は、*１つで成功し、 TRY 0 と表示されます。

次の例は、

Cython$ python3 NP.py -g data/ImpossibleP.txt
No.1   H 17
- - - - - - - X X
- - - - - - - - -
- - X X X - - - -
- - X - - X - - -
- - X - - - X - -
- - - X - X - X -
- - - - X - X - -
X - - - - X - - -
X - - - - - - - -
****************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************FAILURE

total 1  failure 1
Time    37.166832 sec

このパターンでは、多数回試してもだめで、あきらめてしまいました。 現在は、400回試してだめだったらあきらめ、FAILUREと表示します。

このパターンは、このプログラムには組み込んでいない手筋を使って解く・作るプログラムでは、以下のような問題を作ることができます。

問題を連続して解く

ナンプレ500問が１つのファイルになっているProblem500.txtの問題を解いてみます。

Cython$ python3 NP.py -s data/Problem500.txt
No.1   H 18
- - - - 8 - - - -
- - - 9 - 7 - - -
4 2 - - - - 3 - -
- - 7 - - 9 - - -
- 8 - - - - - 3 -
- - - 1 - - 4 - -
- - 2 - - - - 8 7
- - - 3 - 4 - - -
- - - - 5 - - - -
0
7 9 3 4 8 2 1 6 5
5 6 1 9 3 7 8 2 4
4 2 8 5 1 6 3 7 9
1 3 7 8 4 9 6 5 2
9 8 4 2 6 5 7 3 1
2 5 6 1 7 3 4 9 8
3 4 2 6 9 1 5 8 7
8 7 5 3 2 4 9 1 6
6 1 9 7 5 8 2 4 3

No.2   H 18
- 8 - - - - 6 - -
- 9 - 1 - - - 3 -
- - - 5 - - - - -
- - - - - 7 3 - -
- - 1 - - - 8 - -
- - 5 4 - - - - -
- - - - - 6 - - -
- 3 - - - 8 - 4 -
- - 2 - - - - 1 -
0
1 8 3 9 7 4 6 2 5
5 9 6 1 8 2 4 3 7
2 4 7 5 6 3 1 8 9
9 6 4 8 2 7 3 5 1
3 2 1 6 9 5 8 7 4
8 7 5 4 3 1 9 6 2
4 1 8 7 5 6 2 9 3
7 3 9 2 1 8 5 4 6
6 5 2 3 4 9 7 1 8


◇　◇　中略　◇　◇


No.500   H 24
- - 2 3 - - - - -
- - 4 - - 5 - - -
- - - - - 6 - 1 8
- 2 8 5 - 7 - - 6
- - - - - - - - -
7 - - 6 - 1 5 9 -
9 5 - 7 - - - - -
- - - 2 - - - - -
- - - - - 3 7 - -
0
8 9 2 3 1 4 6 7 5
6 1 4 8 7 5 9 2 3
3 7 5 9 2 6 4 1 8
1 2 8 5 9 7 3 4 6
5 6 9 4 3 2 1 8 7
7 4 3 6 8 1 5 9 2
9 5 1 7 6 8 2 3 4
4 3 7 2 5 9 8 6 1
2 8 6 1 4 3 7 5 9

Total 500	Success 500
Time    0.106554 sec

一気に解いて、500問で0.106554秒、1問平均で213マイクロ秒の速度で解きました。

ヒント数が18〜24個の問題500問の問題集です。

あまりにも高速に解くので、時間計測が正しくなるように、一気に解きながら解を記憶し（表示しない）、解いたときの経過時間を記憶しています。 解き終えてから、問題と解を示し、最後に経過時間を表示しています。 これは、解く時間に比べて表示の時間が圧倒的に長いための措置です。

Python版	10.892606 sec
Cython版	0.106554 sec

となっているので、PythonをCythonにしたことで、100倍高速になったことが分かります。

問題を連続して作る

ヒント数24

問題集の数字を全てXにしたパターンファイルがPattern500.txtです。 Java版はこれで試しましたが、Python版は遅いので、とりあえるヒント数24個の問題が６問入ったファイル24P.txtで試してみます。

Python$ python3 NP.py -g data/24P.txt
o.1   H 24
- X - - - X - - -
X - - X - - X - -
- - X - - - - X X
- - - - X - - X X
- - - X - X - - -
X X - - X - - - -
X X - - - - X - -
- - X - - X - - X
- - - X - - - X -
*SUCCESS  TRY 0
- 6 - - - 1 - - -
7 - - 3 - - 4 - -
- - 1 - - - - 9 5
- - - - 7 - - 2 1
- - - 4 - 5 - - -
1 5 - - 6 - - - -
8 1 - - - - 3 - -
- - 9 - - 8 - - 2
- - - 7 - - - 6 -

No.2   H 24
- - X X - - - - -
- X - - - - X X -
- X - - X - - - X
- - - - X - - - X
- - X X - X X - -
X - - - X - - - -
X - - - X - - X -
- X X - - - - X -
- - - - - X X - -
*SUCCESS  TRY 0
- - 8 9 - - - - -
- 3 - - - - 1 4 -
- 1 - - 2 - - - 7
- - - - 7 - - - 1
- - 9 6 - 4 8 - -
6 - - - 8 - - - -
4 - - - 6 - - 1 -
- 7 1 - - - - 3 -
- - - - - 8 4 - -

No.3   H 24
X - - - - X X X -
- - X - - - - - X
- X - - X - - - X
- - - X - - - - X
- - X - - - X - -
X - - - - X - - -
X - - - X - - X -
X - - - - - X - -
- X X X - - - - X
*SUCCESS  TRY 0
4 - - - - 2 9 3 -
- - 1 - - - - - 8
- 7 - - 5 - - - 4
- - - 8 - - - - 5
- - 7 - - - 8 - -
1 - - - - 9 - - -
7 - - - 2 - - 1 -
5 - - - - - 6 - -
- 8 9 4 - - - - 7

No.4   H 24
X - - - - X - - X
- X - X - - X - -
- - - - X - - X -
- X - - - X - - X
- - X - - - X - -
X - - X - - - X -
- X - - X - - - -
- - X - - X - X -
X - - X - - - - X
*SUCCESS  TRY 0
1 - - - - 6 - - 4
- 4 - 2 - - 7 - -
- - - - 7 - - 9 -
- 8 - - - 5 - - 6
- - 9 - - - 1 - -
6 - - 8 - - - 7 -
- 7 - - 6 - - - -
- - 3 - - 1 - 4 -
5 - - 9 - - - - 1

No.5   H 24
- - - - - X X - -
- - - - - X - X -
- - X X - - X X -
- X - X - - - - -
- X X - - - X X -
- - - - - X - X -
- X X - - X X - -
- X - X - - - - -
- - X X - - - - -
**SUCCESS  TRY 1
- - - - - 2 5 - -
- - - - - 4 - 6 -
- - 3 6 - - 4 9 -
- 1 - 9 - - - - -
- 3 7 - - - 2 8 -
- - - - - 6 - 5 -
- 7 6 - - 5 3 - -
- 9 - 8 - - - - -
- - 4 7 - - - - -

No.6   H 24
- - X X - - - - -
- - X - - X - - -
- - - - - X - X X
- X X X - X - - X
- - - - - - - - -
X - - X - X X X -
X X - X - - - - -
- - - X - - X - -
- - - - - X X - -
*SUCCESS  TRY 0
- - 5 6 - - - - -
- - 8 - - 1 - - -
- - - - - 3 - 1 4
- 4 2 7 - 6 - - 3
- - - - - - - - -
1 - - 4 - 5 9 7 -
3 6 - 9 - - - - -
- - - 2 - - 8 - -
- - - - - 7 3 - -

total 6  failure 0
Time    0.192325 sec

失敗(failure)は0です。ヒント数24の問題を6問作成して、0.1923秒で終えました。 1問あたり0.032秒(32ミリ秒)で作れています。 Python版が、1問あたり2.9秒だったので約100倍の速度になっています。 なお、問題自動生成は、乱数を使っていて、早く成功したり、しっぱいし続けるのが偶然置きてしまうので、正確な比較はできません。

ヒント数22

ヒント数22の問題を50問のパターンファイル 22P.txt

Cython$ python3 NP.py -g data/22P.txt
No.1   H 22
- X - - - X X - -
X - - - X - - - -
- - - - X - - - X
- - - X - - - - X
- X X - - - X X -
X - - - - X - - -
X - - - X - - - -
- - - - X - - - X
- - X X - - - X -
***SUCCESS  TRY 2
- 9 - - - 4 7 - -
3 - - - 7 - - - -
- - - - 1 - - - 5
- - - 6 - - - - 9
- 8 2 - - - 4 1 -
1 - - - - 5 - - -
4 - - - 8 - - - -
- - - - 5 - - - 2
- - 5 3 - - - 6 -

◇　◇　中略　◇　◇

No.50   H 22
- X - - - - - - X
X - X - - - X - -
- X - - - X - X -
- - - - X - X - -
- - - X - X - - -
- - X - X - - - -
- X - X - - - X -
- - X - - - X - X
X - - - - - - X -
****SUCCESS  TRY 3
- 6 - - - - - - 2
8 - 7 - - - 4 - -
- 4 - - - 2 - 3 -
- - - - 9 - 2 - -
- - - 7 - 5 - - -
- - 5 - 8 - - - -
- 7 - 2 - - - 6 -
- - 1 - - - 3 - 5
9 - - - - - - 1 -

total 50  failure 0
Time    4.623455 sec

失敗(failure)は0です。ヒント数22の問題を50問作成して、4.62秒で終えました。 1問あたり0.092秒(92ミリ秒)で作れています。 Python版は680秒かかっていたので、100倍以上高速になっているようです。

失敗(failure)は0です。ヒント数22の問題を50問作成して、680秒で終えました。

ヒント数20

ヒント数20の問題を38問のパターンファイル 20P.txt

Python$ python3 NP.py -g data/20P.txt
No.1   H 20
X X - - - - - - X
- - - - - - - - X
- - - X X - - - -
- - - X - X X - -
- - X - - - X - -
- - X X - X - - -
- - - - X X - - -
X - - - - - - - -
X - - - - - - X X
****SUCCESS  TRY 3
6 2 - - - - - - 4
- - - - - - - - 2
- - - 7 8 - - - -
- - - 2 - 1 3 - -
- - 9 - - - 1 - -
- - 8 9 - 7 - - -
- - - - 5 6 - - -
1 - - - - - - - -
8 - - - - - - 9 7

◇　◇　中略　◇　◇

No.38   H 20
- - X - - - - - -
X - - X - - - - -
- X - - X - - - X
X - - X - - - X -
- - X - - - X - -
- X - - - X - - X
X - - - X - - X -
- - - - - X - - X
- - - - - - X - -
*********************************SUCCESS  TRY 32
- - 8 - - - - - -
1 - - 6 - - - - -
- 7 - - 5 - - - 9
5 - - 4 - - - 1 -
- - 9 - - - 6 - -
- 3 - - - 8 - - 7
6 - - - 3 - - 5 -
- - - - - 9 - - 8
- - - - - - 1 - -

total 38  failure 0
Time    54.341966 sec

失敗(failure)は0です。ヒント数20の問題を38問作成して、54.34秒で終えました。 1問あたり1.43秒(1430ミリ秒)で作れています。 Python版は4510秒かかっていたので、83倍ほど高速になっているようです。

500問連続生成

では、500問のパターンファイルで、一気に500問を自動生成してみよう。

Cython$ python3 NP.py -g data/Pattern500.txt
No.1   H 18
- - - - X - - - -
- - - X - X - - -
X X - - - - X - -
- - X - - X - - -
- X - - - - - X -
- - - X - - X - -
- - X - - - - X X
- - - X - X - - -
- - - - X - - - -
**********************SUCCESS  TRY 21
- - - - 3 - - - -
- - - 5 - 9 - - -
4 6 - - - - 7 - -
- - 5 - - 1 - - -
- 9 - - - - - 4 -
- - - 8 - - 6 - -
- - 9 - - - - 5 1
- - - 6 - 3 - - -
- - - - 4 - - - -

No.2   H 18
- X - - - - X - -
- X - X - - - X -
- - - X - - - - -
- - - - - X X - -
- - X - - - X - -
- - X X - - - - -
- - - - - X - - -
- X - - - X - X -
- - X - - - - X -
***SUCCESS  TRY 2
- 7 - - - - 8 - -
- 6 - 3 - - - 5 -
- - - 2 - - - - -
- - - - - 9 6 - -
- - 1 - - - 7 - -
- - 3 4 - - - - -
- - - - - 7 - - -
- 1 - - - 8 - 4 -
- - 4 - - - - 3 -

◇　◇　中略　◇　◇

*SUCCESS  TRY 0
- - - - - 3 6 - -
- - - - - 6 - 1 -
- - 8 4 - - 5 9 -
- 5 - 9 - - - - -
- 6 1 - - - 2 7 -
- - - - - 4 - 6 -
- 1 5 - - 2 3 - -
- 2 - 7 - - - - -
- - 6 8 - - - - -

No.500   H 23
- - X X - - - - -
- - X - - X - - -
- - - - - X - X X
- X X X - X - - X
- - - - - - - - -
X - - X - X X X -
X X - X - - - - -
- - - X - - - - -
- - - - - X X - -
*SUCCESS  TRY 0
- - 4 5 - - - - -
- - 7 - - 6 - - -
- - - - - 3 - 7 1
- 6 1 2 - 8 - - 9
- - - - - - - - -
8 - - 9 - 7 4 5 -
1 2 - 6 - - - - -
- - - 4 - - - - -
- - - - - 5 6 - -

total 500  failure 0
Time    319.108195 sec

失敗(failure)は0です。500問の作成を319秒で終えました。 1問あたり638ミリ秒(0.638秒)で作れていますので、かなり高速に作成できています。 Python版は時間がかかり過ぎたので、途中で放棄しています。

問題作成の難易度（失敗のしやすさ）は、パターンによってかなり違います。 ヒント数が少なくなることも、作りにくくします。

このような感じで、問題を作成することができます。

問題ファイルをパターンファイルとして使用

実は、問題ファイルを、そのままパターンファイルとして利用することができます。 同じファイルを、-s で動かすと、指定されたファイルを問題ファイルとして実行します。 -g で動かすと、マスが - になっていない箇所は全てヒントマスの指定と解釈して解きます。

Cython$ cat data/HeartQ.txt
Heart   H 20
- - - - - - - - -
- 1 6 - - - 5 9 -
4 - - 3 - 7 - - 2
7 - - - 5 - - - 1
8 - - - - - - - 9
- 6 - - - - - 7 -
- - 5 - - - 6 - -
- - - 2 - 3 - - -
- - - - 7 - - - -

Cython$ python3 NP.py -g data/HeartQ.txt
No.1   H 20
- - - - - - - - -
- X X - - - X X -
X - - X - X - - X
X - - - X - - - X
X - - - - - - - X
- X - - - - - X -
- - X - - - X - -
- - - X - X - - -
- - - - X - - - -
*************SUCCESS  TRY 12
- - - - - - - - -
- 3 9 - - - 2 7 -
8 - - 6 - 4 - - 5
5 - - - 8 - - - 7
3 - - - - - - - 6
- 9 - - - - - 4 -
- - 2 - - - 9 - -
- - - 3 - 5 - - -
- - - - 4 - - - -

total 1  failure 0
Time    1.599556 sec

Cythonは、Pythonに比べて約100倍高速になりました。 パズルだけでなく、色々な遅いPythonのプログラムをCythonに手直しして、高速なプログラムに直しましょう。