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秒あたりだった。かなり遅い。まあ、前回書いたような「数分」ではないが（やはりプログラム実行の体感速度はあまりあてにならない・・・）。

まあこの段階ではあまり心配するところではない。

www.youtube.com

このビデオでも言っているように、"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を使う意味が・・・

というわけで、人間が覆面式を解く時に使うような、他の文字・数字との関連性に注目した制約ルールを利用する方法を考えてみる。（続く）

Arantium Maestum

プログラミング、囲碁、読書の話題

Python 覆面式ソルバー　続