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

ソースコード

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

インストールなどの構築はこちら

Ｎクイーン問題（６６） Python-codonで高速化
https://suzukiiichiro.github.io/posts/2025-03-05-01-n-queens-suzuki/

バックトラッキングのcodon化

今回も前回に引き続きcodon化の実例を行います。
今回はバックトラックのPython版をcodon化したものを解説します。
では、実行順に見ていきましょう。
前回、前々回で説明した内容と重複する箇所もありますが、なんども言われれば嫌でも覚えると思いますので、ここは我慢して読んでください。

まずは、ソースの最後尾にある__main__関数です。
codonを使うというのはpythonの高速化を目的としているわけで、少しでも効率的に、最適化された高速を追求している。ということを考えると、classをつかったり、リテラル変数やリストといったオブジェクトを束ねた構造化は高速化と省メモリに繋がります。そのうえで、ソース本体はclassかしてif __name__ == '__main__'を使ってclassを呼び出して処理を開始するのは効率的な省メモリと、見落としがちな変数やオブジェクトの初期化を効率的に行うことができます。

class NQueens03:
  total:int
  unique:int
  aboard:list[int]
  fa:list[int]
  fb:list[int]
  fc:list[int]
  def __init__(self):
    pass
  def init(self,size:int):
    self.total=0;
    self.unique=0;
    self.aboard=[0 for i in range(size)];
    self.fa=[0 for i in range(2*size-1)];
    self.fb=[0 for i in range(2*size-1)];
    self.fc=[0 for i in range(2*size-1)];
:
:
# 3.バックトラック
# $ python <filename>
# $ pypy <fileName>
# $ codon build -release <filename>.py && ./<filename>
# 15:      2279184            0         0:00:16:449
if __name__ == '__main__':
  NQueens03().main();

class ＜class名>: で開始されたclassは __main__から

if __name__ == '__main__':
  NQueens03().main();

で呼び出されます。
NQueens03()クラスの内部関数main()を呼び出して実行しています。
NQueens03()は呼び出された瞬間にNQueens03クラスのコンストラクタdef __init__(self):を呼び出します。
def __init__(self):関数のの中身はpassの一行のみです。
passは「なにもせずに素通り」を意味します。

次に def main(self):を見てきます。

  def main(self):
    min:int=4;
    max:int=18
    print(" N:        Total       Unique         hh:mm:ss.ms")
    for size in range(min,max):
      self.init(size)
      start_time=datetime.now();
      self.nqueens(0,size);
      time_elapsed=datetime.now()-start_time;
      text = str(time_elapsed)[:-3]  
      print(f"{size:2d}:{self.total:13d}{self.unique:13d}{text:>20s}")

この関数は、__main__のNQueens03().main()から呼び出されます。通常のpythonでは以下の様式で変数の宣言と初期化を同時に行います。 pythonの変数は方の宣言は不要なためです。ですので、代入される値を見て判断し、minとmax`はint型だな、と考えます。pythonも同様に判定します。

    min=4;
    max=18

codonではそういった曖昧な型付けを嫌います。
codonではC/C++のように変数の型を明示的に行う必要があります。

    min:int=4;
    max:int=18

その後、出力の項目ラベルを一行で出力し処理のためのforループに入ります。

      self.init(size)

は、コンストラクタとは別に用意した初期化関数init(self,size:int):を呼び出します。
ここでも通常のpythonでは以下のような様式で記述しますが

  def init(self,size):
    self.total=0;
    self.unique=0;

codonでは関数のパラメータにも厳格な型を要求します。以下の通り、size:intというふうに記述する必要があります。

  def init(self,size:int):
    self.total=0;
    self.unique=0;
    self.aboard=[0 for i in range(size)];
    self.fa=[0 for i in range(2*size-1)];
    self.fb=[0 for i in range(2*size-1)];
    self.fc=[0 for i in range(2*size-1)];

グローバル変数にはself.を使ってアクセスします。
関数パラメータのsizeにはself.を付与する必要はありません。

初期化などは包括表記を使うことで高速に初期化することができます。
pythonでは積極的に包括処理を使うことをおすすめします。
ただ、可読性が下がってしまうことに良いことはありません。

def main(self):で以下の行は計測を開始し、self.nqueens(0,size)を呼び出し、計測を終了する３行となります。
self.nqueens(0,size)で、nqueens()関数に２つの値、0とsize`を渡しています。

      start_time=datetime.now();
      self.nqueens(0,size);
      time_elapsed=datetime.now()-start_time;

