英文:
Does go not have a built-in dynamic array?
问题
我刚开始学习go，正在学习数据结构。我习惯于在python中使用类似于list或在C++中使用std::vector这样的动态数组，但是在go中似乎没有类似的东西。动态数组的好处是添加新元素的时间复杂度为O(1)，索引的时间复杂度也是O(1)。
起初我以为slice就是动态数组，但是后来我意识到当我使用append函数时，整个切片都会被复制，因此它的操作时间复杂度是O(N)，而不是动态数组的O(1)。
然后我找到了list，但这是一个双向链表，意味着索引的时间复杂度是O(N)，而不是O(1)。
我是否错过了我正在寻找的数据结构？
英文:
I have just started to pick up go, and I was going over the data structures. I am used to having a dynamic array like list in python or std::vector in C++, but I don't see anything similar in go. The nice things about dynamic array is that it has O(1) time complexity to add a new element, and O(1) time complexity for indexing.
First I thought that slice is it, but then I realized that when I used append function, the whole slice is being copied, and then therefore it is an O(N) operations as opposed to O(1) in dynamic array.
Then I came across list but this is a doubly linked list, which means that indexing is O(N), as opposed to O(1).
Am I missing the data structure I am looking for?
答案1
得分: 10
首先，我以为slice是这样的，但后来我意识到当我使用append函数时，整个切片都被复制了，因此它是一个O(N)的操作，而不是动态数组的O(1)操作。
这是不正确的。
根据《Go编程语言规范》，append函数会检查支持切片的数组的容量，只有在支持数组的空间不足时才会分配新的内存（复制切片）。我在规范中没有看到具体指定要分配多少内存，但根据你提供的博文，新分配的内存块将是当前切片大小的1.5倍。这意味着，在重新分配/复制插入之后，接下来的n/2个插入将不需要重新分配/复制。总体效果是摊销的O(1)时间。这与你提到的其他语言中的示例（Python中的list，C++中的std::vector）使用的方法相同。
因此，切片正是你所需要的。
英文:
> First I thought that slice is it, but the[n] I realized that when I used append function, the whole slice is being copied, and then therefore it is an O(N) operations as opposed to O(1) in dynamic array.
This is not correct.
Per The Go Programming Language Specification, append examines the capacity of the array that backs the slice, and only allocates new memory (copying the slice) if there's not enough room in the backing array. [link] I don't see anything in the specification proper that specifies how much memory it should allocate, but according to the blog post you link to, the new block of memory will be 1.5 times the current size of the slice. That means that, after a reallocating/copying insertion, the next n/2 insertions will not require reallocating/copying. The overall effect is amortized O(1) time. This is the same approach used by the examples you mention in other languages (list in Python, std::vector in C++).
So, slices are exactly what you need.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论