为什么Python对于简单的for循环来说太慢了？

Question

我们正在使用Python 制作一些kNN和SVD实现.其他人选择了Java.我们的执行时间非常不同.我使用cProfile来查看我在哪里犯错但实际上一切都很好.是的,我numpy也用.但我想问一个简单的问题.

total = 0.0
for i in range(9999): # xrange is slower according 
    for j in range(1, 9999):            #to my test but more memory-friendly.
        total += (i / j)
print total

这段代码在我的电脑上占用了31.40秒.

此代码的Java版本在同一台计算机上占用1秒或更短时间.我想,类型检查是这段代码的主要问题.但我应该为我的项目做很多这样的操作,我认为9999*9999不是那么大的数字.

我想我犯了错​​误,因为我知道Python被很多科学项目所使用.但是为什么这段代码这么慢,我怎么能处理比这更大的问题呢？

我应该使用JIT编译器Psyco吗？

编辑

我还说这个循环问题只是一个例子.代码并不像这样简单,可能很难将改进/代码示例付诸实践.

另一个问题是,我可以实现大量的数据挖掘和机器学习算法与numpy和scipy,如果我正确地使用它？

Answer 1

我想我犯了错​​误,因为我知道Python被很多科学项目所使用.

他们大量使用SciPy(NumPy是最突出的组件,但我听说围绕NumPy的API开发的生态系统更为重要),这大大加快了这些项目所需的各种操作.你做错了什么:你不是用C 编写你的关键代码.一般来说,Python非常适合开发,但是扩展良好的扩展模块本身就是一个至关重要的优化(至少当你处理数字时) .Python是一种非常糟糕的语言,用于实现紧密的内部循环.

默认(当时最受欢迎和广泛支持的)实现是一个简单的字节码解释器.即使是最简单的操作,如整数除法,也可能需要数百个CPU周期,多个内存访问(类型检查是一个流行的例子),几个C函数调用等,而不是几个(甚至单个,在整数的情况下)分裂)指令.此外,该语言设计有许多抽象,增加了开销.如果你使用xrange,你的循环会在堆上分配9999个对象 - 如果你使用range(9999*9999整数减去256*256左右,对于缓存的小整数)则更多.此外,该xrange版本在每次迭代时调用一个方法来推进 - range如果序列上的迭代没有被特别优化,那么版本也是如此.它仍然需要一个完整的字节码调度,这本身就非常复杂(当然,与整数除法相比).

看看什么是JIT会很有趣(我推荐PyPy而不是Psyco,后者不再是主动开发的,而且范围非常有限 - 尽管如此,它可能适用于这个简单的例子).经过一小部分迭代之后,它应该产生一个最优的机器代码循环,增加一些防护 - 简单的整数比较,如果它们失败则跳跃 - 以保持正确性,以防你在该列表中得到一个字符串.Java可以做到同样的事情,只是更早(它不必先跟踪)和更少的防护(至少如果你使用ints).这就是它快得多的原因.

Answer 2

因为你提到科学代码,看看numpy.您正在做的事情可能已经完成(或者更确切地说,它使用LAPACK来处理像SVD这样的事情).当你听说python被用于科学代码时,人们可能并不是指你在你的例子中使用它.

作为一个简单的例子:

(如果你使用python3,你的例子会使用浮点除法.我的例子假设你使用python2.x,因此整数除法.如果不是,请指定i = np.arange(9999, dtype=np.float)等)

import numpy as np
i = np.arange(9999)
j = np.arange(1, 9999)
print np.divide.outer(i,j).sum()

给出时间的一些想法...(我将在这里使用浮点除法,而不是像你的例子中的整数除法):

import numpy as np

def f1(num):
    total = 0.0
    for i in range(num): 
        for j in range(1, num):
            total += (float(i) / j)
    return total

def f2(num):
    i = np.arange(num, dtype=np.float)
    j = np.arange(1, num, dtype=np.float)
    return np.divide.outer(i, j).sum()

def f3(num):
    """Less memory-hungry (and faster) version of f2."""
    total = 0.0
    j = np.arange(1, num, dtype=np.float)
    for i in xrange(num):
        total += (i / j).sum()
    return total

如果我们比较时间:

In [30]: %timeit f1(9999)
1 loops, best of 3: 27.2 s per loop

In [31]: %timeit f2(9999)
1 loops, best of 3: 1.46 s per loop

In [32]: %timeit f3(9999)
1 loops, best of 3: 915 ms per loop

Answer 3

我认为 NumPy 可以比 CPython for loops 更快（我没有在 PyPy 中测试）。

我想从 Joe Kington 的代码开始，因为这个答案使用了 NumPy。

%timeit f3(9999)
704 ms ± 2.33 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

我自己：

def f4(num):
    x=np.ones(num-1)
    y=np.arange(1,num)
    return np.sum(np.true_divide(x,y))*np.sum(y)

155 µs ± 284 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

此外，高中数学可以将问题简化为计算机。

Problem= (1+2+...+(num-1)) * (1/1+1/2+...+1/(num-1))
1+2+...+(num-1)=np.sum(np.arange(1,num))=num*(num-1)/2
1/1+1/2+...+1/(num-1)=np.true_divide (1,y)=np.reciprocal(y.astype(np.float64))

所以，

