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

お題

前回の続き。

開発環境

前回踏襲

実践

実装

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

■単語として存在しないことがわかっている分をあらかじめ除外するコードを追加

例えば「nn」のように、その時点で存在する単語がないとわかっているものを除外リストにあらかじめセットしておく。
与えられたワード（例として「Frankenstein」）から１字ずつ組み合わせていく過程で、除外リストに存在するものだった場合は、それ以上の組み合わせ処理を行わず、次の組み合わせを探すようにする。
これにより、ループ処理の回数が（除外リストに存在する分だけ）減らせるので、処理時間の短縮につながる。

除外リスト

今回は完全に「Frankenstein」に特化して除外リストの中身を決めている。
このリストの中身をどう決める（及びメンテナンスする）かは今時点では一旦置いておく。

func getExclusionList() []string {
    return []string{
        "ae",
        "afk", "afn", "afs", "atf", "atk", "ats",
        "ean", "eak", "ekn",
        "enna", "ennf", "ennk", "enns", "ennt",
        "fn", "fs", "fk",
        "frk", "ftr", "fta", "fte", "ftn", "fts", "fnn",
        "ias", "ika", "ikn", "ikr", "iks", "ikt", "ikf", "ifa", "ife", "ifk", "ifr", "ifs", "ift", "iea", "iet", "iek", "ief",
        "kt", "ks", "kf",
        "knn", "krn", "krf", "krt", "knf", "knt", "kns",
        "kren",
        "nn", "nk", "nf",
        "ntk", "nts", "nrk", "nre", "nte", "nta", "nti", "ntn", "ntr",
        "rk", "rt", "rs", "rn",
        "rfk", "rfs", "rft", "rfa", "rfe", "rfn",
        "sf",
        "snn", "snk", "snf", "snt", "stn", "stf", "stk", "srn", "srt", "srk", "snr", "skn", "sek",
        "tf", "tk", "tn",
        "tnn", "tsr", "tsn", "tse", "tsf", "trs", "trf", "trn", "trk", "tef", "tsk",
        "tska", "tske", "tskn", "tskf", "tskr", "tsan", "tsak", "tsaf", "tsae",
        "tsarn", "tsark", "tsarf",
    }
}

除外リストは生成しておき、ループ処理の過程で、その時点の単語に対して除外対象かチェックするために使う。

var exclusionList = getExclusionList()

func addWord(set *set, characters []string, parentChar string) {
    chLen := len(characters)
    for i, c := range characters {
        thisWord := fmt.Sprintf("%s%s", parentChar, c)
追加->   if containsInSlice(thisWord, exclusionList) {
追加->      continue
追加->   }
        set.add(thisWord)
        cpCharacters := make([]string, chLen, chLen)
        copy(cpCharacters, characters)
        addWord(set, getRemaining(cpCharacters, i), fmt.Sprintf("%s%s", parentChar, c))
    }
}

func containsInSlice(str string, slice []string) bool {
    for _, s := range slice {
        if s == str {
            return true
        }
    }
    return false
}

結果

◆「Frankenste」(10字)

===========================
生成単語数 1448365
最初から単語の組み合わせ作成まで 7.833486秒
最初から最後の標準出力まで       13.766960秒
===========================

ちなみに、今回の改修前の結果は↓

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

◆「Frankenstei」(11字)

===========================
生成単語数 17703734
最初から単語の組み合わせ作成まで 103.119950秒
最初から最後の標準出力まで       194.219207秒
===========================

今回の改修前の結果は↓

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

◆「Frankenstein」(12字)

う〜む、残念。やっぱり、ローカル端末でやるにはメモリ増やすか、根本的に考え方を変えるかが必要かな。

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

fatal error: runtime: out of memory

runtime stack:
runtime.throw(0x4c7683, 0x16)
    /usr/lib/go-1.10/src/runtime/panic.go:619 +0x81
runtime.sysMap(0xc543af0000, 0x99000000, 0x486e00, 0x560898)
    /usr/lib/go-1.10/src/runtime/mem_linux.go:216 +0x20a
runtime.(*mheap).sysAlloc(0x548240, 0x99000000, 0x7f78df241570)
    /usr/lib/go-1.10/src/runtime/malloc.go:470 +0xd4
runtime.(*mheap).grow(0x548240, 0x4c800, 0x0)
    /usr/lib/go-1.10/src/runtime/mheap.go:907 +0x60
runtime.(*mheap).allocSpanLocked(0x548240, 0x4c800, 0x5608a8, 0xc42003fee0)
    /usr/lib/go-1.10/src/runtime/mheap.go:820 +0x301
runtime.(*mheap).alloc_m(0x548240, 0x4c800, 0xffffffffffff0100, 0xc42003ff10)
    /usr/lib/go-1.10/src/runtime/mheap.go:686 +0x118
runtime.(*mheap).alloc.func1()
    /usr/lib/go-1.10/src/runtime/mheap.go:753 +0x4d
runtime.(*mheap).alloc(0x548240, 0x4c800, 0xc420010100, 0x41206c)
    /usr/lib/go-1.10/src/runtime/mheap.go:752 +0x8a
runtime.largeAlloc(0x99000000, 0x440001, 0x7f78e4d7a6c8)
    /usr/lib/go-1.10/src/runtime/malloc.go:826 +0x94
runtime.mallocgc.func1()
    /usr/lib/go-1.10/src/runtime/malloc.go:721 +0x46
runtime.systemstack(0x0)
    /usr/lib/go-1.10/src/runtime/asm_amd64.s:409 +0x79
runtime.mstart()
    /usr/lib/go-1.10/src/runtime/proc.go:1170

