golang slice append 后 capacity 增长的算法

栏目: Go · 发布时间: 5年前

内容简介:函数定义:函数说明:内建函数append追加一个或多个elems到一个slice依赖的array的末尾,如果这个slice有足够的capacity,则reslice以容纳新增元素;如果capacity空间不够,则重新分配内存保存新的slice依赖的array,函数返回更新后的slice.(slice是引用,array保存真正的数据,slice切片理解:

一道题目:

golang slice append 后 capacity 增长的算法

append函数

函数定义: func append(slice []Type, elems ...Type) []Type

函数说明:内建函数append追加一个或多个elems到一个slice依赖的array的末尾,如果这个slice有足够的capacity,则reslice以容纳新增元素;如果capacity空间不够,则重新分配内存保存新的slice依赖的array,函数返回更新后的slice.(slice是引用,array保存真正的数据,slice切片理解: https://blog.haohtml.com/arch...

注意:append不会修改传参进来的slice(len和cap),只会在不够用的时候新分配一个array,并把之前的slice依赖的array数据拷贝过来;所以对同一个slice 重复 append,只要不超过cap,都是修改的同一个array,后面的会覆盖前面

capacity如何增长?

图片里提到"Capacity grows in a way not related to the size of appending data",那么,增长算法是什么样的呢?看源代码 src/runtime/slice.go:

newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap {
        newcap = cap
    } else {
        if old.len < 1024 {
            newcap = doublecap
        } else {
            // Check 0 < newcap to detect overflow
            // and prevent an infinite loop.
            for 0 < newcap && newcap < cap {
                newcap += newcap / 4
            }
            // Set newcap to the requested cap when
            // the newcap calculation overflowed.
            if newcap <= 0 {
                newcap = cap
            }
        }
    }
  1. 先将旧的slice容量乘以2,如果乘以2后的容量仍小于新的slice容量,则取新的slice容量(append多个elems)
  2. 如果新slice小于等于旧slice容量的2倍,则取旧slice容量乘以2
  3. 如果旧的slice容量大于1024,则新slice容量取旧slice容量乘以1.25

代码后面还会对newcap进行roundup,比如在64位平台,newcap是奇数的话就会+1

回头看题

package main

import (
    "fmt"
)
func main(){
    a := []int{1,2}
    b := append(a,3)
    fmt.Printf("cap(a)=%v,cap(b)=%v\n",cap(a),cap(b))
    c := append(b,4)
    d := append(b,5)
    fmt.Printf("cap(a)=%v,cap(b)=%v\n",cap(a),cap(b))
    fmt.Println(a,b,c,d)
    fmt.Printf("%p,%p,%p,%p\n",a,b,c,d)
}

第一次append,超出了a的cap范围,分配一个新的newcap为oldcap*2的array,即4;a不变

第二次append,len(b)是3,cap(b)是4,没有超出b的cap范围,b所依赖的array在len(b)的位置追加4,c共用这个array;b不变

第三次append,由于b没有变化,b所依赖的array在len(b)的位置追加5,会覆盖上一步的4

所以:c[3]和d[3]引用的是同一块内存,都是5

另外,如果 d:= append(c,5) 则结果就是 c[3]=4,d[3]=4,d[4]=5因为这一步会新分配array,并将c的数据拷贝过来

总结

写得比较匆忙,如有纰漏,欢迎指正。


以上所述就是小编给大家介绍的《golang slice append 后 capacity 增长的算法》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Node.js开发指南

Node.js开发指南

郭家寶(BYVoid) / 人民邮电出版社 / 2012-7 / 45.00元

Node.js是一种方兴未艾的新技术,诞生于2009年。经过两年的快速变化,Node.js生态圈已经逐渐走向稳定。Node.js采用了以往类似语言和框架中非常罕见的技术,总结为关键词就是:非阻塞式控制流、异步I/O、单线程消息循环。不少开发者在入门时总要经历一个痛苦的思维转变过程,给学习带来巨大的障碍。 而本书的目的就是帮助读者扫清这些障碍,学会使用Node.js进行Web后端开发,同时掌握事件驱......一起来看看 《Node.js开发指南》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具