CODEWITHSUNDEEP
iosobjective-cnsarray
Nikolay Dyankov
Nikolay Dyankov

Reputation: 7234

NSArray containsObject: faster alternative?

I did some runs on my iOS app with Instruments and I saw that 90% of the load on the main thread on launch (about 1000ms total) is caused by containsObject: calls. That's on the main thread and I don't think it's cool.

Is there a faster alternative to this method? An algorithm or another method?

Any suggestions?

MORE INFO:

  1. I looked into my code again I realized that in fact I don't need to know the order of the objects, only if an object is part of that set. Which means NSSet will do just fine (and I guess is faster).

  2. Number of objects - there may very well be 1000+ objects in that set.

Upvotes: 7

Views: 3195

Answers (2)

kokemomuke
kokemomuke

Reputation: 644

You can use NSSet containsObject more faster than NSArray

Upvotes: -1

James Webster
James Webster

Reputation: 32066

If you NEED to use an array, skip a bit further down

Alternate Options

Your other options might include:

  • Using an NSDictionary which uses key->value pairs which (I expect will) have O(1) read complexity at the cost of extra storage space for the keys

  • If you aren't using duplicates and order isn't important, using an NSSet will offer better read complexity (I don't know what the complexity will be, the docs probably will)

Using an Array

If you keep the array sorted, searching can be done in O(log n) time instead of O(n) as you can take advantage of a binary search.

Caveat Lector: This was written from memory

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

Upvotes: 11

Related Questions