12

Go プログラミング言語でのこのループの計算上の複雑さはどれくらいですか?

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

線形時間 (メモリを再割り当てし、追加ごとにすべてをコピーする) で動作しますかappend、それとも償却定数時間 (多くの言語のベクトル クラスが実装されている方法のように) で動作しますか?

4

2 に答える 2

22

Go プログラミング言語の仕様では、append組み込み関数は必要に応じて再割り当てされると記載されています。

スライスへの追加とコピー

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

必要に応じて追加のためにターゲット スライスを拡張する正確なアルゴリズムは、実装に依存します。現在のgcコンパイラ アルゴリズムについてはgrowslice、Goruntimeパッケージslice.goソース ファイルの関数を参照してください。それは償却された定数時間です。

部分的には、成長する量のスライスの計算は次のようになります。

    newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap {
        newcap = cap
    } else {
        if old.len < 1024 {
            newcap = doublecap
        } else {
            for newcap < cap {
                newcap += newcap / 4
            }
        }
}

補遺

Go プログラミング言語仕様により、言語の実装者appendはさまざまな方法で組み込み関数を実装できます。

たとえば、新しい割り当ては「十分に大きく」なければなりません。割り当てられる量は、必要最小限の量を割り当てる parsimonius の場合もあれば、何度もサイズ変更するコストを最小限に抑えるために、必要な最小量よりも多くを割り当てる寛大な場合もあります。Gogcコンパイラは、寛大な動的配列償却定数時間アルゴリズムを使用します。

append次のコードは、組み込み関数の 2 つの有効な実装を示しています。gc寛大な定数関数は、Goコンパイラと同じ償却定数時間アルゴリズムを実装します。parsimonius 変数関数は、最初の割り当てがいっぱいになると、毎回すべてを再割り当てしてコピーします。Goappend関数と Gogccgoコンパイラがコントロールとして使用されます。

package main

import "fmt"

// Generous reallocation
func constant(s []int, x ...int) []int {
    if len(s)+len(x) > cap(s) {
        newcap := len(s) + len(x)
        m := cap(s)
        if m+m < newcap {
            m = newcap
        } else {
            for {
                if len(s) < 1024 {
                    m += m
                } else {
                    m += m / 4
                }
                if !(m < newcap) {
                    break
                }
            }
        }
        tmp := make([]int, len(s), m)
        copy(tmp, s)
        s = tmp
    }
    if len(s)+len(x) > cap(s) {
        panic("unreachable")
    }
    return append(s, x...)
}

// Parsimonious reallocation
func variable(s []int, x ...int) []int {
    if len(s)+len(x) > cap(s) {
        tmp := make([]int, len(s), len(s)+len(x))
        copy(tmp, s)
        s = tmp
    }
    if len(s)+len(x) > cap(s) {
        panic("unreachable")
    }
    return append(s, x...)
}

func main() {
    s := []int{0, 1, 2}
    x := []int{3, 4}
    fmt.Println("data    ", len(s), cap(s), s, len(x), cap(x), x)
    a, c, v := s, s, s
    for i := 0; i < 4096; i++ {
        a = append(a, x...)
        c = constant(c, x...)
        v = variable(v, x...)
    }
    fmt.Println("append  ", len(a), cap(a), len(x))
    fmt.Println("constant", len(c), cap(c), len(x))
    fmt.Println("variable", len(v), cap(v), len(x))
}

出力：

GC:

data     3 3 [0 1 2] 2 2 [3 4]
append   8195 9152 2
constant 8195 9152 2
variable 8195 8195 2

gccgo:

data     3 3 [0 1 2] 2 2 [3 4]
append   8195 9152 2
constant 8195 9152 2
variable 8195 8195 2

要約すると、実装によっては、初期容量がいっぱいになると、append組み込み関数が呼び出しごとに再割り当てされる場合とされない場合があります。

参考文献:

動的配列

償却分析

スライスへの追加とコピー

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

スライス仕様のディスカッションに追加する

仕様（先端および1.0.3）には次のように記載されています。

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

これは「If and only if」であるべきですか？たとえば、スライスの容量が十分に長いことがわかっている場合、基になる配列を変更しないという保証はありますか?

ロブ・パイク

はい、あなたはとても安心しています。

ランタイムslice.goソース ファイル

配列、スライス (および文字列): 「追加」の仕組み

于 2013-03-29T12:39:49.657 に答える
-1

すべての追加で再割り当てされるわけではなく、ドキュメントで明確に述べられています：

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

したがって、償却された定数時間は、求められる複雑さです。

于 2013-03-29T11:44:03.927 に答える