How to find matching dictionaries within an NSArray based on strings contained from a different array

Question

I have an NSArray full of dictionaries.

I want to loop through it and find all dictionaries that have an key value matching any of the string object that exists within a separate array.

I then want to add this to a new results array of all objects found.

This is how I do it now, but I wanted to know if there is a more efficient and faster way of doing this.

NSArray *arrayOfDictionaries, *arrayOfIDs;

NSMutableArray *results = [NSMutableArray array];

for (NSDictionary *dict in arrayOfDictionaries) {

    for (NSString *userID in arrayOfIDs) {

        if ([userID isEqualToString:dict[@"user_id"]]) {

            [results addObject:dict];

        }
    }
}

return results;

score 2 · Accepted Answer · edited May 23 '17 at 11:50

Yes, your code could be a bit simpler, by using the NSArray containsObject: method:

NSArray *arrayOfDictionaries, *arrayOfIDs;

NSMutableArray *results = [NSMutableArray array];

for (NSDictionary *dict in arrayOfDictionaries) {

    if ([arrayOfIDs containsObject:dict[@"user_id"]) {

        [results addObject:dict];

    }
}

return results;

Note that although this code is nicer to read and understand, it still will have a similar run-time complexity to your original approach.

This is because although the code you posted has explicit N^2 run-time complexity in the middle (a nested for loop), and my new version has apparently only N complexity, the containsObject: call contains a loop, so there's still N^2 complexity.

If you wanted your algorithm to be more efficient -- and only if this matters, don't prematurely optimise! -- you could use an NSSet instead of an NSArray for storing the usersIDs. This would be faster because NSArray lookup is linear time, whereas NSSet uses hashing for lookups and has better than linear runtime lookups.

Note that if you want to put your own custom objects into an NSSet, you should override isEquals: and hashcode on that object. For more info, see Best practices for overriding isEqual: and hash

score 1 · Answer 2 · edited May 23 '17 at 12:13

You can go even further and filter your initial NSArray and get a Set of Indexes.

NSIndexSet *results = [NSIndexSet indexSet];    

results = [arrayOfDictionaries indexesOfObjectsPassingTest:^BOOL(NSDictionary* obj, NSUInteger idx, BOOL *stop) {
    return [arrayOfIDs containsObject:obj[@"user_id"]];
}];

Note that your containsObject could be improved if you use an NSSet for your arrayOfIDs instead of an NSArray.

If you want more options to filter the array check this stackoverflow thread.

How to find matching dictionaries within an NSArray based on strings contained from a different array

2 Answers2