NSArray, NSSet, NSOrderedSet 和 NSDictionary

基础集合类是每一个 Mac/iOS 应用的基本组成部分。在本文中，我们将对”老类” (NSArray, NSSet)和”新类” (NSMapTable,NSHashTable, NSPointerArray) 进行一个深入的研究，探索每一个的效率细节，并讨论其使用场景。

作者提示：本文包含一些参照结果，但它们并不意味着绝对精确，也没有进行均差分析及多次的测试。这些结果的目的是给出运行时统计，来帮助我们认识到通常来说用什么会更快。所有的测试基于 iPhone 5s，使用 Xcode 5.1b1 和 iOS 7.1b1 的 64 位程序。编译选项设置为 -Ofast 的发布构建。Vectorize loops 和 unroll loops (默认设置) 均设置为关闭。

大 O 符号，算法复杂度计量

首先，我们需要一些理论知识。效率通常用大 O 符号描述。它定义了一个函数的极限特征，通常被用于描绘其算法效率。O 定义了函数增长率的上限。不同量级的差异非常巨大，可以看看通常使用的 O 符号的量级以及它们所对应需要的操作数的关系。

例如，如果用算法复杂度为 O(n^2)的算法对一个有 50 个元素的数组排序，需要 2,500 步的操作。而且，还有内部的系统开销和方法调用 — 所以是 250 0个操作的时间常量。 O(1)是理想的复杂度，代表着恒定的时间。好的排序算法通常需要 O(n*log n) 的时间。

可变性

大多数的集合类存在两个版本:可变和不可变(默认)。这和其他大多数的框架有非常大的不同，一开始会让人觉得有一点奇怪。然而其他的框架现在也应用了这一特性：就在几个月前，.NET公布了作为官方扩展的不可变集合。

最大的好处是什么？线程安全。不可变的集合完全是线程安全的，可以同时在多个线程中迭代，避免各种转变时出现异常的风险。你的 API 绝不应该暴露一个可变的集合。

当然从不可变到可变然后再回来是会有一定代价的 — 对象必须被拷贝两次，所有集合内的对象将被 retain/release。有时在内部使用一个可变的集合，而在访问时返回一个不可变的对象副本会更高效。

与其他框架不同的是，苹果没有提供一个线程安全的可变集合，NSCache 是例外，但它真的算不上是集合类，因为它不是一个通用的容器。大多数时候，你不会需要在集合层级的同步特性。想象一段代码，作用是检查字典中一个 key 是否存在，并根据检查结果决定设置一个新的 key 或者返回某些值 — 你通常需要把多个操作归类，这时线程安全的可变集合并不能对你有所帮助。

其实也有一些同步的，线程安全的可以使用的可变集合案例，它们往往只需要用几行代码，通过子类和组合的方法建立，比如这个NSDictionary 或这个 NSArray。

需要注意的是，一些较新的集合类，如 NSHashTable，NSMapTable 和 NSPointerArray 默认就是可变的，它们并没有对应的不可变的类。它们用于类的内部使用，你基本应该不会能找到需要它们的不可变版本的应用场景。

NSArray

NSArray 作为一个存储对象的有序集合，可能是被使用最多的集合类。这也是为什么它有自己的比原来的 [NSArray arrayWithObjects:..., nil] 简短得多的快速语法糖符号 @[...]。 NSArray 实现了 objectAtIndexedSubscript:，因为我们可以使用类 C 的语法 array[0] 来代替原来的 [array objectAtIndex:0]。

性能特征

关于 NSArray 的内容比你想象的要多的多。基于存储对象的多少，它使用各种内部的变体。最有趣的部分是苹果对于个别的对象访问并不保证 O(1) 的访问时间 — 正如你在 CFArray.h CoreFoundation 头文件中的关于算法复杂度的注解中可以读到的:

对于 array 中值的访问时间，不管是在现在还是将来，我们保证在任何一种实现下最坏情况是 O(lg N)。但是通常来说它会是 O(1) (常数时间)。线性搜索操作很可能在最坏情况下的复杂度为 O(N*lg N)，但通常来说上限会更小一些。插入和删除操作耗时通常和数组中的值的数量成线性关系。但在某些实现的最坏情况下会是 O(N*lg N) 。在数组中，没有对于性能上特别有优势的数据位置，也就是说，为了更快地访问到元素而将其设为在较低的 index 上，或者在较高的 index 上进行插入和删除，或者类似的一些做法，是没有必要的。

