go - append() は常に必要な最小限の容量を拡張しますか?

Question

スライスを学習するとき、私はこの疑問を持っています: append() は常に必要な最小限の容量を拡張しますか?

a := make([]byte, 0)
a = append(a, 1, 2, 3)
cap(a) == 3  // will this be always true?
// or the assumption may not hold since the underlying implementation of append()
// is not specified.

Answer 1

いいえ、この場合は保証されません。仕様は次のように述べています。

append(s S, x ...T) S  // T is the element type of S

s の容量が追加の値に適合するほど大きくない場合、appendは、既存のスライス要素と追加の値の両方に適合する、十分に大きな新しいスライスを割り当てます。したがって、返されたスライスは別の基になる配列を参照する場合があります。

(私のことを強調)

あなたの場合、明らかに容量 >= 3 は十分に大きいので、 に頼ることはできcap >= 3ますが、 に頼ることはできませんcap == 3。

もちろん、この場合の上限は、1e6、1e9、または 1e12 とは言えないと想定できます。ただし、正確な拡大 (新しいバッキング配列の割り当て) 戦略は、コンパイラ担当者がこのメカニズムに接続されたいくつかのノブを試すことができるように、すべての詳細で意図的に指定されていません。

Answer 2

スライスの容量が長さと等しいことを保証しないだけでなく、実際、長さが長い場合、結果のスライスの容量が長さと等しいことはほとんどありません。

append()vectorパッケージの代替品として宣伝されています。これを行うには、追加の複雑さがvectorパッケージ内の複雑さと一致する必要があります。つまり、要素の追加は O(1) の複雑さを償却する必要があります。この複雑さは言語仕様では保証されていませんが、append()現在 Go コミュニティで使用されているパターンが効率的に機能するためには、この複雑さは真実でなければなりません。

O(1) を償却するappend()には、容量が不足するたびに、現在の容量の一定の割合で容量を拡張する必要があります。たとえば、容量を 2 倍にします。容量がなくなるたびに容量が 2 倍になる場合、長さと容量が同じになるのは、長さが正確に 2 の累乗である場合 (最初は 2 の累乗であると仮定した場合) に限られますが、これは頻繁ではありません。