我感兴趣了这个小例子 https://stackoverflow.com/questions/5523058/how-to-optimize-this-python-code-from-thinkpython-exercise-10-10/5523071#comment-6276679Python 中循环遍历大型单词列表的算法。我正在编写一些“工具”,允许我以与 Python 类似的方式对 Objective-C 字符串或数组进行切片。
具体来说,这个优雅的解决方案 https://stackoverflow.com/questions/5523058/how-to-optimize-this-python-code-from-thinkpython-exercise-10-10/5523071#5523071因其执行速度非常快而引起了我的注意,它使用字符串切片作为算法的关键元素。尝试在不切片的情况下解决这个问题!
我已经使用复制了我的本地版本莫比单词表 http://icon.shef.ac.uk/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
该脚本将 a) 由 Python 解释; b) 读取 4.1 MB、354,983 字的 Moby 词典文件; c) 剥线; d) 将线路放入一组; e) 找到给定单词的偶数和奇数也是单词的所有组合。在 MacBook Pro 上执行大约需要 0.73 秒。
我尝试用 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 秒。
我还将切片测试切换为短路类型建议 https://stackoverflow.com/questions/5616847/why-is-this-program-faster-in-python-than-objective-c/5617487#5617487对于 Python 和 obj-c 版本。现在他们的速度已经接近了。我还尝试使用 C 数组而不是 NSString,这更快,但没那么容易。这样做也会失去对 utf-8 的支持。
Python 真的很酷...
Edit 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]];
}
现在我能finally声称 Objective-C 版本比 Python 版本快——但快不了多少。