NSMutableArray是否真的是堆栈或队列的良好后备存储？

我已经读过NSMutableArray将会有O（1）性能，而不是O（n）当元素从阵列的末端添加/删除（例如removeAtObject:0或removeLastObject），这使得它适合用作堆栈或队列 - 否定需要为这些容器类型创建LinkedList实现。NSMutableArray是否真的是堆栈或队列的良好后备存储？

这是真的吗？如果是这样，苹果如何设法做到这一点？如果不是，是否有任何证据表明，随着阵列中元素数量的增加，添加/删除元素在NSMutableArray实例末端所花费的时间会增加？ PS：由于NSMutableArray基本上是CFArray（它是“纯C”对应物）和the source code to CFArray is open，应该有可能检查它的内部工作。

来源

2013-04-27 adib

我不知道什么是精确的性能点 - 我怀疑它总是O（1），但实现是“聪明”和我怀疑它使用了一系列链接的数组来使性能相当“稳定”。 – 2013-04-27 13:24:25

链接列表具有较差的引用和分段属性的位置。如果没有它们，可以实现摊销O（1）。 – 2013-04-27 17:20:18

一些经验性的探索：http://ridiculousfish.com/blog/posts/array.html – 2013-04-27 18:23:07

_NSArrayM（其被用来代替CFArray对于大多数NSArrays）是目前的阵列双端队列，它确实提供摊销O（1）压入/弹出两端

（这是不能保证是这样在任何过去或未来的操作系统版本。NSArrayM本身是相当新的例如）

来源

2013-04-27 17:18:13

关于这方面的任何可证实的证据/测试结果？ – adib 2013-05-01 13:34:56

你可以尝试用Hopper来分解它。否则，恐怕不是。我的NDA阻止我提供太多。 – 2013-05-01 15:38:47

顺便说一句，你从这篇博客文章的源代码丢失：http://ridiculousfish.com/blog/posts/array.html - 照顾把它放在Github上？提前致谢。 – adib 2013-05-02 02:28:55

CFArray/CFMutableArray（通过扩展，NSArray/NSMutableArray）有非常宽松的性能保证---他们肯定不保证O（1）插入/删除的性能。

从CFArray.h（强调）：

计算复杂
的存取时间为所述阵列中的值被保证是在最坏的情况O（LG N）用于任何实施方式中，当前和未来，但通常是O（1）（恒定时间）。线性搜索类似地具有O（N * lg N），的最坏情况复杂度，尽管通常边界将更紧密，等等。插入或删除操作将典型地在阵列中的值的数目中是线性的，但在一些实现中可能清楚地在最坏情况下为O（N * 1g N）。表现中阵列中没有优势位置;也就是说，访问具有较低索引的值或插入或删除具有较高索引的值或无论如何不一定更快。

核心基金会/基金会目前没有提供任何模拟链接表的性能的数据结构。

来源

2013-04-27 15:07:22

可能值得使用Obj-C++，并且如果数据存储独立使用（即，不用作树/数组控制器的后备存储），则可以使用任何STL/boost容器。

来源

2013-04-27 15:57:27

NSMutableArray是否真的是堆栈或队列的良好后备存储？

回答

相关问题