NSDictionary与NSArray的读取性能比较

Question

NSDictionary与NSArray的读取性能比较

objective-ccxcodeperformancebenchmarking

4

继续这篇文章：NSMutableDictionary与NSMutableArray之间的性能差异>

我正在尝试运行一个小测试，以查看在读写操作方面，NSArray和NSDictionary及其可变版本之间的性能差距是否很大...

然而，我很难找到一个“平衡”的测试...因为字典有2个（或3个，取决于您如何看待它）对象需要循环才能获取所需的值（而不是键），而数组只有一个...

有什么建议吗？

--如果您想要更多细节： 我的意思更容易通过示例解释;

对于数组：（for NSString *str in array）{使用字符串执行某些操作}

对于字典

(for NSString *str in [dictionary allValues]) { string }

或者

(for NSString *str in [dictionary allKeys]) { [dictionary valueForKey:key] }

或者

(for NSString *str in [dictionary allKeys]) { string }

甚至连这个

NSArray *valuesOrKeys = [dictionary allKeys/allValues];

(for NSString *str in valuesOrKeys) {string }

什么是对字典进行“公正”的测试？

--编辑（评论）

正如你们所指出的（并询问为什么我想要这样做），当使用词典时，它比数组更适合模型...

那么我提出这个问题的原因是，我正在构建的应用程序非常缓慢，因此我试图弄清楚是否使用不同的数据类型会改变任何东西，我正在考虑使用基本的 c 数组...在这一点上，我有选择权，因此能够更改内部工作方式以适应所需的任何类型...

- glesage

3个回答

5

这是使用快速枚举的“平衡”测试示例：

[arr enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
    // do something with objects    
}];
[dict enumerateKeysAndObjectsUsingBlock:^(id key, id obj, BOOL *stop) {
    // do something with objects    
}];

- ksh

正如在Itai Ferber的回答中所解释的那样，这似乎是最公平的测试。唯一的真正问题是它强制数组枚举产生块调用开销，这是不必要的（尽管至少在10.7 SDK中对于字典是必要的）。另外，正如Itai Ferber所解释的那样，整个测试有点愚蠢。但如果你坚持要进行测试，这可能是最好的选择。 - abarnert

1

我正在尝试运行一个小测试，以查看NSArray和NSDictionary及其可变对应项之间的读写性能差距是否很大...

为什么？如果只是为了满足你的好奇心，那就没什么问题。但通常情况下，如果你需要一个字典，数组真的不行，反之亦然。因此，在特定操作上哪个更快并不重要——并不像其中一个是另一个的好替代品。

然而，我在寻找一个“平衡”的测试时遇到了困难...因为字典有两个（或三个，这取决于你如何看待它）对象需要循环才能获取所需的值（而不是键），而数组只有一个...

你在这里做出了一些不太可能有效的假设。访问任一种容器的元素可能都没有涉及太多循环。

- Caleb

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Itai Ferber · Accepted Answer

我推荐您阅读以下文章: "Array"，该文章由苹果工程师ridiculous_fish撰写。Cocoa数组并不一定是单纯的朴素数组，也不是简单的哈希表。它们的性能很大程度上取决于它们所包含的对象数量（以及它们的值等）。虽然这可能不会直接影响答案，但这是需要考虑的（NSDictionary的性能当然会随哈希函数的速度和可靠性而变化）。

此外，如果您正在寻找一个“平衡”的测试方法，您需要让两个类的表现尽量接近。您需要排除通过字典键访问值的情况，因为无论维护NSDictionary的底层数据结构的检索时间有多快，这都比仅从数组中提取对象要慢，因为您需要执行更多的操作。从数组中访问的时间复杂度为O(1)，而对于哈希表来说，最好的情况下是O(1)，最坏的情况下是O(n)（取决于实现方式，在中间某个地方）。

有几种枚举字典和数组的方法，正如您上面提到的。您需要使用实现方式最接近的方法，即基于块的枚举（对于NSArray使用enumerateObjectsUsingBlock:，对于NSDictionary使用enumerateKeysAndObjects:），或者快速枚举（使用NSDictionary的allKeys或allValues）。由于这些算法的性能主要是经验性的，我进行了多次测试以记录访问时间（每个测试包含10000个NSNumber对象）。

NSArray, Block Enumeration:
1. 10.5s
2.  9.1s
3. 10.0s
4.  9.8s
5.  9.9s
   -----
    9.9s Avg

NSArray, Fast Enumeration:
1.  9.7s
2.  9.5s
3.  9.3s
4.  9.1s
5. 10.5s
   -----
    9.6s Avg

NSDictionary, Block Enumeration
1. 10.5s
2. 10.6s
3.  9.9s
4. 11.1s
5. 11.0s
   -----
   10.6s Avg

NSDictionary, allKeys -> Fast Enumeration
1. 10.0s
2. 11.2s
3. 10.2s
4. 10.8s
5. 10.8s
   -----
   10.6s Avg

NSDictionary, allValues -> Fast Enumeration
1. 10.7s
2. 10.3s
3. 10.5s
4. 10.5s
5.  9.7s
   -----
   10.3s Avg

正如你从这个人为测试的结果中所看到的，NSDictionary 明显比 NSArray 慢（使用块枚举慢大约 7％，使用快速枚举慢 7-10％）。然而，这种比较相当无意义，因为对于 NSDictionary，使用最快的枚举方式只是将其降级为一个数组。

所以重要的问题是，为什么要考虑使用字典？数组和哈希表并不完全可互换；您有哪种模型能够允许用NSDictionary替代NSArray? 不管使用假设示例给出的时间来证明性能方面的优劣，您应该总是以有意义的方式实现模型——如果必须的话，您可以稍后进行性能优化。我不知道您如何交替使用这些数据结构，但无论如何，NSArray 在这里是胜者，特别是考虑到您尝试按顺序访问值的情况。