首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >NSMutableArray背后的数据结构是什么?

NSMutableArray背后的数据结构是什么?
EN

Stack Overflow用户
提问于 2014-03-23 21:05:19
回答 2查看 3.8K关注 0票数 20

通常,“可变数组”类是作为简单数组的包装器实现的。当您添加超过末尾的元素时,包装器会分配更多内存。这是一种常见的数据结构,各种操作的性能是众所周知的。您可以在数组的末尾获得O(1)个元素访问、O(N)个插入和删除,或者O(1)个(平均)插入和删除。但NSMutableArray是另一回事。例如,docs说重点是我的

注意:数组上的大多数操作都需要constant time:访问元素,在两端添加或删除元素,以及替换元素。在数组中间插入一个元素需要线性时间。

那么,NSMutableArray到底是什么呢?这有记录在什么地方吗?

EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2014-03-23 21:10:02

它是circular buffer的包装器。

这既没有文档记录,也没有开源,但是this blog postNSMutableArray上展示了一个令人惊叹的逆向工程工作,我认为您会发现这非常有趣。

NSMutableArray类集群由一个名为__NSArrayM的具体私有子类支持。

最大的发现是,NSMutableArray不是CFArray的薄薄包装器,正如人们可能合理地认为的那样:CFArray是开源的,并且它不使用循环缓冲区,而__NSArrayM使用循环缓冲区。

通读这篇文章的评论,似乎从iOS 4开始就是这样的,而在以前的SDK中,NSMutableArray实际上在内部使用了CFArray,而__NSArrayM甚至都不在那里。

直接从我上面提到的博客文章中

数据结构

正如您可能已经猜到的那样,__NSArrayM使用循环缓冲区。这种数据结构非常简单,但比常规的数组/缓冲区稍微复杂一点。当到达任何一端时,循环缓冲区的内容都可以回绕。

循环缓冲区有一些非常酷的属性。值得注意的是,除非缓冲区已满,否则从两端插入/删除都不需要移动任何内存。

objectAtIndex:的伪代码如下:

代码语言:javascript
复制
- (id)objectAtIndex:(NSUInteger)index {
    if (_used <= index) {
        goto ThrowException;
    }

    NSUInteger fetchOffset = _offset + index;
    NSUInteger realOffset = fetchOffset - (_size > fetchOffset ? 0 : _size);

    return _list[realOffset];

ThrowException:
    // exception throwing code
}

其中ivars被定义为

  • _used:数组的元素数holds
  • _list:指向循环缓冲区的指针buffer
  • _size:缓冲区的大小buffer
  • _offset:数组的第一个元素的索引

再说一次,我不会把上面的所有信息都归功于任何人,因为它们直接来自这个amazing blog post by Bartosz Ciechanowski

票数 26
EN

Stack Overflow用户

发布于 2014-03-23 21:43:52

做了一些测量:从一个空数组开始,添加@"Hello“100,000次,然后删除它100,000次。不同的模式:在结尾处、开始处、中间添加/删除,接近开始处(可能时在索引20处),接近结束处(可能时远离结束处20个索引),以及在接近开始处和结束处交替添加/删除。以下是100,000个对象的时间(在Core 2 Duo上测量):

代码语言:javascript
复制
Adding objects = 0.006593 seconds
Removing objects at the end = 0.004674 seconds
Adding objects at the start = 0.003577 seconds
Removing objects at the start = 0.002936 seconds
Adding objects in the middle = 3.057944 seconds
Removing objects in the middle = 3.059942 seconds
Adding objects close to the start = 0.010035 seconds
Removing objects close to the start = 0.007599 seconds
Adding objects close to the end = 0.008005 seconds
Removing objects close to the end = 0.008735 seconds
Adding objects close to the start / end = 0.008795 seconds
Removing objects close to the start / end = 0.008853 seconds

因此,每次添加/删除的时间与数组开头或结尾的距离成正比,以较近者为准。在中间添加东西是很昂贵的。您不必完全在结尾工作;删除靠近开头/结尾的元素也是非常便宜的。

建议的循环列表实现忽略了一个重要的细节:在最后一个和第一个数组元素的位置之间有一个可变大小的间隙。当添加/删除数组元素时,该间隙的大小会发生变化。当间隙消失并添加更多对象时,需要分配更多的内存,并且需要移动对象指针;当间隙变得太大时,可以缩小数组,并且需要移动对象指针。一个简单的更改(允许间隙位于任何位置,而不仅仅是最后一个元素和第一个元素之间)将允许在任何位置进行快速更改(只要是相同的位置),并将使“精简”阵列的操作更快。

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/22591296

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档