Pertanyaan `kompleksitas append`


Apa kompleksitas komputatif dari loop ini dalam bahasa pemrograman Go?

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

Apakah append beroperasi dalam waktu linier (mengalokasikan kembali memori dan menyalin segala sesuatu pada masing-masing append), atau dalam waktu diamortisasi yang diamortisasi (seperti cara kelas vektor dalam banyak bahasa diaktipkan)?


10
2018-03-29 11:37


asal


Jawaban:


Spesifikasi Bahasa Pemrograman Go mengatakan bahwa append fungsi built-in mengalokasikan ulang jika perlu.

Menambahkan dan menyalin irisan

Jika kapasitas s tidak cukup besar untuk memenuhi nilai tambahan,   append mengalokasikan irisan baru, cukup besar yang sesuai dengan keduanya   elemen irisan yang ada dan nilai tambahan. Dengan demikian, yang dikembalikan   slice dapat merujuk ke array yang mendasari yang berbeda.

Algoritma yang tepat untuk menumbuhkan irisan target, bila perlu, untuk suatu lampiran tergantung pada penerapannya. Untuk saat ini gc algoritma kompiler, lihat growslice berfungsi dalam Go runtime paket slice.go sumber data. Ini diamortisasi waktu yang konstan.

Sebagian, jumlah komputasi potongan bertumbuh membacanya:

    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
            }
        }
}

TAMBAHAN

Itu Pergi Spesifikasi Bahasa Pemrograman memungkinkan pelaksana bahasa untuk mengimplementasikan append fungsi built-in dalam beberapa cara.

Misalnya, alokasi baru hanya harus "cukup besar". Jumlah yang dialokasikan mungkin parsimonius, mengalokasikan jumlah minimum yang diperlukan, atau murah hati, mengalokasikan lebih dari jumlah minimum yang diperlukan untuk meminimalkan biaya mengubah ukuran berkali-kali. The Go gc compiler menggunakan array dinamis waktu amortisasi algoritma waktu yang konstan.

Kode berikut menggambarkan dua implementasi hukum dari append fungsi built-in. Fungsi konstan murah hati mengimplementasikan algoritma waktu diamortisasi yang sama sebagai Go gc penyusun. Fungsi variabel parsimonius, setelah alokasi awal diisi, realokasi, dan menyalin semuanya setiap saat. The Go append fungsi dan Go gccgo compiler digunakan sebagai kontrol.

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))
}

Keluaran:

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

Untuk meringkas, tergantung pada implementasi, setelah kapasitas awal diisi, append fungsi bawaan dapat atau mungkin tidak dialokasikan ulang pada setiap panggilan.

Referensi:

Array dinamis 

Analisis yang diamortisasi 

Menambahkan dan menyalin irisan 

Jika kapasitas s tidak cukup besar untuk memenuhi nilai tambahan,    append mengalokasikan irisan baru yang cukup besar yang sesuai dengan keduanya   elemen irisan yang ada dan nilai tambahan. Dengan demikian, yang dikembalikan   slice dapat merujuk ke array yang mendasari yang berbeda.

Tambahkan ke diskusi spesifikasi slice 

Spec (di tip dan 1.0.3) menyatakan:

"Jika kapasitas s tidak cukup besar untuk muat tambahan   nilai-nilai, append mengalokasikan irisan baru yang cukup besar yang sesuai   baik elemen slice yang ada dan nilai tambahnya. Jadi, itu   potongan yang dikembalikan dapat merujuk ke array yang mendasari berbeda. "

Haruskah ini menjadi "Jika dan hanya jika"? Misalnya, jika saya tahu   kapasitas irisan saya cukup panjang, saya yakin bahwa saya akan melakukannya   tidak mengubah array yang mendasarinya?

Rob Pike 

Ya, Anda sangat yakin.

runtime slice.go sumber data

Array, irisan (dan string): Mekanisme 'append'


18
2018-03-29 12:39



Itu tidak realokasi pada setiap tambahan dan itu cukup eksplisit dinyatakan dalam dokumen:

Jika kapasitas s tidak cukup besar untuk memenuhi nilai tambahan, tambahkan mengalokasikan irisan baru yang cukup besar yang sesuai dengan elemen slice yang ada dan nilai tambahan. Dengan demikian, potongan yang dikembalikan dapat merujuk ke array yang mendasari yang berbeda.

Amortisasi waktu yang konstan adalah kompleksitas yang ditanyakan.


-1
2018-03-29 11:44