Efficient means to enumerate an array looking for items in another array

Question

Without unintentionally killing performance, does this appear at first glance to be acceptable for perhaps 200 guid strings in one list compared for equality with 100 guid strings from another list to find the matching indexes.

I have a method signature defined like so...

-(NSArray*)getItemsWithGuids:(NSArray*)guids

And I wanted to take that passed in array of guids and use it in conjunction with this array...

NSArray *allPossibleItems; // Has objects with a property named guid.

... to obtain the indexes of the items in allPossibleItems which have the matching guids from guids

My first instinct was to try indexesOfObjectsPassingTest but after putting together the block, I wondered whether the iOS framework already offers something for doing this type of compare more efficiently.

-(NSArray*)getItemsWithGuids:(NSArray*)guids
    {
        NSIndexSet *guidIndexes = [allPossibleItems indexesOfObjectsPassingTest:^BOOL(id  _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop)
    {
        SomeObjWithGuidProperty *someObject = obj;

        for (NSString *guid in guids) {
            if ([someObject.guid isEqualToString:guid]) {
                return YES;
            }
        }
        return NO;
    }];


    if (guidIndexes) {
        // Have more fun here.
    }
}

Don't set *stop to YES in your if statement. Doing that will mean guidIndexes will only ever contain at most 1 index. — rmaddy
– rmaddy, Commented Mar 14, 2016 at 23:55
Why is the return type of your getItemsWithGuids:forGuids: method set to be NSArray * but you return an NSIndexSet? — rmaddy
– rmaddy, Commented Mar 14, 2016 at 23:56
Check this thread, comparing different ways. stackoverflow.com/questions/21157109/… — dichen
– dichen, Commented Mar 14, 2016 at 23:58
@rmaddy Sorry if that was confusing. I'm going to return an array of the matching objects I find in allPossibleItems array using the guidIndexes found in the search. — Logicsaurus Rex
– Logicsaurus Rex, Commented Mar 15, 2016 at 0:01
"guid" sounds to me like a thing that would make a nice NSDictionary key. Maybe a better design even beyond the scope of this question would be to keep your objects-with-guid properties in an indexed data structure, like NSDictionary — danh
– danh, Commented Mar 15, 2016 at 0:07

Josh Gafni · Accepted Answer · 2016-03-14 23:53:02Z

2

Since you're working with Objective-C (not Swift) check out YoloKit. In your case, you can do something like:

guids.find(^(NSString *guid){
    return [someObject.guid isEqualToString:guid];
});

answered Mar 14, 2016 at 23:53

Josh Gafni

2,8812 gold badges22 silver badges36 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Josh Gafni Over a year ago

A part of me wants to downvote my own post haha. I think my suggestion only reduces the number of lines. It doesn't make the algorithm more efficient.

danh Over a year ago

A part of me wants to up-vote because I think this OP should choose brevity over efficiency for 100-element sized collections. The reason I'm resisting the up-vote instinct is the reliance on net code which I distrust by default. Ehhh +1 anyway, because skimming yolo reminds me of underscorejs, which is a godsend.

Paulw11 · Accepted Answer · 2016-03-15 00:43:03Z

1

My thought would be to use a set -

-(NSArray*)getItemsWithGuids:(NSArray*)guids inAllObjects:(NSArray *)allObjects 
{

   NSSet *matchGuids=[NSSet setWithArray:guids];
   NSMutableArray *matchingObjects=[NSMutableArray new];
   for (SOmeObjectWithGuidProperty *someObject in allObjects) {
       if ([matchGuids contains:someObject.guid]) {
           [matchingObjects addObject:someObject];
       }
   }

   return [matchingObjects copy];
}

edited Mar 15, 2016 at 0:43

answered Mar 15, 2016 at 0:01

Paulw11

116k15 gold badges175 silver badges213 bronze badges

6 Comments

rmaddy Over a year ago

allGuids should be: NSSet *allGuids = [NSSet setWithArray:guids];. And the for loop should be over allObjects.

Paulw11 Over a year ago

Why do you say that? I changed the function signature since in the original question, allPossibleItems comes from nowhere and although the input parameter is called guids it actually seems to contain instances of SomeObjWithGuidProperty

rmaddy Over a year ago

In the OP's code, guids is an array of NSString and allObjects is an array of SomeObjWithGuidProperty.

Borys Verebskyi Over a year ago

Answer is actually wrong. [allObjects valueForKey:@"guid"] will return NSArray, not NSSet. Moreover, there is no someObject declaration.

Paulw11 Over a year ago

Thanks, that was a typo between my brain and the keyboard.

|

Duncan C · Accepted Answer · 2016-03-15 00:07:42Z

1

Your code looks like it would have O(n^2) performance, which is bad. I think the solution of converting guids to an NSSet and then using NSSet's containsObject would likely be much more performant. You could rewrite your indexesOfObjectsPassingTest code to use an NSSet and containsObject pretty easily.

answered Mar 15, 2016 at 0:07

Duncan C

132k22 gold badges185 silver badges295 bronze badges

Comments

Borys Verebskyi · Accepted Answer · 2016-03-15 00:26:52Z

If order doesn't matter much, I would suggest to change data structure here. Instead of using NSArray, consider to use NSDictionary with guid as key and someObject as value. In this case, you should use -[NSDictionary objectsForKeys:notFoundMarker:] method to obtain objects.

It will work much faster, than enumeration trough 2 arrays. If the NSDictionary key have a good hash function, accessing an element, setting an element, and removing an element all take constant time. NSString has good hash.

-(NSArray*)getItemsWithGuids:(NSArray*)guids {
    NSArray *objectsAndNulls = [allPossibleItemsDictionary objectsForKeys:guids notFoundMarker:[NSNull null]];
    if (objectsAndNulls) {
        // Have more fun here.
        // You should check that object in objectsAndNulls is not NSNull before using it
    }
    return objectsAndNulls;
}

UPD Unfortunately, there is no way to pass nil as notFoundMarker. If you can't provide usable notFoundMarker value and don't want to perform additional checks, you can query objects one by one and fill NSMutableArray. In this case you will avoid pass trough array to remove NSNulls:

-(NSArray*)getItemsWithGuids:(NSArray*)guids {
    NSMutableArray *objects = [NSMutableArray arrayWithCapacity:guids.count];
    for (NSString *guid in guids) {
        SomeObjWithGuidProperty *object = allPossibleItemsDictionary[guid];
        if (nil != object) {
            [objects addObject:object];
        }
    }
    if (nil != objects) {
        // Have more fun here.
    }
    return object;
}

Collectives™ on Stack Overflow

Efficient means to enumerate an array looking for items in another array

4 Answers 4

2 Comments

6 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

6 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related