CODEWITHSUNDEEP
iosoptimization
NarbehM
NarbehM

Reputation: 345

NSMutable objects: removeAllObjects vs. containsObject speed

Disclaimer: I'm relatively new to iOS development. I'm using ARC for this project.

I'd like to know which of these operations is faster and why?

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

OR 

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];
    }
}

EDIT 1

The question is really that whether doing removeAllObjecs and then adding things back would work faster or having to check if the item is already not there, add it to the set?

Upvotes: 0

Views: 179

Answers (1)

Dan Shelly
Dan Shelly

Reputation: 6011

Lets analyse this (the if that wrap the loop is the same so I'll ignore it):

Option 1:
-removeAllObjects: all objects are removed from the array, each is released once ==> N operations at the minimum ==> O(N)
The loop makes N iterations each of which:
* Create an NSIndexPath ==> O(1)
* Add the index path to the end of the array ==> O(1)
==> O(N) + O(N) + N*O(1) + N*O(1) = 2O(N) + 2*N*O(1) = 4O(N) = O(N)

Option 2:
The loop makes N iterations each of which:
* Create an NSIndexPath ==> O(1)
* Verify existence in the array ==> O(N) (an array must assume that it may contain duplicates)
* The if statement will also have its toll as it will be asked N times, and will mess the branch predication of the loop.
** The addition in the loop is a probabilistic matter (lets ignore it for now)
==> N*(O(1) + O(N) + O(1)) = N*O(N) + 2*N*O(1) = O(N^2)

==> Flat analysis would suggest that the first option is better.

If you were to use a NSMutableIndexSet your code would look like this for both options:

//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];
    }
}

==> The worst case complexity here would probably be O(N)

Please feel free to correct any wrong assumptions or calculations

Upvotes: 1

Related Questions