Golangでアナグラム2（未完成）

お題

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

開発環境

前回踏襲

実践

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

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

今回は、10字なら10字でループを回すのはいいとして、１字ピックアップしたら、その１字に加える１字を選択するループは10字を回すのではなく（選択した１字を除いた）9字を回す方式にした。ただ、それだけ。
こうすると、先の「ant」なら３✕２✕１＝６回ループとなり、前回の方式の４分の１程度のループ数に減らせる。
「Frankenste」(10字)にしても、１０✕９✕８✕．．．✕１＝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秒
===========================

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

◆「Frankenstei」(11字)

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

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

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

◆「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使う案も少し試してみたもののメモリ使う意味では解決せずなので、いよいよローカル端末では限界か。。。