Go

Golangでアナグラム2(未完成)

お題

子どもの宿題で「Frankenstein」に含まれる文字を使って別の英単語をできるだけたくさん見つけるというものが出されたので、プログラムで解いてみようと思った。
前回は、当初予定していた単語「Frankenstein」(12字)を試す前の「Frankenste」(10字)の時点で 88秒 かかり、12字の方はメモリが足りず計測不可だった。
今回は、とりあえず無駄なループ数を減らす対応をしてみる。

開発環境

前回踏襲

実践

■無駄なループ数を減らす

前回のは、最初に単語を与えられたら、その文字数分のループを繰り返し、重複する単語は(重複を受け付けない(=重複分が追加されても無視される))セットを定義して追加していく方式にした。
例えば、「ant」なら「a」「n」「t」に分割し、1字ずつループで処理していく中で、「a」の1字につき、さらにループで「a」「n」「t」を1字ずつループ処理し、これまたさらに「a」1字につき、ループで「a」「n」「t」を処理するため、3字なら3✕3✕3=27回ループが回る。
その結果、「Frankenstein」どころか「Frankenste」(10字)で10✕10✕...✕10=100億回ループとなり、さすがにけっこうな時間がかかる結果となった。

今回は、10字なら10字でループを回すのはいいとして、1字ピックアップしたら、その1字に加える1字を選択するループは10字を回すのではなく(選択した1字を除いた)9字を回す方式にした。ただ、それだけ。
こうすると、先の「ant」なら3✕2✕1=6回ループとなり、前回の方式の4分の1程度のループ数に減らせる。
「Frankenste」(10字)にしても、10✕9✕8✕...✕1=3,628,800回ループとなり、段違いにループ回数を減らせる。

実装

ソースの全量は下記。
https://github.com/sky0621/compito/blob/7a224c28f55b84ded52456b4e1e397643fdde062/main.go

まあ、単純で、再帰で組み合わせをセットに格納していくたびに、スライスを今処理中の字を除くものにしていくだけ。

func addWord(set *set, characters []string, parentChar string) {
    chLen := len(characters)
    for i, c := range characters {
        set.add(fmt.Sprintf("%s%s", parentChar, c))
        cpCharacters := make([]string, chLen, chLen)
        copy(cpCharacters, characters)
        addWord(set, getRemaining(cpCharacters, i), fmt.Sprintf("%s%s", parentChar, c))
    }
}

func getRemaining(characters []string, index int) []string {
    if characters == nil {
        return nil
    }
    if len(characters) <= index {
        return nil
    }

    before := characters[:index]
    after := characters[index+1:]
    return append(before, after...)
}

結果

◆「Frankenste」(10字)

===========================
最初から単語の組み合わせ作成まで 11.876701秒
最初から最後の標準出力まで       20.184065秒
===========================

組み合わせの作成の処理時間が前回の8分の1になった。

◆「Frankenstei」(11字)

前回は試していないけど、もう1字追加するとどれくらいかかるか。

===========================
最初から単語の組み合わせ作成まで 151.009902秒
最初から最後の標準出力まで       271.952606秒
===========================

パフォーマンス改善したと言っても、やはり1字追加でここまで変わる。

◆「Frankenstein」(12字)

11字の結果から、やはりダメな気がするけど、最後に「Frankenstein」(12字)を試してみる。

$ go run main.go Frankenstein
word:Frankenstein
aryWords:[a e e f i k n n n r s t]

signal: killed

ダメだった。

まとめ

ループ数を減らしてパフォーマンス改善したものの、12字を解析するにはメモリの問題でまだ不足。
goroutine使う案も少し試してみたもののメモリ使う意味では解決せずなので、いよいよローカル端末では限界か。。。