Я заинтересовался этим небольшим примером алгоритма в Python для циклического прохождения большого списка слов. Я пишу несколько «инструментов», которые позволят мне нарезать строку или массив Objective-C аналогично Python.
В частности, это элегантное решение привлекло мое внимание к очень быстрому выполнению, и оно использует срез строки в качестве ключевого элемента алгоритма. Попробуйте и решить это без среза!
Я воспроизвел свою локальную версию, используя список слов Moby ниже. Вы можете использовать /usr/share/dict/words, если не хотите загружать Moby. Источник - просто большой словарный список уникальных слов.
#!/usr/bin/env python
count=0
words = set(line.strip() for line in
open("/Users/andrew/Downloads/Moby/mwords/354984si.ngl"))
for w in words:
even, odd = w[::2], w[1::2]
if even in words and odd in words:
count+=1
print count
Этот скрипт будет а) интерпретироваться Python; b) прочитайте файл словаря Moby размером 4,1 МБ, 354 983 слова; в) лишить линии; d) поместите линии в набор и; д) и найти все комбинации, где четные и вероятные значения данного слова также являются словами. Это выполняется примерно за 0,73 секунды на MacBook Pro.
Я пытался переписать ту же программу в Objective-C. Я новичок в этом языке, поэтому, пожалуйста, будьте спокойны, но, пожалуйста, укажите на ошибки.
#import <Foundation/Foundation.h>
NSString *sliceString(NSString *inString, NSUInteger start, NSUInteger stop,
NSUInteger step){
NSUInteger strLength = [inString length];
if(stop > strLength) {
stop = strLength;
}
if(start > strLength) {
start = strLength;
}
NSUInteger capacity = (stop-start)/step;
NSMutableString *rtr=[NSMutableString stringWithCapacity:capacity];
for(NSUInteger i=start; i < stop; i+=step){
[rtr appendFormat:@"%c",[inString characterAtIndex:i]];
}
return rtr;
}
NSSet * getDictWords(NSString *path){
NSError *error = nil;
NSString *words = [[NSString alloc] initWithContentsOfFile:path
encoding:NSUTF8StringEncoding error:&error];
NSCharacterSet *sep=[NSCharacterSet newlineCharacterSet];
NSPredicate *noEmptyStrings =
[NSPredicate predicateWithFormat:@"SELF != ''"];
if (words == nil) {
// deal with error ...
}
// ...
NSArray *temp=[words componentsSeparatedByCharactersInSet:sep];
NSArray *lines =
[temp filteredArrayUsingPredicate:noEmptyStrings];
NSSet *rtr=[NSSet setWithArray:lines];
NSLog(@"lines: %lul, word set: %lul",[lines count],[rtr count]);
[words release];
return rtr;
}
int main (int argc, const char * argv[])
{
NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];
int count=0;
NSSet *dict =
getDictWords(@"/Users/andrew/Downloads/Moby/mwords/354984si.ngl");
NSLog(@"Start");
for(NSString *element in dict){
NSString *odd_char=sliceString(element, 1,[element length], 2);
NSString *even_char=sliceString(element, 0, [element length], 2);
if([dict member:even_char] && [dict member:odd_char]){
count++;
}
}
NSLog(@"count=%i",count);
[pool drain];
return 0;
}
Версия Objective-C дает тот же результат (13 341 слово), но на это уходит почти 3 секунды. Я должен делать что-то ужасно неправильное, чтобы скомпилированный язык был более чем в 3 раза медленнее, чем язык сценариев, но я буду проклят, если пойму, почему.
Основной алгоритм тот же: читайте строки, разбирайте их и складывайте в набор.
Мое предположение о том, что является медленным, - это обработка элементов NSString, но я не знаю альтернативы.
Редактировать
Я отредактировал Python так:
#!/usr/bin/env python
import codecs
count=0
words = set(line.strip() for line in
codecs.open("/Users/andrew/Downloads/Moby/mwords/354984si.ngl",
encoding='utf-8'))
for w in words:
if w[::2] in words and w[1::2] in words:
count+=1
print count
Чтобы utf-8 находился в одной плоскости с строкой utf-8 NSString. Это замедлило Питона до 1,9 с.
Я также переключаю тест среза на тип короткого замыкания, как предложил для версий Python и obj-c. Теперь они близки к одинаковой скорости. Я также пытался использовать массивы C, а не NSStrings, и это было намного быстрее, но не так просто. Вы также теряете поддержку utf-8, делая это.
Python действительно классный ...
Редактировать 2
Я нашел узкое место, которое значительно ускорило ситуацию. Вместо использования метода [rtr appendFormat:@"%c",[inString characterAtIndex:i]]; для добавления символа в возвращаемую строку, я использовал это:
for(NSUInteger i=start; i < stop; i+=step){
buf[0]=[inString characterAtIndex:i];
[rtr appendString:[NSString stringWithCharacters:buf length:1]];
}
Теперь я могу наконец утверждать, что версия Objective C быстрее, чем версия Python, но ненамного.