xcode 读取 nsdictionary 与 nsarray 的性能

performance for reads of nsdictionary vs nsarray

提问by glesage

Continuing off this post: Performance hit incurred using NSMutableDictionary vs. NSMutableArray>

继续这篇文章：使用 NSMutableDictionary 与 NSMutableArray 导致的性能损失>

I am trying to run a little test to see if the performance gap is that great for read and writes between NSArray & NSDictionary as well as their mutable coutnerparts...

我正在尝试运行一个小测试，看看性能差距是否对于 NSArray 和 NSDictionary 以及它们的可变 coutnerparts 之间的读写来说是那么大...

However, I am having difficulties finding a "balanced" test... because the dictionary has 2 (or 3 depending on how you see this) objects to loop through to get the value (not the key) seeked, while the array has only one...

但是，我很难找到“平衡”测试......因为字典有 2 个（或 3 个，取决于你如何看待这个）对象来循环获取值（不是键），而数组只有一...

Any suggestions?

有什么建议？

--If you want more details:What I mean is easier to explain through examples;

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

For the array: (for NSString *str in array) { do smth with the string }

对于数组：（对于数组中的 NSString *str）{ do smth with the string }

For the dictionary

对于字典

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

OR

或者

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

OR

或者

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

OR EVEN

甚至

NSArray *valuesOrKeys = [dictionary allKeys/allValues];

(for NSString *str in valuesOrKeys) {string }

What is the "fairest" test to do for the dictionary?

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

--EDIT (comment)

--编辑（评论）

As you all pointed (and asked why I would want that) that when a dictionary is used, it's because it fits the model better than an array...

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

well the reason for my asking is that an app I'm building is painfully slow and so I'm trying to figure out if the use of a different datatype would change any of that, and I am considering using basic c arrays... I have the choice at this point so I am able to change the inner workings to fit whatever type I want...

好吧，我问的原因是我正在构建的应用程序非常缓慢，所以我试图弄清楚使用不同的数据类型是否会改变其中的任何一种，我正在考虑使用基本的 c 数组......在这一点上我有选择，所以我可以改变内部工作以适应我想要的任何类型......

回答by Itai Ferber

I'd like to point you at the following article: "Array", by ridiculous_fish, an engineer at Apple. Cocoa arrays are not necessarily well-implemented na?ve arrays as you might expect, nor are dictionaries simple hash tables. Their performance is very circumstantial, and depends on the number of objects they hold (as well as their values, etc.). This might not directly affect the answer, but it's something to consider (NSDictionaryperformance will, of course, vary with the speed and reliability of your hashing function, and so on).

我想向您指出以下文章：“数组”，作者有笑料_fish，Apple 的一名工程师。Cocoa 数组不一定像您期望的那样实现良好的原始数组，字典也不是简单的哈希表。它们的性能非常重要，取决于它们持有的对象数量（以及它们的值等）。这可能不会直接影响答案，但需要考虑（NSDictionary当然，性能会随着散列函数的速度和可靠性等而变化）。

Additionally, if you're looking for a 'balanced' test, you'd have to look for a way for both classes to behave as close to each other as possible. You want to rule out accessing values via keys in the dictionary, because that — regardless of how fast seek times are for the underlying data structures maintained by NSDictionary— is slower than simply pulling objects from an array because you're performing more operations to do it. Access from an array is O(1), for a hash table, O(1)at best and O(n)at worst (depending on the implementation, somewhere in the middle).

此外，如果您正在寻找“平衡”测试，则必须寻找一种方法，使两个类的行为尽可能接近。您想排除通过字典中的键访问值，因为无论由维护的底层数据结构的查找时间有多快，这NSDictionary都比简单地从数组中提取对象要慢，因为您要执行更多操作来执行此操作. O(1)对于哈希表，从数组访问是O(1)最好的和O(n)最坏的（取决于实现，在中间的某个地方）。

There are several ways to enumerate both dictionaries and arrays, as you mentioned above. You're going to want to use the methods that are closest to each other in terms of implementation, those being either block-based enumeration (enumerateObjectsUsingBlock:for NSArrayand enumerateKeysAndObjects:for NSDictionary), or fast enumeration (using either allKeysor allValuesfor the NSDictionary). Because the performance of these algorithms is mainly empirical, I performed several tests to note access times (each with 10000 NSNumberobjects):

如上所述，有多种方法可以枚举字典和数组。您将希望使用在实现方面彼此最接近的方法，这些方法要么是基于块的枚举（enumerateObjectsUsingBlock:forNSArray和enumerateKeysAndObjects:for NSDictionary），要么是快速枚举（使用allKeys或allValuesfor 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

As you can see from the results of this contrived test, NSDictionaryis clearly slower than NSArray(around 7% slower using block enumeration, and 7–10% slower with fast enumeration). However, this comparison is rather pointless, seeing as using the fastest enumeration for NSDictionarysimply devolves it into an array anyway.

正如您从这个人为测试的结果中看到的那样，NSDictionary显然比NSArray（使用块枚举慢约 7%，使用快速枚举慢 7-10%）。然而，这种比较是相当没有意义的，因为使用最快的枚举NSDictionary无论如何只是将其转化为数组。

So the big question is, why would you consider using a dictionary? Arrays and hash tables aren't exactly interchangeable; what kind of model do you have that allows drop-in replacement of NSArraywith NSDictionary? Regardless of the times given by contrived examples to prove performance benefits one way or another, you should always implement your models in a way that makes sense— you can optimize later for performance if you have to. I don't see how you would uses these data structures interchangeably, but anyway, NSArrayis the winner here, especially considering the sequential order in which you're attempting to access values.

所以最大的问题是，你为什么要考虑使用字典？数组和哈希表不能完全互换；你有什么样的模型可以直接替换NSArraywith NSDictionary？不管人为的例子给出了多少时间来证明性能优势以一种或另一种方式，你应该始终以一种有意义的方式实现你的模型——如果需要，你可以稍后优化性能。我不知道您将如何互换使用这些数据结构，但无论如何，NSArray这里是赢家，尤其是考虑到您尝试访问值的顺序。

回答by ksh

Here's your "balanced" test using fast enumeration:

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

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

回答by Caleb

I am trying to run a little test to see if the performance gap is that great for read and writes between NSArray & NSDictionary as well as their mutable coutnerparts...

我正在尝试运行一个小测试，看看性能差距是否对于 NSArray 和 NSDictionary 以及它们的可变 coutnerparts 之间的读写来说是那么大...

Why? If it's just to satisfy your curiosity, that's one thing. But usually if you need a dictionary, an array really won't do, and vice versa. So it doesn't matter which one is faster at a given operation -- it's not like one is good alternative for the other.

为什么？如果只是为了满足你的好奇心，那是一回事。但通常如果你需要字典，数组真的不行，反之亦然。因此，在给定的操作中哪个更快并不重要——这并不是说一个是另一个的好选择。

However, I am having difficulties finding a "balanced" test... because the dictionary has 2 (or 3 depending on how you see this) objects to loop through to get the value (not the key) seeked, while the array has only one...

但是，我很难找到“平衡”测试......因为字典有 2 个（或 3 个，取决于你如何看待这个）对象来循环获取值（不是键），而数组只有一...

You're making some assumptions here that aren't likely to be valid. There's probably not a lot of looping involved to access elements of either kind of container.

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