没有内置的动态数组吗? [英] Does go not have a built-in dynamic array?

问题描述

我刚刚开始学习 go ，我正在研究数据结构.我习惯于在 python 中使用 list 或在 C ++ 中使用 std :: vector 的动态数组，但是我在 go 中看不到任何类似内容.动态数组的优点是添加新元素的时间复杂度为O(1)，用于索引的时间复杂度为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.

首先我以为是 slice ，但是后来我意识到，当我使用附加函数，整个切片都将被复制，因此它是一个O(N)操作，而不是动态数组中的O(1).

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.

然后我遇到了列表，但这是一个双向链接的列表，这意味着建立索引是O(N)，而不是O(1).

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?

推荐答案

首先，我以为是 slice ，但是[n]我意识到，当我使用追加后函数，整个切片将被复制，因此它是一个O(N)操作，而不是动态数组中的O(1).

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.

这是不正确的.

每个 Go编程语言规范， append 会检查支持切片的数组的容量，并仅在内存不足的情况下才分配新内存(复制切片)支持阵列中的空间.[链接]我在规范中看不到任何指定应分配多少内存的内容，但根据您链接到的博客文章，新的内存块将是当前切片大小的1.5倍.这意味着，在重新分配/复制插入之后，接下来的 n /2个插入将 not 要求重新分配/复制.总体效果是摊销O(1)时间.这与您在其他语言中提到的示例(Python中的 list ，C ++中的 std :: vector )所使用的方法相同.

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.

这篇关于没有内置的动态数组吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！