Я заинтересовался этим небольшим примером алгоритма в Python для прокрутки большого списка слов. Я пишу несколько "инструментов", которые позволят мне нарезать строку или массив Objective-C так же, как Python.
В частности, это элегантное решение привлекло мое внимание для выполнения очень быстро, и он использует строковый срез в качестве ключевого элемента алгоритма. Попробуйте и решите это без кусочка!
Я воспроизвел свою локальную версию, используя список слов Моби > ниже. Вы можете использовать /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
Этот script будет a) интерпретироваться Python; б) читать файл словаря Moby объемом 4.1 MB, 354 983 слов; c) линять линии; 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, но я не знаю альтернативы.
Edit
Я редактировал 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. Это замедлило Python до 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, но не сильно.