动态数组是怎样实现的?

发布于 2022-09-02 01:51:15 字数 71 浏览 10 评论 0

现在的很多高级语言里面的Array都是动态数组,这个是怎么实现的?按理说效率应该很低的啊,而且swift里面还可以拷内存啊什么的

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(4

美胚控场 2022-09-09 01:51:15

反对 @肥肥的兔子 的观点。

题主明确说了是高级语言中的 Array,很显然 Array 就是线性表的顺序存储,而不是 linked list,不过在实现中,有一些变通方法,然而 Ø(1) 的读取等数组的特征却是必须的,你的 linked list 如何 Ø(1) 读取?

我讲一下三种实现方式吧:

  1. 模仿 std::vector 的实现,比如说 ArrayList 等,当 storage() == size() 事件发生的时候(逻辑元素数量已经达到了存储容量),将会按照增长因子进行容量翻倍,并且将原有数据拷贝到新的内存中。关于增长因子有必要一提,不少实现中都是 2,然而 sum(i ^ 2, {i, 0, n - 1} 是小于 n^2 的,所以之前的内存都不会被重用,cache 不友好,理论表明,最好的增长因子是 1 + (√5 - 1) / 2,即黄金分割率,工程上大多使用 1.5. 时间复杂度最佳Ø(1),最坏Ø(n),然而扩容的期望值为 1 / n,算出平均时间复杂度 = Ø(n) * 1 / n = Ø(1)

  2. 如果你能保证该动态数组的元素一定有默认构造函数,而且元素能够被 realloc() 或者其他语言中类似的东西分配,那就可以在上述事件发生时进行 realloc(),时间复杂度 Ø(1).

  3. 模仿 std::deque 的实现,一般实现为多块定长数组,增长时间复杂度是 Ø(1) 了,顺带也支持了 front 上操作,何乐而不为呢?唯一的缺点是读取、插入看似都是 Ø(1),然而实际上操作更复杂,系数比较大,如果只有尾部操作,速度反而比 std::vector、ArrayList 要慢 30% 左右。

零度℉ 2022-09-09 01:51:15

update

经 @rushcheyo提醒,确实链式存储的方法不太靠谱。确实这方面我不太了解,所以我在答案前也说明是抛砖引玉一下,后来上网查阅一下才大概弄懂。另外,题主可以参考一下这里有代码和对应的解释。


原答案

抛砖引玉一下,貌似有两种方式,第一种是添加元素时会拷贝之前的内容,和你新添加的内容放到新的空间里(空间上仍然是连续存储),第二种是采用链式存储(空间上不连续)。

心碎无痕… 2022-09-09 01:51:15

首先,任何数据结构都会有各自的优缺点,使用时需要根据需求取舍。比如需要高效率的随机访问(random access),可能就会有低效率的随机插入/删除(insert/delete in middle),反之亦然。

其次,关于动态数组(高效率的随机访问)的实现,题主可以参考 C++ 中 std::vector。简单来说与 @rushcheyo 的说法类似,初始时系统会分配一块内存,每当数组中的元素个数达到上限时,就会再次分配一块更大的内存(增加的速率由算法决定),然后将原有的元素移动到新分配的内存中去(当然如果数组的元素类型不支持移动构造函数(move constructor),则会拷贝数组中的元素到新内存中)。其实现效率并不低。另外 C++11 中引入了右值引用(rvalue reference)可以有效的减少在移动数组时拷贝的发生。

需要注意的是 std::vector 对于在数组中间的插入/删除操作是相对低效率的(一般情况下仍然可以接受),它会移动被插入/删除元素后面的所有元素。

对于 Python 中的 List,根据官方文档可知,也是按照类似的方法进行设计的。根据这篇博文,在 Python 最常见实现的 CPython 中,List 是通过一个变长数组实现的,数组的元素是指向 List 中元素的指针。

涙—继续流 2022-09-09 01:51:15

补充一个Python的实现:
[https://github.com/python/cpython/blob/master/Include/listobject.h#L23-L40]
[https://github.com/python/cpython/blob/master/Objects/listobject.c]
Python里面内置List的实现方式很简单,就是一个指针数组,分配在堆上,加一个allocated字段保存指针数组当前已经分配的内存数和一个ob_size字段保存当前已经占用的内存数。Python中List操作若涉及长度变化就会判断当前List已经分配的内存数是否足够,如果不够就realloc重新分配内存,够了就直接用已经分配的内存。

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文