读取nsdictionary与nsarray的性能

Question

继续这篇文章:使用NSMutableDictionary与NSMutableArray>产生的性能损失

我正在尝试进行一些测试,看看性能差距是否对NSArray和NSDictionary以及它们的可变coutnerparts之间的读写非常有用......

但是,我很难找到"平衡"测试...因为字典有2个(或3个,具体取决于你如何看待这个)对象循环以获取所寻找的值(而不是键),而数组只有一...

有什么建议？

- 如果你想了解更多细节: 我的意思是通过例子更容易解释;

对于数组:(对于数组中的NSString*str){do smth with the string}

对于字典

(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 }

对字典做什么是"最公平"的测试？

--EDIT(评论)

正如你们所指出的那样(并问我为什么会这么想),当使用字典时,这是因为它比数组更适合模型......

我问的原因是我正在构建的应用程序是非常缓慢的,所以我试图弄清楚是否使用不同的数据类型会改变其中任何一个,我正在考虑使用基本的c数组......我现在有了选择,所以我能够改变内部工作方式以适应我想要的任何类型......

Answer 1

我想在下面的文章中指出:" Array ",来自Apple的工程师ridiculous_fish.Cocoa数组不一定是你想象中的天真数组,也不是字典简单的哈希表.它们的表现非常具有间接性,取决于它们所拥有的物体数量(以及它们的价值等).这可能不会直接影响答案,但需要考虑的是(NSDictionary性能当然会随着散列函数的速度和可靠性而变化,等等).

此外,如果您正在寻找"平衡"测试,则必须寻找两种类型尽可能彼此接近的方式.你想排除通过在字典键访问值,因为-不论如何快速查找时间是维护底层数据结构NSDictionary-是不是简单地从一个数组对象拉,因为你执行更多操作干得慢.O(1)对于哈希表,对数组的访问O(1)最好是O(n)在最坏的情况下(取决于实现,在中间的某个地方).

如上所述,有几种方法可以枚举字典和数组.你会想用最接近彼此在执行方面的方法,它们是:无论是基于块的枚举(enumerateObjectsUsingBlock:用于NSArray与enumerateKeysAndObjects:供NSDictionary),或快速列举(使用allKeys或allValues对NSDictionary).因为这些算法的性能主要是经验性的,所以我进行了几次测试来记录访问时间(每个都有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只是简单地将其转换为数组.

所以最大的问题是,你为什么要考虑使用字典？数组和哈希表不完全可以互换; 什么样的模式,你必须允许简易替换的NSArray用NSDictionary？无论人工举例说明如何以某种方式证明性能优势,您都应该以一种有意义的方式实现模型- 如果必须,您可以稍后优化性能.我不知道你将如何交替使用这些数据结构,但无论如何,NSArray这里是赢家,特别是考虑到你试图访问值的顺序.

Answer 2

这是使用快速枚举的"平衡"测试:

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