メモ。sliceを定義して要素を追加し続ける。
capacityの容量を超えると動的にcap値がスケールする。
~/S/g/tourOfGo ❯❯❯ go version
go version go1.11.5 darwin/amd64
~/S/g/tourOfGo ❯❯❯ go run slice9.go
len=0 cap=0 value=[]
len=1 cap=1 value=[0]
len=2 cap=2 value=[0 1]
len=3 cap=4 value=[0 1 2]
len=4 cap=4 value=[0 1 2 3]
len=5 cap=8 value=[0 1 2 3 4]
len=6 cap=8 value=[0 1 2 3 4 5]
len=7 cap=8 value=[0 1 2 3 4 5 6]
len=8 cap=8 value=[0 1 2 3 4 5 6 7]
len=9 cap=16 value=[0 1 2 3 4 5 6 7 8]
len=10 cap=16 value=[0 1 2 3 4 5 6 7 8 9]
len=11 cap=16 value=[0 1 2 3 4 5 6 7 8 9 10]
len=12 cap=16 value=[0 1 2 3 4 5 6 7 8 9 10 11]
len=13 cap=16 value=[0 1 2 3 4 5 6 7 8 9 10 11 12]
len=14 cap=16 value=[0 1 2 3 4 5 6 7 8 9 10 11 12 13]
len=15 cap=16 value=[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14]
len=16 cap=16 value=[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15]
len=17 cap=32 value=[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16]
~/S/g/tourOfGo ❯❯❯
【追記】
配列の容量(cap)が1,2,4,8..と変化する事象について、
オライリーのデータ構造とアルゴリズムを読みまして、これは繰り返し二倍化による動的配列実装になっていることがわかりました。
動的な配列を実装する際、配列のスタックが満杯になる都度、配列の要素を1増やす方式(厳密には1増えた新しい配列を用意し、満杯のスタックを全てpushして、新しい要素をpushする方式。)だと、push演算の時間はBig O notationで表すとO(n^2)となります。
(1+2+3+...+nの加算式の結果は(n+1)*n/2で求められ最も高い増加率を示すのはn^2であるためです)
一方で動的配列実装は、配列が満杯になるごとに新しい配列として容量が2倍の配列を用意します。(1,2,4,8,16,32...の要領です。)
この方式の場合push演算の回数は、Big O notationで表すとO(n)となり、上のアイディアよりも演算回数が大幅に削減されます。
配列のスタックが満杯になったときに、新しいスタックに対してpush操作がどれくらい必要か見てみます。満杯になったスタックの容量をnとします
n=1のとき1push演算、n=2のとき2push演算、n=4のとき4push演算、n=8のとき8push演算、、と進みます。
スタックの容量が32に達した時のpush演算の回数は、1+2+4+8+16=31でほぼ2n(32)に等しくなります。2nではnが最も高い増加率を示すので、O(n)となり、アルゴリズムの評価ではこちらの実装の方が計算量が少なく、優れた実装ということになります。