为什么这个程序在Python中比在Objective-C中更快？

Question

我对这个小例子产生了兴趣，内容是用Python编写的算法，用来遍历一个很大的单词列表。我正在写一些“工具”，希望能像Python那样对Objective-C中的字符串或数组进行切片操作。

特别是，这个优雅的解决方案引起了我的注意，因为它执行得非常快，并且在算法中使用了字符串切片作为关键元素。试着不使用切片来解决这个问题！

我在下面用Moby单词列表复现了我的本地版本。如果你不想下载Moby，可以使用/usr/share/dict/words。这个源文件就是一个包含独特单词的大字典列表。

#!/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元素的过程，但我不知道有什么替代方法。

编辑

我把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和Objective-C版本的速度现在差不多了。我还尝试使用C数组而不是NSString，这样速度快了很多，但不太容易。而且这样会失去对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版本快了——但差别不大。

集合操作性能比较编程语言数据结构字符串处理算法优化切片操作 utf-8编码

为什么这个程序在Python中比在Objective-C中更快？

5 个回答

撰写回答