ios - NSMutable 对象 : removeAllObjects vs. 包含对象速度

Question

免责声明:我对 iOS 开发还比较陌生。我在这个项目中使用 ARC。

我想知道这些操作中哪一个更快，为什么？

if([selectedIndexes containsObject:indexPath]) {
    [selectedIndexes removeAllObjects];
    for(int i=0; i<self.options.count; i++) {
        [selectedIndexes addObject:[NSIndexPath indexPathForItem:i inSection:0]];   
    }
} 

或

NSIndexPath *indexPath;
if([selectedIndexes containsObject:indexPath]) {
    for(int i=0; i<self.options.count; i++) {
        indexPath = [NSIndexPath indexPathForItem:i inSection:0];
        if(![selectedIndexes containsObject:indexPath])
            [selectedIndexes addObject:indexPath];
    }
}

编辑 1

问题实际上是，执行removeAllObjecs然后将内容添加回去是否会工作得更快，或者必须检查该项目是否已经不存在，然后将其添加到集合中？

Answer 1

让我们分析一下(包装循环的 if 是相同的，所以我将忽略它):

选项 1:
-removeAllObjects:从数组中删除所有对象，每个对象释放一次 ==> 至少 N 次操作 ==> O(N)
该循环进行 N 次迭代，每次迭代:
* 创建一个 NSIndexPath ==> O(1)
* 将索引路径添加到数组末尾==> O(1)
==> O(N) + O(N) + N*O(1) + N*O(1) = 2O(N) + 2*N*O(1) = 4O(N) = O(N)

选项 2:
该循环进行 N 次迭代，每次迭代:
* 创建一个 NSIndexPath ==> O(1)
* 验证数组中是否存在==> O(N)(数组必须假设它可能包含重复项)
* if 语句也会产生影响，因为它会被询问 N 次，并且会弄乱循环的分支预测。
** 循环中的加法是一个概率问题(暂时忽略它)
==> N*(O(1) + O(N) + O(1)) = N*O(N) + 2*N*O(1) = O(N^2)

==> 平面分析表明第一个选项更好。

如果您要使用 NSMutableIndexSet，对于这两个选项，您的代码将如下所示:

//Not tested
//Assume that selectedIndexes is a NSMutableIndexSet
if ([selectedIndexes containsIndex:indexPath.row]) {
    if (self.options.count) {//This could probably be optimised depend on your goal
        [selectedIndexes addIndexesInRange:NSMakeRange(0,self.options.count-1)];
    } else {
        [selectedIndexes removeAllIndexes];
    }
} 

==> 这里最坏情况的复杂度可能是 O(N)

请随时纠正任何错误的假设或计算