Search NSArray for value matching value

Question

I have an NSArray of objects, which has a particular property called name (type NSString).
I have a second NSArray of NSStrings which are names.

I'd like to get an NSArray of all the objects whose .name property matches one of the names in the second NSArray.

How do I go about this, fast and efficiently as this will be required quite often.

Solution 1

With your current data structures, you can only do it in O(n^2) time by looping over the first array once for each member of the second array:

NSMutableArray * array = [NSMutableArray array];
for (NSString * name in names) {
    for (MyObject * object in objects) {
        if ([[myObject name] isEqualToString:name]) {
            [array addObject:object];
        }
    }
}

(Alternate as suggested by Stefan: loop over the objects array and ask the names array if it containsObject: for the name of each object.)

But if this really needs to be faster (really depends on the size of the arrays as much as how often you do it), you can improve this by introducing an NSDictionary that maps the names in the first array to their objects. Then each of those lookups is O(1) and the overall time is O(n). (You'd have to keep this dictionary always in sync with the array of objects, which isn't hard with reasonable accessors. This technique also has the constraint that the same name can't appear on more than one object.)

An alternate way of getting this result (and which doesn't have that last constraint) is to use an NSSet for your second collection, then walk through the objects array calling containsObject: with each one on the set of names. Whether this technique is better depends on whether your two collections are roughly the same size, or if one is much larger than the other.

Solution 2

Why not just to use predicates to do that for you?:

// For number kind of values:
NSPredicate *predicate = [NSPredicate predicateWithFormat:@"SELF = %@", value];
NSArray *results = [array_to_search filteredArrayUsingPredicate:predicate];

// For string kind of values:
NSPredicate *predicate = [NSPredicate predicateWithFormat:@"SELF contains[cd] %@", value];
NSArray *results = [array_to_search filteredArrayUsingPredicate:predicate];

// For any object kind of value (yes, you can search objects also):
NSPredicate *predicate = [NSPredicate predicateWithFormat:@"SELF MATCHES %@", value];
NSArray *results = [array_to_search filteredArrayUsingPredicate:predicate];

Solution 3

Here's a simple way:

NSPredicate *predicate = [NSPredicate predicateWithFormat:@"name == %@", nameToFind];
[listOfItems filteredArrayUsingPredicate:predicate];

Solution 4

I like to use this method:

NSIndexSet *indexes = [_items indexesOfObjectsPassingTest:^BOOL(id obj, NSUInteger idx, BOOL *stop) {
   return ((MyObject *)obj).name isEqualToString:name];
}];

if (indexes.count != 0) {
//extract your objects from the indexSet, and do what you like...
}

Solution 5

NSMutableArray * foundNames = [NSMutableArray array];
for (MyObject * objectWithName in objectCollection) {
    if ([names containsObject:objectWithName.name]) {
        [foundNames objectWithName];
    }
}

View more solutions

Comments

[Stefan H]

Loop through your NSArray with a for loop, and add the matching objects (found with containsObject) to an NSMutableArray.

[Stefan H]

Why not use [names containsObject:object.name]?

[Stefan H]

Why not use [names containsObject:object.name]?

[Jonathan.]

But that will only find the object(s) with a single name, Their are multiple names that need to be found. (eg I want all the objects whose names are "Joe", "Bill", etc)

[Ben Zotto]

@Stefan H: Sure, if that way of thinking about it works better with your head. Still n^2 though. :) (Edited)

[CRD]

Note that using an NSDictionary for the first array will only work if none of your objects contain the same name - depends on your domain. That minor caveat aside, quixoto is correct - you won't improve this without redesigning your data structures.

[zakdances]

Why are string searches different than objects? Aren't NSStrings objects too?

[Lukasz]

Yes, they are and I am pretty sure you can. MATCHES is just dedicated for strings and you can add case options to it [cd].

[mkko]

+1 for this. Predicates also have now predicateWithBlock which is even more convenient.

[KevinH]

The predicate format for "any object kind of value" is not correct. MATCHES is only applicable to NSStrings. For a generic object, you should use the == operator to compare. I.e.: NSPredicate *predicate = [NSPredicate predicateWithFormat:@"SELF == %@", value]; NSArray *results = [array_to_search filteredArrayUsingPredicate:predicate];

[Kpmurphy91]

so change the predicate to [NSPredicate predicateWithFormat:@"name IN %@", arrayOfNames], use KVC to grab the array of names you need like: [_arrayOfObjects valueForKeyPath:@"name"], which will give you an NSArray (or set in some instances) which you can use as your IN %@ argument for the predicate.

[TylerH]

@MarcJohnson While the effort to improve content is appreciated, the OP above explicitly states their data is of the type NSString, so a solution which only works for NSString is fine and doesn't need to be changed. KevinH's comment is useful information, but it's not necessary/ideal to replace the answerer's code above, which works just fine here. There are competing answers that use == if you want to upvote them, instead.