Шаблон Regex и / или NSRegularExpression слишком медленный поиск в очень большом файле, можно ли его оптимизировать?
В среде iOS я ищу в этом файле размером 3,2 МБ произношение: https://cmusphinx.svn.sourceforge.net/svnroot/cmusphinx/trunk/pocketsphinx/model/lm/en_US/cmu07a.dic
Я использую NSRegularExpression для поиска произвольного набора слов, которые заданы как NSArray. Поиск осуществляется по содержимому большого файла в виде строки NSString. Мне нужно сопоставить любое слово, которое появляется в скобках с новой строки и символа табуляции, а затем захватить всю строку, например, если у меня есть слово "понедельник" в моем NSArray, я хочу сопоставить эту строку в файле словаря:
monday M AH N D IY
Эта строка начинается с новой строки, за строкой "понедельник" следует символ табуляции, а затем следует произношение. Вся строка должна соответствовать регулярному выражению для его конечного результата. Мне также нужно найти альтернативные произношения слов, которые перечислены ниже:
monday(2) M AH N D EY
Альтернативное произношение всегда начинается с (2) и может доходить до (5). Поэтому я также ищу итерации слова, за которыми следуют круглые скобки, содержащие одно число, заключенное в скобки с новой строкой и символом табуляции.
У меня есть 100% рабочий метод NSRegularExpression следующим образом:
NSArray *array = [NSArray arrayWithObjects:@"friday",@"monday",@"saturday",@"sunday", @"thursday",@"tuesday",@"wednesday",nil]; // This array could contain any arbitrary words but they will always be in alphabetical order by the time they get here.
// Use this string to build up the pattern.
NSMutableString *mutablePatternString = [[NSMutableString alloc]initWithString:@"^("];
int firstRound = 0;
for(NSString *word in array) {
if(firstRound == 0) { // this is the first round
firstRound++;
} else { // After the first iteration we need an OR operator first.
[mutablePatternString appendString:[NSString stringWithFormat:@"|"]];
}
[mutablePatternString appendString:[NSString stringWithFormat:@"(%@(\\(.\\)|))",word]];
}
[mutablePatternString appendString:@")\\t.*$"];
// This results in this regex pattern:
// ^((change(\(.\)|))|(friday(\(.\)|))|(monday(\(.\)|))|(saturday(\(.\)|))|(sunday(\(.\)|))|(thursday(\(.\)|))|(tuesday(\(.\)|))|(wednesday(\(.\)|)))\t.*$
NSRegularExpression * regularExpression = [NSRegularExpression regularExpressionWithPattern:mutablePatternString
options:NSRegularExpressionAnchorsMatchLines
error:nil];
int rangeLocation = 0;
int rangeLength = [string length];
NSMutableArray * matches = [NSMutableArray array];
[regularExpression enumerateMatchesInString:string
options:0
range:NSMakeRange(rangeLocation, rangeLength)
usingBlock:^(NSTextCheckingResult *result, NSMatchingFlags flags, BOOL *stop){
[matches addObject:[string substringWithRange:result.range]];
}];
[mutablePatternString release];
// matches array is returned to the caller.
Моя проблема в том, что, учитывая большой текстовый файл, он не очень быстрый на iPhone. 8 слов занимают 1,3 секунды на iPhone 4, что слишком долго для приложения. Учитывая следующие известные факторы:
• Текстовый файл объемом 3,2 МБ содержит слова для сопоставления в алфавитном порядке.
• Массив произвольных слов для поиска всегда в алфавитном порядке, когда они попадают в этот метод
• Альтернативные произношения начинаются с (2) в скобках после слова, а не (1)
• Если нет (2), не будет (3), (4) или более
• Наличие одного альтернативного произношения встречается редко, встречаясь в среднем 1 раз в 8 раз. Дальнейшие альтернативные произношения еще реже.
Можно ли оптимизировать этот метод, улучшив регулярное выражение или какой-либо аспект Objective-C? Я предполагаю, что NSRegularExpression уже достаточно оптимизирован, поэтому не стоит пытаться делать это с другой библиотекой Objective-C или в C, но если я ошибаюсь, дайте мне знать. В остальном очень благодарен за любые предложения по улучшению производительности. Я надеюсь сделать это обобщенным для любого файла произношения, поэтому я стараюсь держаться подальше от таких решений, как предварительный расчет алфавитных диапазонов для более ограниченного поиска.
****РЕДАКТИРОВАТЬ****
Вот сроки на iPhone 4 для всех ответов, связанных с поиском, данных 16 августа 2012 года:
Подход dasblinkenlight к созданию NSDictionary /questions/7778755/shablon-regex-i-ili-nsregularexpression-slishkom-medlennyij-poisk-v-ochen-bolshom-fajle-mozhno-li-ego-optimizirovat/7778762#7778762: 5,259676 секунд
Самое быстрое регулярное выражение Ωmega на /questions/7778755/shablon-regex-i-ili-nsregularexpression-slishkom-medlennyij-poisk-v-ochen-bolshom-fajle-mozhno-li-ego-optimizirovat/7778763#7778763: 0,609593 секунды
Многократный подход NSRegularExpression от dasblinkenlight по адресу https://stackru.com/a/11969602/119717: 1,255130 секунд
мой первый гибридный подход по адресу /questions/7778755/shablon-regex-i-ili-nsregularexpression-slishkom-medlennyij-poisk-v-ochen-bolshom-fajle-mozhno-li-ego-optimizirovat/7778760#7778760: 0,372215 секунд
мой второй гибридный подход по адресу /questions/7778755/shablon-regex-i-ili-nsregularexpression-slishkom-medlennyij-poisk-v-ochen-bolshom-fajle-mozhno-li-ego-optimizirovat/7778760#7778760: 0,337549 секунд
Лучшее время пока - вторая версия моего ответа. Я не могу отметить ни один из ответов наилучшим образом, поскольку все ответы, связанные с поиском, отражают подход, который я использовал в своей версии, поэтому все они очень полезны, а мой основан только на других. Я многому научился, и мой метод занял четверть первоначального времени, так что это было чрезвычайно полезно, спасибо dasblinkenlight и Ωmega за то, что обсудили это со мной.
4 ответа
Так как вы все равно помещаете весь файл в память, вы также можете представить его как структуру, которую легко найти:
- Создать изменчивый
NSDictionary words, сNSStringключи иNSMutableArrayценности - Прочитать файл в память
- Просмотрите строку, представляющую файл построчно
- Для каждого
line, выделите часть слова, ища'('или'\t'персонаж - Получить подстроку для слова (от нуля до индекса
'('или же'\t'минус один); Это вашаkey, - Проверьте, если
wordsсодержит вашkey; если нет, добавьте новыйNSMutableArray - добавлять
lineкNSMutableArrayчто вы нашли / создали на конкретномkey - Когда вы закончите, отбросьте исходную строку, представляющую файл.
Имея эту структуру в руках, вы сможете выполнять поиск в то время, когда ни один механизм регулярных выражений не сможет соответствовать, потому что вы заменили полнотекстовое сканирование, которое является линейным, поиском по хешу, который является постоянным. время.
** РЕДАКТИРОВАТЬ: ** Я проверил относительную скорость этого решения по сравнению с регулярным выражением, это примерно в 60 раз быстрее на симуляторе. Это совсем не удивительно, потому что шансы сильно зависят от решения на основе регулярных выражений.
Чтение файла:
NSBundle *bdl = [NSBundle bundleWithIdentifier:@"com.poof-poof.TestAnim"];
NSString *path = [NSString stringWithFormat:@"%@/words_pron.dic", [bdl bundlePath]];
data = [NSString stringWithContentsOfFile:path encoding:NSUTF8StringEncoding error:nil];
NSMutableDictionary *tmp = [NSMutableDictionary dictionary];
NSUInteger pos = 0;
NSMutableCharacterSet *terminator = [NSMutableCharacterSet characterSetWithCharactersInString:@"\t("];
while (pos != data.length) {
NSRange remaining = NSMakeRange(pos, data.length-pos);
NSRange next = [data
rangeOfCharacterFromSet:[NSCharacterSet newlineCharacterSet]
options:NSLiteralSearch
range:remaining
];
if (next.location != NSNotFound) {
next.length = next.location - pos;
next.location = pos;
} else {
next = remaining;
}
pos += (next.length+1);
NSString *line = [data substringWithRange:next];
NSRange keyRange = [line rangeOfCharacterFromSet:terminator];
keyRange.length = keyRange.location;
keyRange.location = 0;
NSString *key = [line substringWithRange:keyRange];
NSMutableArray *array = [tmp objectForKey:key];
if (!array) {
array = [NSMutableArray array];
[tmp setObject:array forKey:key];
}
[array addObject:line];
}
dict = tmp; // dict is your NSMutableDictionary ivar
Поиск:
NSArray *keys = [NSArray arrayWithObjects:@"sunday", @"monday", @"tuesday", @"wednesday", @"thursday", @"friday", @"saturday", nil];
NSMutableArray *all = [NSMutableArray array];
NSLog(@"Starting...");
for (NSString *key in keys) {
for (NSString *s in [dict objectForKey:key]) {
[all addObject:s];
}
}
NSLog(@"Done! %u", all.count);
Попробуй это:
^(?:change|monday|tuesday|wednesday|thursday|friday|saturday|sunday)(?:\([2-5]\))?\t.*$
а также этот (используя положительный прогноз со списком возможных первых букв):
^(?=[cmtwfs])(?:change|monday|tuesday|wednesday|thursday|friday|saturday|sunday)(?:\([2-5]\))?\t.*$
и в конце версия с некоторой оптимизацией:
^(?=[cmtwfs])(?:change|monday|t(?:uesday|hursday)|wednesday|friday|s(?:aturday|unday))(?:\([2-5]\))?\t.*$
Вот мой гибридный подход ответов dasblinkenlight и Ωmega, который я решил добавить в качестве ответа и на этом этапе. Он использует метод dasblinkenlight для прямого поиска по строке, а затем выполняет полное регулярное выражение в небольшом диапазоне в случае попадания, поэтому он использует тот факт, что словарь и слова для поиска находятся в алфавитном порядке и получают выгоду от оптимизированное регулярное выражение. Жаль, что у меня не было двух лучших проверок ответа! Это дает правильные результаты и занимает около половины времени подхода регулярных выражений на симуляторе (позже я должен протестировать устройство, чтобы узнать, каково сравнение времени на iPhone 4, который является эталонным устройством):
NSMutableArray *mutableArrayOfWordsToMatch = [[NSMutableArray alloc] initWithArray:array];
NSMutableArray *mutableArrayOfUnfoundWords = [[NSMutableArray alloc] init]; // I also need to know the unfound words.
NSUInteger pos = 0;
NSMutableString *mutablePatternString = [[NSMutableString alloc]initWithString:@"^(?:"];
int firstRound = 0;
for(NSString *word in array) {
if(firstRound == 0) { // this is the first round
firstRound++;
} else { // this is all later rounds
[mutablePatternString appendString:[NSString stringWithFormat:@"|"]];
}
[mutablePatternString appendString:[NSString stringWithFormat:@"%@",word]];
}
[mutablePatternString appendString:@")(?:\\([2-5]\\))?\t.*$"];
// This creates a string that reads "^(?:change|friday|model|monday|quidnunc|saturday|sunday|thursday|tuesday|wednesday)(?:\([2-5]\))?\t.*$"
// We don't want to instantiate the NSRegularExpression in the loop so let's use a pattern that matches everything we're interested in.
NSRegularExpression * regularExpression = [NSRegularExpression regularExpressionWithPattern:mutablePatternString
options:NSRegularExpressionAnchorsMatchLines
error:nil];
NSMutableArray * matches = [NSMutableArray array];
while (pos != data.length) {
if([mutableArrayOfWordsToMatch count] <= 0) { // If we're at the top of the loop without any more words, stop.
break;
}
NSRange remaining = NSMakeRange(pos, data.length-pos);
NSRange next = [data
rangeOfString:[NSString stringWithFormat:@"\n%@\t",[mutableArrayOfWordsToMatch objectAtIndex:0]]
options:NSLiteralSearch
range:remaining
]; // Just search for the first pronunciation.
if (next.location != NSNotFound) {
// If we find the first pronunciation, run the whole regex on a range of {position, 500} only.
int rangeLocation = next.location;
int searchPadding = 500;
int rangeLength = searchPadding;
if(data.length - next.location < searchPadding) { // Only use 500 if there is 500 more length in the data.
rangeLength = data.length - next.location;
}
[regularExpression enumerateMatchesInString:data
options:0
range:NSMakeRange(rangeLocation, rangeLength)
usingBlock:^(NSTextCheckingResult *result, NSMatchingFlags flags, BOOL *stop){
[matches addObject:[data substringWithRange:result.range]];
}]; // Grab all the hits at once.
next.length = next.location - pos;
next.location = pos;
[mutableArrayOfWordsToMatch removeObjectAtIndex:0]; // Remove the word.
pos += (next.length+1);
} else { // No hits.
[mutableArrayOfUnfoundWords addObject:[mutableArrayOfWordsToMatch objectAtIndex:0]]; // Add to unfound words.
[mutableArrayOfWordsToMatch removeObjectAtIndex:0]; // Remove from the word list.
}
}
[mutablePatternString release];
[mutableArrayOfUnfoundWords release];
[mutableArrayOfWordsToMatch release];
// return matches to caller
РЕДАКТИРОВАТЬ: вот еще одна версия, которая не использует регулярные выражения и экономит немного больше времени от метода:
NSMutableArray *mutableArrayOfWordsToMatch = [[NSMutableArray alloc] initWithArray:array];
NSMutableArray *mutableArrayOfUnfoundWords = [[NSMutableArray alloc] init]; // I also need to know the unfound words.
NSUInteger pos = 0;
NSMutableArray * matches = [NSMutableArray array];
while (pos != data.length) {
if([mutableArrayOfWordsToMatch count] <= 0) { // If we're at the top of the loop without any more words, stop.
break;
}
NSRange remaining = NSMakeRange(pos, data.length-pos);
NSRange next = [data
rangeOfString:[NSString stringWithFormat:@"\n%@\t",[mutableArrayOfWordsToMatch objectAtIndex:0]]
options:NSLiteralSearch
range:remaining
]; // Just search for the first pronunciation.
if (next.location != NSNotFound) {
NSRange lineRange = [data lineRangeForRange:NSMakeRange(next.location+1, next.length)];
[matches addObject:[data substringWithRange:NSMakeRange(lineRange.location, lineRange.length-1)]]; // Grab the whole line of the hit.
int rangeLocation = next.location;
int rangeLength = 750;
if(data.length - next.location < rangeLength) { // Only use the searchPadding if there is that much room left in the string.
rangeLength = data.length - next.location;
}
rangeLength = rangeLength/5;
int newlocation = rangeLocation;
for(int i = 2;i < 6; i++) { // We really only need to do this from 2-5.
NSRange morematches = [data
rangeOfString:[NSString stringWithFormat:@"\n%@(%d",[mutableArrayOfWordsToMatch objectAtIndex:0],i]
options:NSLiteralSearch
range:NSMakeRange(newlocation, rangeLength)
];
if(morematches.location != NSNotFound) {
NSRange moreMatchesLineRange = [data lineRangeForRange:NSMakeRange(morematches.location+1, morematches.length)]; // Plus one because I don't actually want the line break at the beginning.
[matches addObject:[data substringWithRange:NSMakeRange(moreMatchesLineRange.location, moreMatchesLineRange.length-1)]]; // Minus one because I don't actually want the line break at the end.
newlocation = morematches.location;
} else {
break;
}
}
next.length = next.location - pos;
next.location = pos;
[mutableArrayOfWordsToMatch removeObjectAtIndex:0]; // Remove the word.
pos += (next.length+1);
} else { // No hits.
[mutableArrayOfUnfoundWords addObject:[mutableArrayOfWordsToMatch objectAtIndex:0]]; // Add to unfound words.
[mutableArrayOfWordsToMatch removeObjectAtIndex:0]; // Remove from the word list.
}
}
[mutableArrayOfUnfoundWords release];
[mutableArrayOfWordsToMatch release];
Глядя на файл словаря, который вы предоставили, я бы сказал, что разумной стратегией может быть чтение данных и помещение их в любое постоянное хранилище данных.
Прочитайте файл и создайте объекты для каждого уникального слова, n строки произношения (где n количество уникальных произношений). Словарь уже в алфавитном порядке, поэтому, если вы проанализируете его в том порядке, в котором вы читаете, вы получите алфавитный список.
Затем вы можете выполнить бинарный поиск по данным - даже с ОГРОМНЫМ числом объектов, бинарный поиск найдет то, что вы ищете очень быстро (в алфавитном порядке).
Вы, вероятно, могли бы даже сохранить все это в памяти, если бы вам нужна молниеносная производительность.