2019/01/10

[golang]任意の値、要素数で配列を初期化する方法

Go言語の練習がてら「プログラマ脳を鍛える数学パズル」をやっていた。

そこでひとつの疑問が生まれた。
一発で任意の値、要素数で配列を初期化できないのか？

そんなことをツイートしたらリプライをいただいたので実際に試してみた。

それくらいしかないですね〜〜〜
効率的にやりたいという話になるとこの辺が参考になるかと👀https://t.co/3QiQKVbzk1
— しょっさん@ʕ ◔ϖ◔ʔ (@syossan27) 2018年12月26日

make関数を使って配列（正確にはslice）を生成する。

// すべてfalseの配列ができる
list := make([]bool, 1000)

// すべて0の配列ができる
list := make([]int, 1000)

make(型, 要素数, 容量)で任意の型と要素数でsliceを生成する。しかし型がboolならすべてfalse、intならすべで0のスライスができる。

まずは単純に1個ずつ書き換えていく方法。
簡単だが要素数分ループが必要なので計算量はO(n)になる。

list := make([]bool, 1000)
for i := range list {
    list[i] = true
}

要素数が大量にある場合はcopy関数を使うと効率化できる。
書き換えた分を1→2→4→8→16→…のように倍々にコピーする方法。

list := make([]bool, 1000)
list[0] = true

for p := 1; p < len(list); p *= 2 {
    copy(list[p:], list[:p])
}

追記: 2019/01/16 8:00
copyはビルトイン関数なのでO(1)という前提で当記事の計算量を書いたのだが、Twitterで以下のような指摘をされたので訂正する。

これってcopyがO(1) (引数のサイズに関係なく定数時間) という主張なんですか？
— (っ=﹏=c) .｡o○ (@itchyny) 2019年1月10日

built-in関数がすべてO(1)だと思ったら大きな間違いだぞっ
— (っ=﹏=c) .｡o○ (@itchyny) 2019年1月10日

2019/01/10