数组性能与LinkedList非常相似 - 给出了什么？

Question

所以标题有点误导......我会保持这个简单:我正在比较这两个数据结构:

1. 一个数组,从大小开始,每次后续添加,都有一个realloc()调用来扩展内存,然后将新的(malloced)元素追加到n-1位置.
2. 一个链表,我跟踪头部,尾部和大小.另外还涉及mallocing一个新元素并更新尾指针和大小.

不要担心这些数据结构的任何其他细节.这是我对此测试唯一关注的功能.

理论上,LL应该表现得更好.然而,它们在涉及10,100,1000 ......多达5,000,000个元素的时间测试中几乎相同.

我的直觉是堆很大.我认为Redhat上的数据段默认为10 MB？我错了.无论如何,realloc()首先检查在已分配的连续内存位置(0- [n-1])的末尾是否有空间可用.如果第n个位置可用,则不会重新定位元素.相反,realloc()只保留旧空间+紧接着的空格.我很难找到这方面的证据,而且我很难证明这个阵列在实践中应该比LL更差.

以下是阅读以下帖子后的进一步分析:

[更新#1]我已经修改了代码,使其具有一个单独的列表,该列表为LL和数组每隔50次迭代执行mallocs内存.对阵列增加了100万,几乎总是有18个动作.没有移动LL的概念.我做了一个时间比较,他们仍然几乎相同.这里有1000万个新增内容:

(Array)
time ./a.out a 10,000,000
real    0m31.266s
user    0m4.482s
sys     0m1.493s
(LL)
time ./a.out l 10,000,000
real    0m31.057s
user    0m4.696s
sys     0m1.297s

我希望时间与18个动作完全不同.数组添加需要1次分配和1次比较以获取并检查realloc的返回值以确保发生移动.

[更新#2]我在上面发布的测试中运行了一个ltrace,我认为这是一个有趣的结果......看起来像realloc(或一些内存管理器)正在抢先将数组移动到更大的连续位置,基于目前的规模.对于500次迭代,在迭代时触发存储器移动:1,2,4,7,11,18,28,43,66,101,154,235,358这非常接近求和序列.我发现这很有意思 - 以为我会发布它.

Answer 1

你是对的,realloc只会增加分配块的大小,除非它被阻止这样做.在现实世界的场景中,您很可能在列表的后续添加之间在堆上分配其他对象？在这种情况下,realloc必须分配一个全新的内存块并复制列表中已有的元素.

尝试每隔十次插入使用malloc在堆上分配另一个对象,并查看它们是否仍然执行相同的操作.