оптимизация вложенного цикла

Question

Итак, у меня есть следующий цикл, и он немного напоминает горлышко бутылки - есть ли способ ускорить это?

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 objectForKey@"name"]];
    for (NSString *n in otherArray)
    {
        if ([name hasPrefix:n])
            [newArray addObject:dict];
    }
    [name release];
}

Answer 1

Вы можете использовать предикат для фильтрации array и полного удаления цикла.

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

Предполагая, что name является ключом.

Answer 2

Все, что я могу видеть для существенного увеличения, это то, что вы можете создать массив логического C-стиля, индексированный по первой букве вашего префикса, и предварительно загрузить его YES / NO в зависимости от того, является ли этот символ "хитом". , (Вероятно, вы хотите, чтобы массив из 256 элементов индексировался младшим байтом 2-байтового символа.) Во внешнем цикле возьмите первый символ имени, индексируйте этот массив, и если он НЕТ, пропустите оставшуюся часть внешнего тело петли. Работает только в том случае, если префиксный массив достаточно мал (поэтому менее половины элементов логического массива имеют значение YES).

Вероятно, вы можете сделать небольшое улучшение, используя массив в стиле C, а не префикс NSArray, но за счет создания этого массива в стиле C заранее.

Существуют и другие методы, которые включают хеширование, но затраты и сложность установки, вероятно, не стоят того.

Answer 3

Вы можете определить NSPredicate и использовать

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

на вашем array и не делать петли самостоятельно.Вам нужно профилировать, если это на самом деле быстрее.