ソート
前回で、大量の問題を並列処理で生成することができた。
でも、問題が生成される順序は、パターンの順番ではなく、問題が出来た順番なので、順番が入れ替わってしまう。入れ替えて正しい順序にしてから書き出す必要がある。
自分でソートの関数を作るのは面倒。でもそんな必要はなく、Pythonにはソートのための関数sorted()が用意されている。
リストgenproblemsに、出来上がった順にProblemオブジェクトが加えられる。
Problemクラスのindexが0から問題順の値が入っているので、この値を昇順になるように並べ替えれば、希望の順番になる。
並べ替える関数として、sort()とsorted()があるが、汎用性の高いsorted()を使ったほうが良いので、sort()は忘れよう。
sorted()は、第1引数にソートしたいもの(リストなど)を与えると、ソートされたリストが返ってくる。元のリストは変化しない。
ソートする時、Problemオブジェクトのindexの値によってソートするため、lamda関数を使ってキーの取り出し方を指定する。
では、実際のソート部分を見てみよう。
sortedproblems = sorted(genproblems,key=lambda x: x.index)問題ファイルの出力
まず、画面への出力のときにdataoutput(出力ファイルオブジェクト)へ出力していた部分を全て消す。
全問題の生成が終了したら、リストgenproblemsに全問のProblemオブジェクトが順不同で入っている。
dataoutputが設定されていたら、genproblemsをまずソートし、問題順に並んだProblemオブジェクトリストsortedproblemsを作り、その順番にProblemオブジェクトを参照しながら出力ファイルを書き出していく。
if dataoutput != None:
sortedproblems = sorted(genproblems,key=lambda x: x.index)
for pb in sortedproblems:
str = f"No.{pb.index+1} H {util.countHint(pb.pattern)}"
print(str,file=dataoutput)
if pb.retrycount >= 0:
util.printBoard(pb.problem,dataoutput)
else:
str = f"FAILURE {-pb.retrycount}"
print(str,file=dataoutput)以下に、最終版のgenerateNP()を示す。
def generateNP(filename):
global datainput, dataoutput
problems = util.readPatterns(filename)
genproblems = []
totalprobs = len(problems)
failureCount=0
successCount=0
sendCount = 0
recvCount = 0
start_time = time.perf_counter()
status = MPI.Status()
## 全ワーカーに問題を送りつける
for i in range(1,size):
if sendCount<totalprobs:
comm.send(problems[sendCount], dest=i, tag=1)
sendCount += 1
else:
comm.send("END", dest=i, tag=9)
while recvCount < totalprobs:
# パターンの送信、問題の受信
prob = comm.recv(source=MPI.ANY_SOURCE, tag=2, status=status)
recvCount += 1
worker = status.Get_source()
genproblems.append(prob)
if sendCount<totalprobs:
comm.send(problems[sendCount], dest=worker, tag=1)
sendCount += 1
else:
comm.send("END", dest=worker, tag=9)
print( f"No.{prob.index+1} H {util.countHint(prob.pattern)}" )
util.printHintBoard(prob.pattern)
if prob.retrycount >= 0:
print( f"r{prob.rank} [{prob.retrycount}] {prob.time:06f} sec" )
util.printBoard(prob.problem)
successCount += 1
else:
print( f"FAILURE {-prob.retrycount}" )
failureCount += 1
print()
print( f"length of genproblems = {len(genproblems)}" )
exe_time = time.perf_counter() - start_time
probSize = len(problems)
totalCount = successCount+failureCount
print( f"total {totalCount} failure {failureCount}\n" )
print( f"Time\t{exe_time:06f} sec\n" )
if dataoutput != None:
sortedproblems = sorted(genproblems,key=lambda x: x.index)
for pb in sortedproblems:
str = f"No.{pb.index+1} H {util.countHint(pb.pattern)}"
print(str,file=dataoutput)
if pb.retrycount >= 0:
util.printBoard(pb.problem,dataoutput)
else:
str = f"FAILURE {-pb.retrycount}"
ちょっと長くなっているが、難しいことはしていないので説明は省略する。
実行
$ mpiexec -hostfile host32 python3 NP_MPIGEN4.py -g data/Pattern500.txt prob.txt
No.6 H 19
- - - X - - - X -
- - X - - - - X -
- - X - - - - - X
- - X - - X - - -
- X - - X - - X -
- - - X - - X - -
X - - - - - X - -
- X - - - - X - -
- X - - - X - - -
r6 [1] 2.320428 sec
- - - 5 - - - 9 -
- - 8 - - - - 2 -
- - 3 - - - - - 6
- - 6 - - 8 - - -
- 2 - - 7 - - 1 -
- - - 3 - - 5 - -
5 - - - - - 8 - -
- 4 - - - - 7 - -
- 9 - - - 2 - - -
No.17 H 20
- X - - - - - X -
X - - - X - - - X
- - - X - - - - -
- - - - X - X - -
- X - X - X - X -
- - X - X - - - -
- - - - - X - - -
X - - - X - - - X
- X - - - - - X -
r17 [0] 2.074807 sec
- 8 - - - - - 7 -
6 - - - 4 - - - 8
- - - 2 - - - - -
- - - - 3 - 4 - -
- 7 - 1 - 9 - 2 -
- - 5 - 2 - - - -
- - - - - 7 - - -
4 - - - 5 - - - 7
- 1 - - - - - 8 -
No.9 H 19
X - - - - - - - -
- - - - - X X - -
X X - - - - X - -
X - - X - - X - -
- - - - X - - - -
- - X - - X - - X
- - X - - - - X X
- - X X - - - - -
- - - - - - - - X
r9 [0] 3.450197 sec
5 - - - - - - - -
- - - - - 2 1 - -
8 6 - - - - 7 - -
4 - - 6 - - 5 - -
- - - - 9 - - - -
- - 9 - - 3 - - 2
- - 2 - - - - 9 3
- - 7 8 - - - - -
- - - - - - - - 5
中略
No.304 H 19
- - - - - - X - -
- - - X - X - - -
X - X - - - X - -
- X - - - - - X -
- - - X - X - - -
- X - - X - - X -
- - X - - - X - X
- - - X - X - - -
- - X - - - - - -
r25 [221] 296.620231 sec
- - - - - - 6 - -
- - - 3 - 4 - - -
1 - 9 - - - 2 - -
- 7 - - - - - 4 -
- - - 1 - 6 - - -
- 3 - - 9 - - 8 -
- - 8 - - - 9 - 3
- - - 4 - 7 - - -
- - 5 - - - - - -
length of genproblems = 500
total 500 failure 0
Time 384.755112 sec
500問を384.755秒で作ったので、768ミリ秒/問題となる。
しかし、最後に出来上がったNo.304は、296秒もかかっている。全体で384秒なので、この問題が生成できるのをじっと待っていた感じである。
次が、問題ファイルprob.txt であり、きちんと問題番号順に並んでいる。
No.1 H 18
- - - - 9 - - - -
- - - 3 - 4 - - -
8 7 - - - - 2 - -
- - 3 - - 9 - - -
- 1 - - - - - 5 -
- - - 8 - - 7 - -
- - 6 - - - - 9 3
- - - 7 - 2 - - -
- - - - 1 - - - -
No.2 H 18
- 7 - - - - 4 - -
- 9 - 2 - - - 1 -
- - - 3 - - - - -
- - - - - 8 7 - -
- - 4 - - - 6 - -
- - 3 9 - - - - -
- - - - - 4 - - -
- 8 - - - 7 - 9 -
- - 5 - - - - 2 -
No.3 H 18
- - - - 6 - - - -
- - 7 5 - - - - -
5 - - - - - 3 6 -
3 8 - - - 9 - - -
- - - - - - - - -
- - - 4 - - - 5 7
- 4 5 - - - - - 9
- - - - - 2 8 - -
- - - - 3 - - - -
以下省略そして、出来上がった問題ファイル prob.txtを、元のプログラムで解いてみた。
$ python3 NP_ORG.py -s prob.txt
中略
No.500 H 23
- - 2 9 - - - - -
- - 4 - - 2 - - -
- - - - - 5 - 9 8
- 2 5 1 - 6 - - 9
- - - - - - - - -
9 - - 8 - 3 7 4 -
8 3 - 2 - - - - -
- - - 4 - - - - -
- - - - - 1 6 - -
0
5 8 2 9 1 7 3 6 4
6 9 4 3 8 2 5 1 7
7 1 3 6 4 5 2 9 8
4 2 5 1 7 6 8 3 9
3 7 8 5 9 4 1 2 6
9 6 1 8 2 3 7 4 5
8 3 7 2 6 9 4 5 1
1 5 6 4 3 8 9 7 2
2 4 9 7 5 1 6 8 3
Total 500 Success 500
Time 0.391458 sec作った問題がちゃんと解けるみたいだ。
１万問を連続生成
最後に、10000万問を連続して作成した例を示す。
でも、１万パターンを用意するのは大変なので、いままで使ってきた500問の分のパターンファイルを20回繰り返しつなげて１万パターンのファイルを作った。非常に横着な方法だが、これで一気に1万問の作成に挑戦することができる。
$ mpiexec -hostfile host32 python3 NP_MPIGEN4.py -g data/Pattern10000.txt prob10000.txt
中略
r14 [168] 224.996675 sec
- - 9 - - - - 3 1
- - - 7 - - - 6 9
- - - 5 - - - - -
- 1 3 - - - - - -
- - - - 6 - - - -
- - - - - - 8 7 -
- - - - - 1 - - -
4 7 - - - 9 - - -
8 5 - - - - 7 - -
No.9019 H 19
- - - - X - - - -
- X - X - - - X -
- - X - - - X - -
- - - X - X - X -
X - - - - - - - X
- X - X - X - - -
- - X - - - X - -
- X - - - - - X -
- - - - X - - - -
FAILURE 400
length of genproblems = 10000
total 10000 failure 14
Time 3243.363190 sec10000問も作ろうとすると、少々失敗もしたが、1問あたりの時間は324ミリ秒となった。
延々とナンプレでの並列処理について書いてきたが、もう読むのも飽きているのではないかと思う。書く方だって長くなり過ぎたなと思っているんだから。
ということで、次からはナンプレではない別のテーマで、まだ紹介していないMPIの機能を使った例を示そう。
＃人気の記事
＃タグ
