Python 覆面式ソルバー 続
前回からの続き。
ということで高速化に取り組んでみる。
が、その前に、とりあえず短く書いたコードが実際どれくらいかかっているのか、数値化しておく。
import time def time_solver(input_string): start = time.time() solve(input_string) end = time.time() print(end - start) if __name__=='__main__': time_solver('SEND + MORE = MONEY') time_solver('WWWDOT + GOOGLE = DOTCOME')
私のノートだと最初の例題で30秒、実際の問題で70秒あたりだった。かなり遅い。まあ、前回書いたような「数分」ではないが(やはりプログラム実行の体感速度はあまりあてにならない・・・)。
まあこの段階ではあまり心配するところではない。
このビデオでも言っているように、"When you start with horrible code, you get major speed-ups"である。そもそもとりあえず正しく簡潔なコードから始めるのが正道。
本当はcProfileを使ってボトルネックを測ったりもしたいのだが、たぶんeval
を使っているせいでうまくいかない。たぶんそもそもそこが一番遅い。一旦コンパイルされたPython bytecodeではなく、テキストをそのままパースしているのでけっこう非効率。
というわけで、eval
に頼らない方法を考えてみる。
input stringに括弧を挿入したあと、分割して数字部分と演算子部分にわけて、数字部分は以前の通りstring.format
に辞書を渡してからint()
化、演算子はoperator.add
とoperator.sub
にマップして、最終的に等式が成り立つか評価する、という方法でいく。
bracketed_list = [bracket_letter(c) for c in input_string] bracketed_string = ''.join(bracketed_list)
この部分の後に
b1, op, b2, _, b3 = bracketed_string.split() operator = {'+':add, '-':sub}[op]
上記のコードを加え、if eval(output_string):
の代わりに
num1 = int(b1.format(**alpha_dict)) num2 = int(b2.format(**alpha_dict)) num3 = int(b3.format(**alpha_dict)) if operator(num1, num2) == num3:
上記のコードを入れる。ちなみにbracketed_string
は
'{S}{E}{N}{D} + {M}{O}{R}{E} = {M}{O}{N}{E}{Y}'
のような文字列になる。そこに{'S':1, 'E':2, 'N':3...}
といった辞書を.format(**dict)
で入力することで{S}が1に置換され、{E}が2に置換され、数字っぽい文字列にした時点でint()
で数値化する。
今回はeval
しないので等号を==
に修正する必要はない。
これで時間を測ってみると13秒と30秒くらいで、実行時間が半減したことになる。
string.format
ではなく10の倍数で掛け算をする方法もあるが、試しに書いてみたら非常にごちゃごちゃしてきて大してスピードも向上しなかったので割愛。
最終的に以下のようになる。
from string import ascii_letters from itertools import permutations from operator import add, sub def solve(input_string): bracketed_list = [bracket_letter(c) for c in input_string] bracketed_string = ''.join(bracketed_list) b1, operator, b2, _, b3 = bracketed_string.split() op = {'+':add, '-':sub}[operator] characters = set(c for c in input_string if (c in ascii_letters)) n1, _, n2, _, n3 = input_string.split() first_characters = [n[0] for n in (n1, n2, n3)] for numbers in permutations(range(10), len(characters)): alpha_dict = dict(zip(characters, numbers)) if any(alpha_dict[c]==0 for c in first_characters): continue num1 = int(b1.format(**alpha_dict)) num2 = int(b2.format(**alpha_dict)) num3 = int(b3.format(**alpha_dict)) if operator(num1, num2) == num3: output_string = bracketed_string.format( **alpha_dict) print(output_string) def bracket_letter(c): if c in ascii_letters: c = '{'+c+'}' return c
これで一分以内にどちらの問題も結果がでるようになる。しかし、もっと向上できるのではないだろうか。
今回やったような、ミクロな部分をさらに向上させて、一番コストがかかっている処理をより軽くすることもできる。しかし、この問題に関しては、むしろ「総当たり」という大戦略を変えるほうが結果が出しやすそうである。dict(zip(characters, numbers))
をやめて手動で文字と数字のマップを処理する、といったコーディングはめんどくさいしそもそもそれだったらPythonを使う意味が・・・
というわけで、人間が覆面式を解く時に使うような、他の文字・数字との関連性に注目した制約ルールを利用する方法を考えてみる。(続く)