优化Python的for循环

Question

这里有两个程序，它们简单地计算小于等于 n 的素数个数。
一个是用 Python 写的，另一个是用 Java 写的。

public class prime{
    public static void main(String args[]){
        int n = Integer.parseInt(args[0]);
        int nps = 0;
 boolean isp;

        for(int i = 1; i <= n; i++){
            isp = true;

            for(int k = 2; k < i; k++){
               if( (i*1.0 / k) == (i/k) ) isp = false;
            }
            if(isp){nps++;}
 }
        System.out.println(nps);
    }
}


`#!/usr/bin/python`                                                                                                                                        
import sys
n = int(sys.argv[1])
nps = 0

for i in range(1,n+1):
    isp = True
    for k in range(2,i):
        if( (i*1.0 / k) == (i/k) ): isp = False
    if isp == True: nps = nps + 1
print nps

在 n=10000 的情况下运行它们，我得到了以下的时间记录。
shell:~$ time python prime.py 10000 && time java prime 10000
1230

真实时间 0m49.833s
用户时间 0m49.815s
系统时间 0m0.012s
1230

真实时间 0m1.491s
用户时间 0m1.468s
系统时间 0m0.016s

我在 Python 中使用 for 循环的方式是否不对，还是说 Python 本身就是这么慢？

我并不是在寻找专门用于计算素数的答案，而是想知道 Python 代码通常是否可以更聪明地使用。

Java 代码是用以下命令编译的：
javac 1.6.0_20
用 java 版本 "1.6.0_18" 运行
OpenJDK 运行环境 (IcedTea6 1.8.1) (6b18-1.8.1-0ubuntu1~9.10.1)
OpenJDK 客户端虚拟机 (构建 16.0-b13, 混合模式, 共享)

Python 版本是：
Python 2.6.4 (r264:75706, 2009年12月7日, 18:45:15)

Answer 1

你可以通过把那个复杂的测试换成下面的代码，让你的Python程序速度快大约一倍。

if i % k == 0: isp = False

如果在isp = False之后加一个break，你的程序在n=10000时速度可以快到大约八倍。

另外，建议你跳过偶数（从nps开始加1来包含2）。

最后，你只需要让k的值到达sqrt(i)就可以了。

当然，如果你在Java中做同样的改动，它的速度仍然比优化后的Python快大约10倍。

Answer 2

是的，Python的速度确实比较慢，大约比C语言慢一百倍。你可以用xrange来代替range，这样能稍微快一点，但除此之外也没什么特别的。

你主要的问题在于，你在用普通的Python写代码，而不是使用一些优化过的库，比如Numpy或Psyco，这些库能让你的代码运行得更快。

Java有一个即时编译器（jit），在处理大量数字时，这个编译器能带来很大的性能提升。

Answer 3

正如大家所提到的，普通的Python其实不太适合这种情况。而且，判断质数的算法比较简单也不是重点。不过，我通过两个简单的方法，成功把Python的运行时间大大缩短了，尽管还是用了原来的算法。

首先，把所有的代码放到一个函数里，可以叫它main()或者别的名字。这样做让我在机器上运行Python的时间从20.6秒减少到了14.54秒。全局运行的代码比放在函数里的要慢。

其次，使用Psyco，一个即时编译器。这需要在文件顶部加两行代码（当然，你得先安装Psyco）：

import psyco
psyco.full()

这样一来，最终的运行时间就变成了2.77秒。

最后补充一下。我为了好玩，试着用Cython来做，结果时间降到了0.8533秒。不过，想要知道怎么做出快速的Cython代码，我不太建议普通用户去尝试。