在测量的时候，NSArray 产生了一些有趣的额外的性能特征。在数组的开头和结尾插入/删除元素通常是一个 O(1)操作，而随机的插入/删除通常是 O(N) 的。

有用的方法

NSArray 的大多数方法使用 isEqual: 来检查对象间的关系(例如 containsObject: 中)。有一个特别的方法indexOfObjectIdenticalTo: 用来检查指针相等，如果你确保在同一个集合中搜索，那么这个方法可以很大的提升搜索速度。 在 iOS 7 中，我们最终得到了与 lastObject 对应的公开的 firstObject 方法，对于空数组，这两个方法都会返回 nil — 而常规的访问方法会抛出一个 NSRangeException 异常。

关于构造（可变）数组有一个漂亮的细节可以节省代码量。如果你通过一个可能为 nil 的数组创建一个可变数组，通常会这么写:

或者通过更简洁的三元运算符:

更好的解决方案是使用arrayWithArray:，即使原数组为nil，该方法也会返回一个数组对象:

这两个操作在效率上几乎相等。使用 copy 会快一点点，不过话说回来，这不太可能是你应用的瓶颈所在。提醒：不要使用 [@[] mutableCopy]。经典的[NSMutableArray array]可读性更好。

逆序一个数组非常简单：array.reverseObjectEnumerator.allObjects。我们使用系统提供的 reverseObjectEnumerator，每一个 NSEnumerator 都实现了 allObjects，该方法返回一个新数组。虽然没有原生的 randomObjectEnumerator 方法，你可以写一个自定义的打乱数组顺序的枚举器或者使用一些出色的开源代码。

数组排序

有很多各种各样的方法来对一个数组排序。如果数组存储的是字符串对象，sortedArrayUsingSelector:是第一选择:

下面的代码对存储数字的内容同样很好，因为 NSNumber 实现了 compare:

如果想更可控，可以使用基于函数指针的排序方法:

苹果增加了一个方法来加速使用 sortedArrayHint 的排序。

hinted sort 方式在你有一个已排序的大数组 (N 个元素) 并且只改变其中一小部分（P 个添加和删除，这里 P远小于 N）时，会非常有效。你可以重用原来的排序结果，然后在 N 个老项目和 P 个新项目进行一个概念上的归并排序。为了得到合适的 hint，你应该在原来的数组排序后使用 sortedArrayHint 来在你需要的时候(比如在数组改变后想重新排序时)保证持有它。

因为block的引入，也出现了一些基于block的排序方法:

性能上来说，不同的方法间并没有太多的不同。有趣的是，基于 selector 的方式是最快的。你可以在 GitHub 上找到测试用的源代码:

Sorting 1000000 elements. selector: 4947.90[ms] function: 5618.93[ms] block: 5082.98[ms].

二分查找

NSArray 从 iOS 4 / Snow Leopard 开始内置了二分查找

为什么要使用这个方法？类似 containsObject: 和 indexOfObject: 这样的方法从 0 索引开始搜索每个对象直到找到目标 — 这样不需要数组被排序，但是却是 O(n)的效率特性。如果使用二分查找的话，需要数组事先被排序，但在查找时只需要 O(log n) 的时间。因此，对于 一百万条记录，二分查找法最多只需要 21 次比较，而传统的线性查找则平均需要 500,000 次的比较。

这是个简单的衡量二分查找有多快的数据:

作为比较，查找 NSOrderedSet 中的指定索引花费 0.23 毫秒 — 就算和二分查找相比也又快了 30 多倍。

记住排序的开销也是昂贵的。苹果使用复杂度为 O(n*log n) 的归并排序，所以如果你执行一次 indexOfObject: 的话，就没有必要使用二分查找了。

通过指定 NSBinarySearchingInsertionIndex，你可以获得正确的插入索引，以确保在插入元素后仍然可以保证数组的顺序。

枚举和总览

作为测试，我们来看一个普通的使用场景。从一个数组中过滤出一些元素组成另一个数组。这些测试都包括了枚举的方法以及使用 API 进行过滤的方式：