为什么遍历 NSArray 比遍历 NSSet 快?

Why is iterating through NSArray is faster than iterating through NSSet?

我想知道为什么遍历 NSArray 比遍历 NSSet 快?我想象它与 NSArray 被订购而 NSSet 不是的事实有关,但我是一个经过认证的答案,而不仅仅是猜测。

编辑:

我的问题是:为什么它更快,但该主题中没有解释。而不是如果它更快。

第一:你不能说NSArrayNSSet快。正如您从评论中的 link 中得到的那样,这取决于您在做什么。在 NSSet 的实例中搜索对象要快得多。当您选择 NSSet.

时,这就是您想要做的

集合和数组之间有两个的区别。

  • 数组必须保持顺序,集合则不需要。
  • 集合必须注意唯一性,数组则不需要。

所以看起来很聪明,对两者都有完全不同的实现。这会导致不同的运行时行为。所以正确的问题应该是:惊喜在哪里?

显然,集合的额外条件比数组的额外条件更昂贵。

顺便说一句:NSSet 的实例不可能实现其唯一性承诺。这是因为只有在将对象插入集合时才会检查唯一性。当您在插入一个对象后对其进行更改时,它可以与集合中的另一个对象相等。

@Amin的回答有些地方不准确

  1. 我们说的是迭代,而不是搜索。
  2. Set 中搜索当然比在 Array 中搜索更快,因为第一个只需要 O(1) 时间,而第二次需要 O(n) 时间。
  3. 在我看来,NSArrayNSSet(迭代)快,因为 NSArray 的访问时间是精确的 O(1),尽管 NSSet 是O(1) 也是,但它是摊销的。
  4. 您甚至不能将对象插入 NSSet

你能详细解释一下 "Obviously the extra condition for sets is more expensive than the extra condition for arrays."