3

想象一下，你有一堆 NSArray。这些数组都包含包裹在 NSValues 中的 CGPoints。所有元素都不是唯一的。所以某些元素可以出现在多个数组中。将这些数组组合成一个数组以使结果数组只包含唯一元素的最快方法是什么？

目前我正在这样做：

  1. 使用将每个数组插入 NSSetsetByAddingObjectsFromArray
  2. 用集合的内容填充结果数组

另一种选择是：

  1. 遍历每个数组一次并将每个值插入到 NSDictionary 中（如果它不在其中）
  2. 遍历字典的键一次并将每个键插入结果数组

传统的运行时分析表明，第一个选项应该随O(n log n)n 是所有初始数组中元素的数量（遍历所有元素并将每个元素插入到二叉搜索树或类似的日志时间）进行缩放。对于第二种方法，运行时间是O(n)因为查找和插入哈希表是在摊销的常数时间内运行的。然而，在阅读了一些有关 Apple 数据结构的信息后，假设它们的行为类似于传统数据结构似乎是愚蠢的。

4

2 回答 2

3

由于这两种方法都介于O(n)和 之间，O(n log n)并且您的 n 可能足够小以至于log n有界且很小，因此常数因素可能会决定其中哪种方法最快。

在这一点上，实际上用看起来像您的用例的数据进行基准测试是最好的做法。

我相信，但不确定，NSSet 也是用哈希实现的。

于 2012-10-21T17:34:35.490 回答
1

实际上...我认为时间几乎相同，但是，在 NSDictionary 的情况下，您将获得一些内存开销，因为在这种情况下，您需要将键复制到该 NSDictionary。它们都以相同NSDictionary的NSSet方式工作：

  1. hash检查唯一性
  2. 如果两个项目具有相同的缓存，isEqual则被调用

您已经提到，方法没有太大区别。

于 2012-12-05T17:44:02.910 回答