def f5(num):
    return np.sum(np.reciprocal(np.arange(1, num).astype(np.float64))) * num*(num-1)/2
%timeit f5(9999)
106 µs ± 615 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

此外，大学数学更能将问题简化为计算机。

1/1+1/2+...+1/(num-1)=np.log(num-1)+1/(2*num-2)+np.euler_gamma
(n>2)

np.euler_gamma: Euler-Mascheroni 常数 (0.57721566...)

由于 NumPy 中 Euler-Mascheroni 常数的不准确，你会失去像 489223499.9 991845 -> 489223500.0 408554这样的准确度。如果您可以忽略 0.0000000085% 的不准确度，您可以节省更多时间。

def f6(num):
    return (np.log(num-1)+1/(2*num-2)+np.euler_gamma)* num*(num-1)/2
%timeit f6(9999)
4.82 µs ± 29.1 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

NumPy 的好处随着输入的增加而变得更大。

%timeit f3(99999)
56.7 s ± 590 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit f5(99999)
534 µs ± 86.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit f5(99999999)
1.42 s ± 15.4 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
9.498947911958**416**e+16
%timeit f6(99999999)
4.88 µs ± 26.7 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
9.498947911958**506**e+16
%timeit f6(9999999999999999999)
17.9 µs ± 921 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

在特殊情况下，您可以使用 numba（不幸的是并非总是如此）。

from numba import jit
@jit
def f7(num):
    return (np.log(num-1)+1/(2*num-2)+np.euler_gamma)* num*(num-1)/2
# same code with f6(num)

%timeit f6(999999999999999)
5.63 µs ± 29.6 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
f7(123) # compile f7(num)
%timeit f7(999999999999999)
331 ns ± 1.9 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit f7(9999)
286 ns ± 3.09 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

因此，我建议将 NumPy、数学和 numba 结合使用。

Answer 4

Python for 循环是静态类型和解释的。没有编译。Java 速度更快，因为它具有 Python 没有的额外 JIT 加速功能。

http://en.wikipedia.org/wiki/Just-in-time_compilation

为了说明 Java JIT 产生的巨大差异，请看这个大约需要 5 分钟的 Python 程序：

if __name__ =='__main__':
    total = 0.0
    i=1
    while i<=9999:
        j=1
        while j<=9999:
            total=1
            j+=1
        i+=1
    print total

虽然这个基本等效的 Java 程序需要大约 23 毫秒：

public class Main{
    public static void main(String args[]){
        float total = 0f; 

        long start_time = System.nanoTime();
        int i=1;

        while (i<=9999){
            int j=1;
            while(j<=9999){
                total+=1;
                j+=1;
            }
            i+=1;
        }
        long end_time = System.nanoTime();

        System.out.println("total: " + total);
        System.out.println("total milliseconds: " + 
           (end_time - start_time)/1000000);
    }
}

就在 for 循环中执行任何操作而言，Java 以 1 到 1000 个数量级的速度清理 python 的时钟。

这个故事的寓意是：如果需要快速的性能，应该不惜一切代价避免使用基本的 Python for 循环。这可能是因为 Guido van Rossum 想要鼓励人们使用多处理器友好的结构，比如数组拼接，它的运行速度比 Java 快。

Answer 5

这是一个众所周知的现象——python 代码是动态的和解释性的，java 代码是静态类型化和编译的。那里没有惊喜。

人们偏爱 python 的原因通常是：

• 较小的代码库
• 更少的冗余（更多的 DRY）
• 更干净的代码

但是，如果您使用用 C 编写的库（来自 python），性能可能会好得多（比较： pickleto cpickle）。

Answer 6

您会发现列表推导式或生成器表达式要快得多。例如：

total = sum(i / j for j in xrange(1, 9999) for i in xrange(9999))

这在我的机器上执行约 11 秒，而原始代码执行约 26 秒。仍然比 Java 慢一个数量级，但这更符合您的预期。

顺便说一下，您的原始代码可以通过初始化total为0而不是0.0使用整数而不是浮点加法来稍微加快速度。您的除法都具有整数结果，因此将结果求和为浮点数是没有意义的。

在我的机器上，Psyco 实际上将生成器表达式减慢到与原始循环大致相同的速度（它根本不加速）。

Answer 7

使用kindall的列表理解

total = sum(i / j for j in xrange(1, 9999) for i in xrange(9999))

是 10.2 秒，使用 pypy 1.7 是2.5秒。这很有趣，因为 pypy 也将原始版本加速到 2.5 秒。因此，对于 pypy 列表理解将是过早的优化；)。干得好皮皮！

Answer 8

Python的好处是,与Java(你只有这种反射机制)相比,它有更多的灵活性(例如,类是对象)

这里没有提到的是Cython.它允许引入类型变量并将您的示例转换为C/C++.然后它快得多.我也改变了循环中的界限......

from __future__ import division

cdef double total = 0.00
cdef int i, j
for i in range(9999):
    for j in range(1, 10000+i):
        total += (i / j)

from time import time
t = time()
print("total = %d" % total)
print("time = %f[s]" % (time() - t))

其次是

$ cython loops.pyx
$ gcc -I/usr/include/python2.7 -shared -pthread -fPIC -fwrapv -Wall -fno-strict-aliasing -O3 -o loops.so loops.c
$ python -c "import loops"

给

total = 514219068
time = 0.000047[s]