def nqueens(self,row:int,size:int):関数では、２つの値を受け取ります。パラメータの数が３つありますが、第一パラメータは暗黙的にclass内の関数であることを振る舞うselfが指定されることになっています。
ですので、rowとsizeの２つ値は、selfの続いて記述します。
この２つの関数パラメータは上記で説明した通り、片付けを明示的に記述する必要があります。
python/pypyでは:から後ろはコメントとして処理されますので、幻覚に書いたソースはpython/pypyでも完全に動作します。

通常時からpythonでは片付けを厳格に明示化することをおすすめします。
最後に、def nqueens()関数は再帰関数です。
ソースのforループ内で自分自身を呼び出して処理を続行します。

  def nqueens(self,row:int,size:int):
    if row==size:
      self.total+=1;
    else:
      for i in range(size):
        self.aboard[row]=i;
        if self.fa[i]==0 and self.fb[row-i+(size-1)]==0 and self.fc[row+i]==0:
          self.fa[i]=self.fb[row-i+(size-1)]=self.fc[row+i]=1;
          self.nqueens(row+1,size);
          self.fa[i]=self.fb[row-i+(size-1)]=self.fc[row+i]=0;

完全なソースは以下のとおりです。

from datetime import datetime

# pypyを使う場合はコメントを解除
# pypyで再帰が高速化できる
# import pypyjit
# pypyjit.set_param('max_unroll_recursion=-1')

class NQueens03:
  total:int
  unique:int
  aboard:list[int]
  fa:list[int]
  fb:list[int]
  fc:list[int]
  def __init__(self):
    pass
  def init(self,size:int):
    self.total=0;
    self.unique=0;
    self.aboard=[0 for i in range(size)];
    self.fa=[0 for i in range(2*size-1)];
    self.fb=[0 for i in range(2*size-1)];
    self.fc=[0 for i in range(2*size-1)];
  def nqueens(self,row:int,size:int):
    if row==size:
      self.total+=1;
    else:
      for i in range(size):
        self.aboard[row]=i;
        if self.fa[i]==0 and self.fb[row-i+(size-1)]==0 and self.fc[row+i]==0:
          self.fa[i]=self.fb[row-i+(size-1)]=self.fc[row+i]=1;
          self.nqueens(row+1,size);
          self.fa[i]=self.fb[row-i+(size-1)]=self.fc[row+i]=0;
  def main(self):
    min:int=4;
    max:int=18
    print(" N:        Total       Unique         hh:mm:ss.ms")
    for size in range(min,max):
      self.init(size)
      start_time=datetime.now();
      self.nqueens(0,size);
      time_elapsed=datetime.now()-start_time;
      text = str(time_elapsed)[:-3] 
      print(f"{size:2d}:{self.total:13d}{self.unique:13d}{text:>20s}")

# 3.バックトラック
# $ python <filename>
# $ pypy <fileName>
# $ codon build -release <filename>.py && ./<filename>
# 15:      2279184            0         0:00:16:449
if __name__ == '__main__':
  NQueens03().main()

実行結果は以下のとおりです。

CentOS$ codon build -release 03Python_backTracking.py && ./03Python_backTracking
 N:        Total       Unique         hh:mm:ss.ms
 4:            2            0         0:00:00.000
 5:           10            0         0:00:00.000
 6:            4            0         0:00:00.000
 7:           40            0         0:00:00.000
 8:           92            0         0:00:00.000
 9:          352            0         0:00:00.000
10:          724            0         0:00:00.002
11:         2680            0         0:00:00.017
12:        14200            0         0:00:00.075
13:        73712            0         0:00:00.409
14:       365596            0         0:00:02.459
15:      2279184            0         0:00:16.093
16:     14772512            0         0:01:49.948
17:     95815104            0         0:13:07.511

次の章では、対象解除法の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で高速化 03Python_backTracking

ソースコード

インストールなどの構築はこちら

バックトラッキングのcodon化

ソースコード

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

書籍の紹介

suzukiiichiro

サイト内検索

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

ソースコード

インストールなどの構築はこちら

バックトラッキングのcodon化

ソースコード

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

書籍の紹介

Ｎクイーン問題（７０）Python-codonで高速化 04Python_symmetry

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

suzukiiichiro

サイト内検索

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