Палец вверх 4
Перевод
Перевод

Эффективно найти первое из многих ключевых слов в большой строке NSString

Мне нужно найти все ключевые слова в большой NSString (для анализа исходного кода), и моя текущая реализация слишком медленная, но я не уверен, как ее улучшить.

Я использую NSRegularExpression , исходя из предположения, что он более оптимизирован, чем все, что я мог бы написать, но производительность ниже, чем я ожидал. Кто-нибудь знает более быстрый способ реализовать это?

Целевая строка будет содержать символы utf-8, но сами ключевые слова всегда будут буквенно-цифровыми ascii. Я полагаю, что это может быть использовано для оптимизации вещей совсем немного?

@implementation MyClass

// i'm storing the regular expression in a static variable, since it never changes and I need to re-use it often
static NSRegularExpression *keywordsExpression;

+ (void)initialize
{
  [super initialize];

  NSArray *keywords = [NSArray arrayWithObjects:@"accumsan", @"adipiscing", @"aliquam", @"aliquet", @"amet", @"ante", @"arcu", @"at", @"commodo", @"congue", @"consectetur", @"consequat", @"convallis", @"cras", @"curabitur", @"cursus", @"dapibus", @"diam", @"dolor", @"dui", @"elit", @"enim", @"erat", @"eros", @"est", @"et", @"eu", @"felis", @"fermentum", @"gravida", @"iaculis", @"id", @"imperdiet", @"integer", @"ipsum", @"lacinia", @"lectus", @"leo", nil];

  NSString *pattern = [NSString stringWithFormat:@"\\b(%@)\\b", [keywords componentsJoinedByString:@"|"]; // \b(accumsan|adipiscing|aliquam|…)\b
  keywordsExpression = [NSRegularExpression regularExpressionWithPattern:pattern] options:NSRegularExpressionCaseInsensitive error:NULL];
}

// this method will be called in quick succession, I need it to be a able to run tens
// of thousands of times per second. The target string is big (50KB or so), but the
// search range is short, rarely more than 30 characters
- (NSRange)findNextKeyword:(NSString *)string inRange:(NSRange)range
{
  return [keywordsExpression rangeOfFirstMatchInString:string options:0 range:range];
}

@end

РЕДАКТИРОВАТЬ В соответствии с ответом @ CodeBrickie, я обновил свой код, чтобы выполнить поиск по регулярному выражению один раз по всей строке и сохранить совпадения в кэшированном NSIndexSet , а затем каждый раз, когда вызывается метод, он ищет в NSIndexSet диапазоны ключевых слов вместо поиска строка. Результат примерно на порядок быстрее:

@implementation MyClass

static NSRegularExpression *keywordsExpression;
static NSIndexSet *keywordIndexes = nil;

+ (void)initialize
{
  [super initialize];

  NSArray *keywords = [NSArray arrayWithObjects:@"accumsan", @"adipiscing", @"aliquam", @"aliquet", @"amet", @"ante", @"arcu", @"at", @"commodo", @"congue", @"consectetur", @"consequat", @"convallis", @"cras", @"curabitur", @"cursus", @"dapibus", @"diam", @"dolor", @"dui", @"elit", @"enim", @"erat", @"eros", @"est", @"et", @"eu", @"felis", @"fermentum", @"gravida", @"iaculis", @"id", @"imperdiet", @"integer", @"ipsum", @"lacinia", @"lectus", @"leo", nil];

  NSString *pattern = [NSString stringWithFormat:@"\\b(%@)\\b", [keywords componentsJoinedByString:@"|"]; // \b(accumsan|adipiscing|aliquam|…)\b
  keywordsExpression = [NSRegularExpression regularExpressionWithPattern:pattern] options:NSRegularExpressionCaseInsensitive error:NULL];
}

- (void)prepareToFindKeywordsInString:(NSString *)string
{
  NSMutableIndexSet *keywordIndexesMutable = [[NSIndexSet indexSet] mutableCopy];
  [keywordsExpression enumerateMatchesInString:string options:0 range:NSMakeRange(0, string.length) usingBlock:^(NSTextCheckingResult *match, NSMatchingFlags flags, BOOL *stop){
    [keywordIndexesMutable addIndexesInRange:match.range];
  }];

  keywordIndexes = [keywordIndexesMutable copy];
}

- (NSRange)findNextKeyword:(NSString *)string inRange:(NSRange)range
{
  NSUInteger foundKeywordMax = (foundCharacterSetRange.location == NSNotFound) ? string.length : foundCharacterSetRange.location;
  NSRange foundKeywordRange = NSMakeRange(NSNotFound, 0);
  for (NSUInteger index = startingAt; index < foundKeywordMax; index++) {
    if ([keywordIndexes containsIndex:index]) {
      if (foundKeywordRange.location == NSNotFound) {
        foundKeywordRange.location = index;
        foundKeywordRange.length = 1;
      } else {
        foundKeywordRange.length++;
      }
    } else {
      if (foundKeywordRange.location != NSNotFound) {
        break;
      }
    }
  }

  return foundKeywordRange;
}

@end

Кажется, это работает хорошо, и производительность достигает того уровня, который я хочу. Я хотел бы подождать немного дольше, чтобы увидеть, есть ли еще предложения, прежде чем принять это, хотя.

objective-c regex string performance cocoa
задан Abhi Beckert 18 нояб. 2011 г., 13:24:58
источник

3 ответа

Решение 3
Перевод
Перевод

Поскольку вам нужны ключевые слова вместе с их диапазонами, я бы использовал enumerateMatchesInString:options:range:usingBlock: и реализовал блок, который добавляет ключевое слово в качестве ключа и диапазон в качестве значения для NSMutableDictionary .

Таким образом, у вас есть только один вызов для всей строки и всех ключевых слов с их диапазонами в словаре после этого вызова.

ответ дан tobiasbayer 18 нояб. 2011 г., 13:34:45
источник
Палец вверх 1
Перевод
Перевод

Вместо того, чтобы собирать регулярное выражение для соответствия всем ключевым словам, я предлагаю вам использовать очень простое регулярное выражение для соответствия любому слову, а затем искать соответствующее слово в Словаре, содержащем ваши ключевые слова; если этого слова нет, игнорируйте его.

Вы можете адаптировать регулярные выражения к тому, что вы знаете о ключевых словах для максимальной эффективности. Например, если вы знаете, что ищете только слова из трех-двенадцати строчных букв ASCII, вы можете использовать @"\\b[az]{3,12}+\\b" . По сравнению с вашим монстром регулярное выражение с десятками альтернатив.

Я с большим успехом использовал эту технику в своем проекте подсветки синтаксиса. Это было в Java, но быстрый взгляд на документы NSRegularExpression обнаруживает удивительно похожий набор функций.

ответ дан Alan Moore 18 нояб. 2011 г., 15:15:36
источник
Палец вверх 0
Перевод
Перевод

Что произойдет, если вы переключите поиск на какой-либо NSLiteral поиск вместо регистронезависимого?

Конечно, вам нужно учитывать регистр, но если он будет быстрее, он даст вам идеи.

Я бы поспорил, что максимальная скорость будет намного больше работы и будет включать строчную строку c и strstr ().

ответ дан Tom Andersen 18 нояб. 2011 г., 15:14:27
источник