optimising a nested for loop

So, I have the following loop, and it's a bit of a bottle neck - is there any way I can speed this up?

NSArray *array = [an array of NSDictionaries];
NSArray *otherArray = [an array of NSStrings];
NSMutableArray *newArray = [NSMutableArray new] autorelease];

for (NSDictionary *dict in array)
{
    NSString *name = [[NSString alloc] initWithString:[dict object开发者_如何转开发ForKey@"name"]];
    for (NSString *n in otherArray)
    {
        if ([name hasPrefix:n])
            [newArray addObject:dict];
    }
    [name release];
}

---

You can define a NSPredicate and use

- (NSArray *)filteredArrayUsingPredicate:(NSPredicate *)predicate

on your array and don't loop on your own. You need to profile if it is actually faster.

---

About all I can see for substantial gains is that you could make up a boolean C-style array indexed by the first letter of your prefix and pre-load it with YES/NO based on whether that character is a "hit". (Probably you'd want a 256-element array indexed by the low byte of the 2-byte character.) Inside the outer loop take the first character of name, index this array, and if it's NO then skip the rest of the outer loop body. Only works if the prefix array is fairly small, though (so less than about half of the boolean array elements are YES).

You can probably make a small improvement by using a C-style array rather than the prefix NSArray, but at the expense of creating that C-style array up front.

There are other techniques that would involve hashing, but the setup expense and complexity is probably not worth it.

---

You can use a predicate to filter the array & remove the loop entirely.

NSPredicate * predicate = [NSPredicate predicateWithFormat:@"SUBQUERY(%@, $str, name BEGINSWITH[cd] $str).@count != 0", otherArray];
NSArray * newArray = [array filteredArrayUsingPredicate:predicate];

Assuming name is the key.