ios - NSArray 包含对象 : faster alternative?

Question

我使用 Instruments 在我的 iOS 应用程序上运行了一些，我发现启动时主线程上 90% 的负载(总共大约 1000 毫秒)是由 containsObject: 调用引起的。这是在主线程上，我认为这不太酷。

是否有比此方法更快的替代方法？算法还是其他方法？

有什么建议吗？

更多信息:

1. 我再次查看我的代码，我意识到实际上我不需要知道对象的顺序，只要一个对象是该集合的一部分即可。这意味着 NSSet 会做得很好(而且我猜更快)。

2. 对象数量 - 该集合中很可能有 1000 多个对象。

Answer 1

如果您需要使用数组，请往下跳一点

---

备选方案

您的其他选择可能包括:

• 使用 NSDictionary，它使用键->值对(我预计)具有 O(1) 的读取复杂度，代价是键的额外存储空间

• 如果您不使用重复且顺序不重要，使用 NSSet 将提供更好的读取复杂度(我不知道复杂度是多少，文档可能将)

---

使用数组

如果您保持数组排序，搜索可以在 O(log n) 时间内完成，而不是 O(n)，因为您可以利用二进制搜索.

Caveat Lector:这是凭内存写的

-(void) /*adding*/
{
    int proposedIndex = 0;
    proposedIndex = [array indexOfObject:node
                                inSortedRange:NSMakeRange(0, array.count)
                                      options:NSBinarySearchingInsertionIndex
                              usingComparator:
                      ^ NSComparisonResult(id obj1, id obj2)
                      {
                          if (obj1.valueToCompare < obj2.valueToCompare) return NSOrderedAscending;
                          if (obj1.valueToCompare > obj2.valueToCompare) return NSOrderedDescending;
                          else return NSOrderedSame;
                      }];

    [array insertObject:node atIndex:proposedIndex];
}


-(id) /* Getting */
{
    int location = [array indexOfObject:node
                                    inSortedRange:NSMakeRange(0, array.count)
                                          options:NSBinarySearchingFirstEqual
                                  usingComparator:
                          ^ NSComparisonResult(id obj1, id obj2)
                          {
                              if (obj1.valueToCompare < obj2.valueToCompare) return NSOrderedAscending;
                              if (obj1.valueToCompare > obj2.valueToCompare) return NSOrderedDescending;
                              else return NSOrderedSame;
                          }];
    if (location == NSNotFound) return nil;
    return [array objectAtIndex:location];
}