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

我对这个在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和obj-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版本快——但并没有多。

请记住，Python版本在CPython上执行时，已经将许多繁重的工作移到了高度优化的C代码中(特别是文件输入缓冲，字符串切片和哈希表查找，以检查even和odd是否在words中)。

也就是说，你似乎在Objective-C代码中将文件解码为UTF-8，但在Python代码中以二进制形式保留文件。在Objective-C版本中使用Unicode NSString，而在Python版本中使用8位字节字符串并不是一个真正公平的比较——如果你使用codecs.open()打开声明编码为"utf-8"的文件，我预计Python版本的性能会明显下降。

您还在Objective-C中进行了完整的第二次传递以剥离空行，而Python代码中没有这样的步骤。

在这两个代码中，您构建偶数和奇数片，然后针对单词测试它们。如果只在偶数片成功之后才构建奇数片会更好。

当前Python代码:

even, odd = w[::2], w[1::2]
if even in words and odd in words:

更好:

# even, odd = w[::2], w[1::2]
if w[::2] in words and w[1::2] in words:

顺便说一下，你没有提到的一个指标是:你写每段代码花了多长时间?

http://developer.apple.com/library/mac/#documentation/Cocoa/Reference/Foundation/Classes/NSSet_Class/Reference/Reference.html建议您可能需要用CFSet代替NSSet，这可能会提高性能。

我无法通过快速谷歌搜索找到用于NSSet/CFSet的实现:如果他们使用基于树的实现(与stdc++ set类型相同)，那么查找和检查是O(log(N))，而Python的集合查找是O(1)，这可以解释速度差异。

[edit] ncoghlan在下面的注释中指出，objective C中的集合使用哈希表，因此您也可以获得常数时间查找。因此，这归结为Python与Objective c中实现集合的效率。正如其他人指出的那样，Python的集合和字典进行了大量优化，特别是当字符串用作键时(Python字典用于实现命名空间，需要非常快)。

你的python代码主要在内置数据结构中运行，这些数据结构是用c语言实现的。python为这些数据类型包含了令人难以置信的复杂优化。更多细节请关注雷蒙德·赫廷格的谈话。它主要是关于非常有效的对象哈希，使用这些哈希查找，特殊的内存分配策略，…

我用python实现了一个网络搜索，只是为了测试，我们从来没有能够在c++， c#或类似的语言中加速它。不是c++或c#的初学者!

首先，CPython的库是用C编写的，并且是高度优化的，所以利用该库的程序比未优化的Objective C运行得更快也就不足为奇了。

如果你将Objective - C程序逐行翻译成Python，结果将会不同。

我怀疑大部分结果是由于计数器不经常增加，并且Python非常有效地确定对象不在集合中。毕竟，如果您取一个单词的每两个字母，似乎不太可能最终得到一个有效的英语单词，更不用说同一源文本中的单词了。

相关内容

最新更新

热门标签：