Go の「append」の時間計算量はどれくらいですか?

Go での追加の複雑さ

問題:

Go の次のループの計算複雑さはどれくらいですか?

var a []int
for i := 0 ; i < n ; i++ {
  a = append(a, i)
}

追加は線形時間で動作しますか、それとも償却定数時間?

答え:

Go プログラミング言語仕様では、append は必要に応じて再割り当てを実行すると規定されています:

If the capacity of s is not large enough to fit the additional values, append allocates a new, sufficiently large slice that fits both the existing slice elements and the additional values. Thus, the returned slice may refer to a different underlying array.

ただし、必要に応じてターゲット スライスを拡張するアルゴリズムは実装に依存します。現在の gc コンパイラの場合、アルゴリズムは一定時間で償却されます。

一定時間で償却されます。

スライス容量は貪欲に増加します:

• 古い容量が古い容量の 2 倍を超える場合、新しい容量は古い容量に設定されます。
• それ以外の場合、古い長さが 1024 未満の場合、新しい容量は古い容量の 2 倍に設定されます。
• それ以外の場合、新しい容量は 1024 になるまで 4 分の 1 ずつ増加します。

このアプローチにより、再割り当てに費やされる合計時間は確実に O(n) に償却されます。 n は、結果のスライスの長さです。

実装に関する考慮事項:

Go 言語仕様では、append のさまざまな実装が許可されています。たとえば、実装は寛大 (必要最小限の量を超える量を割り当てる) または倹約的 (必要最小限の量を割り当てる) の場合があります。 Go gc コンパイラーは、豊富な動的配列償却定数時間アルゴリズムを使用します。

概要:

Go での追加の複雑さは実装によって異なります。ただし、Go gc コンパイラーや gccgo などの一般的な実装では、償却定数時間アルゴリズムが使用されます。

以上がGo の「append」の時間計算量はどれくらいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。