栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

追加复杂度

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

追加复杂度

Go编程语言规范说,

append
如果需要,内置函数会重新分配。

附加并复制切片

如果s的容量不足以容纳附加值,则append分配一个新的,足够大的切片,使其既适合现有slice元素又适合附加值。因此,返回的切片可以引用不同的基础数组。

必要时,增加目标切片的精确算法取决于实现。有关当前的

gc
编译器算法,请参见
growslice
Go
runtime
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 }        }}

附录

在围棋编程语言规范允许语言的实现者来实现

append
的内置功能在许多方面。

例如,新的分配仅必须“足够大”。分配的数量可以是parsimonius(分配最小的必要数量),或者是慷慨的,分配的数量大于最小必需的数量,以使多次调整大小的成本最小化。Go

gc
编译器使用大量的动态数组摊销恒定时间算法。

以下代码说明了

append
内置函数的两种合法实现。慷慨的常量函数实现了与Go
gc
编译器相同的摊销常量时间算法。一旦完成了初始分配,parsimonius变量函数便会重新分配并复制所有内容。Go
append
函数和Go
gccgo
编译器用作控件。

package mainimport "fmt"// Generous reallocationfunc 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 reallocationfunc 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 2constant 8195 9152 2variable 8195 8195 2

gccgo:

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

总而言之,取决于实现方式,一旦初始容量已满,

append
内置函数可能会或可能不会在每次调用时重新分配。

参考文献:

动态数组

摊销分析

附加并复制切片

如果s的容量不足以适合附加值,请

append
分配一个新的足够大的切片,使其既适合现有slice元素又适合附加值。因此,返回的切片可以引用不同的基础数组。

附加到切片规范讨论

规范(技巧和1.0.3)指出:

“如果s的容量不足以容纳其他值,则

append
分配一个新的,足够大的切片,使其既适合现有slice元素又适合附加值。因此,返回的切片可能引用了另一个基础数组。”

这应该是“如果且仅当”吗?例如,如果我知道切片的容量足够长,是否可以确定不会更改基础数组?

罗伯·派克

是的,你很放心。

运行时slice.go源文件

数组,切片(和字符串):“追加”的机制



转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/447881.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号