goroutine 1 [running]:
runtime.systemstack_switch()
    /usr/lib/go-1.10/src/runtime/asm_amd64.s:363 fp=0xc420044ef0 sp=0xc420044ee8 pc=0x44d6b0
runtime.mallocgc(0x99000000, 0x4b4b60, 0xc420045001, 0xc420045090)
    /usr/lib/go-1.10/src/runtime/malloc.go:720 +0x8a2 fp=0xc420044f90 sp=0xc420044ef0 pc=0x40e7a2
runtime.newarray(0x4b4b60, 0x1100000, 0xc400000073)
    /usr/lib/go-1.10/src/runtime/malloc.go:855 +0x6a fp=0xc420044fc0 sp=0xc420044f90 pc=0x40eb2a
runtime.makeBucketArray(0x4ab0a0, 0xc420045018, 0x45e97c, 0x53cc60)
    /usr/lib/go-1.10/src/runtime/hashmap.go:881 +0xe2 fp=0xc420044ff8 sp=0xc420044fc0 pc=0x408532
runtime.hashGrow(0x4ab0a0, 0xc42007a150)
    /usr/lib/go-1.10/src/runtime/hashmap.go:905 +0x80 fp=0xc420045048 sp=0xc420044ff8 pc=0x4086b0
runtime.mapassign_faststr(0x4ab0a0, 0xc42007a150, 0xc48c888440, 0xa, 0xc48c888440)
    /usr/lib/go-1.10/src/runtime/hashmap_fast.go:760 +0x20e fp=0xc4200450b8 sp=0xc420045048 pc=0x40a57e
main.(*set).add(0xc42004e290, 0xc48c888440, 0xa)
    /work/src/golang/src/github.com/sky0621/compito/main.go:147 +0x91 fp=0xc4200450f8 sp=0xc4200450b8 pc=0x492411
main.addWord(0xc42004e290, 0xc46b64d980, 0x3, 0x4, 0xc48c8882e0, 0x9)
    /work/src/golang/src/github.com/sky0621/compito/main.go:63 +0x1ec fp=0xc420045240 sp=0xc4200450f8 pc=0x491c7c
main.addWord(0xc42004e290, 0xc44a415d60, 0x4, 0x5, 0xc48c8882a0, 0x8)
    /work/src/golang/src/github.com/sky0621/compito/main.go:66 +0x3ed fp=0xc420045388 sp=0xc420045240 pc=0x491e7d
main.addWord(0xc42004e290, 0xc44d2293e0, 0x5, 0x6, 0xc48c8833a0, 0x7)
    /work/src/golang/src/github.com/sky0621/compito/main.go:66 +0x3ed fp=0xc4200454d0 sp=0xc420045388 pc=0x491e7d
main.addWord(0xc42004e290, 0xc452c5e150, 0x6, 0x7, 0xc48c883390, 0x6)
    /work/src/golang/src/github.com/sky0621/compito/main.go:66 +0x3ed fp=0xc420045618 sp=0xc4200454d0 pc=0x491e7d
main.addWord(0xc42004e290, 0xc520206700, 0x7, 0x8, 0xc4786d64a0, 0x5)
    /work/src/golang/src/github.com/sky0621/compito/main.go:66 +0x3ed fp=0xc420045760 sp=0xc420045618 pc=0x491e7d
main.addWord(0xc42004e290, 0xc4a5266900, 0x8, 0x9, 0xc48a9835bc, 0x4)
    /work/src/golang/src/github.com/sky0621/compito/main.go:66 +0x3ed fp=0xc4200458a8 sp=0xc420045760 pc=0x491e7d
main.addWord(0xc42004e290, 0xc470a12640, 0x9, 0xa, 0xc48ed03f3b, 0x3)
    /work/src/golang/src/github.com/sky0621/compito/main.go:66 +0x3ed fp=0xc4200459f0 sp=0xc4200458a8 pc=0x491e7d
main.addWord(0xc42004e290, 0xc4579e6000, 0xa, 0xb, 0xc4bca2991a, 0x2)
    /work/src/golang/src/github.com/sky0621/compito/main.go:66 +0x3ed fp=0xc420045b38 sp=0xc4200459f0 pc=0x491e7d
main.addWord(0xc42004e290, 0xc54398e000, 0xb, 0xc, 0xc51fdb3d11, 0x1)
    /work/src/golang/src/github.com/sky0621/compito/main.go:66 +0x3ed fp=0xc420045c80 sp=0xc420045b38 pc=0x491e7d
main.addWord(0xc42004e290, 0xc42008c0c0, 0xc, 0xc, 0x0, 0x0)
    /work/src/golang/src/github.com/sky0621/compito/main.go:66 +0x3ed fp=0xc420045dc8 sp=0xc420045c80 pc=0x491e7d
main.main()
    /work/src/golang/src/github.com/sky0621/compito/main.go:37 +0x2b5 fp=0xc420045f88 sp=0xc420045dc8 pc=0x4915b5
runtime.main()
    /usr/lib/go-1.10/src/runtime/proc.go:198 +0x212 fp=0xc420045fe0 sp=0xc420045f88 pc=0x428582
runtime.goexit()
    /usr/lib/go-1.10/src/runtime/asm_amd64.s:2361 +0x1 fp=0xc420045fe8 sp=0xc420045fe0 pc=0x450111
exit status 2

今回の改修前の結果は↓

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

signal: killed

まとめ

結局、今回も１２字の壁は突破できず。
たかだか「Frankenstein」に含まれる英単語を洗い出すだけという単純なお題と捉えていたものの、このローカル端末のスペックでは単純にロジック組むだけではダメみたい。
もはや、１回ではダメそうだから、英単語として存在することがわかっているものをキャッシュする仕組みなども組み合わせていくとかも考えていかないと。。。