logo标签列表

优化Python循环

pythonoptimization
4

我有一个循环是特定函数中最耗费时间的部分，我想加快它的速度。当前，这个单一循环需要大约400毫秒的时间，而函数其他部分的执行只需要大约610毫秒。

代码如下:

for ctr in xrange(N):
    list1[ctr] = in1[ctr] - in1[0] - ctr * c1
    list2[ctr] = in2[ctr] - in2[0] - ctr * c2
    list3[ctr] = c3 - in1[ctr]
    list4[ctr] = c4 - in2[ctr]

N 的值可以从大约 40,000 到 120,000 不等，它是所有列表（in1、in2、listN）的长度。
有没有人知道一些 Python 技巧来加速这个过程？我已经尝试使用 map 来代替循环，因为我知道它会编译成更有效率的代码，但结果比原来慢了大约 250 毫秒。
谢谢。
9个回答
9
假设list1、list2等都是数字，考虑使用numpy数组代替列表。对于大量整数或浮点数序列，您将看到显著的加速。
如果您选择这条路线，您上面的循环可以写成这样：
ctr = np.arange(N)
list1 = n1 - n1[0] - ctr * c1
list2 = n2 - n2[0] - ctr * c2
list3 = c3 - ctr
list4 = c4 - ctr

以下是关于计时的完整示例：

import numpy as np
N = 100000

# Generate some random data...
n1 = np.random.random(N)
n2 = np.random.random(N)
c1, c2, c3, c4 = np.random.random(4)

ctr = np.arange(N)
list1 = n1 - n1[0] - ctr * c1
list2 = n2 - n2[0] - ctr * c2
list3 = c3 - ctr
list4 = c4 - ctr

当然，如果你的list1，list2等不是数字（即除浮点数或整数以外的python对象列表），那么这种方法就不适用。
1
使用np.linspace可能比ctr * c1和ctr * c2更快。或者也可能不是，需要通过性能分析来确定。 - Michael J. Barber
@Michael J. Barber - 内部 linspace 只是做 np.arange(0，num) * step + start，因此我怀疑它比 ctr * c1 更快。当然，正如你所说，这最好由分析确定，而我还没有检查过。无论如何，上面的代码片段仍有很多优化空间。 - Joe Kington
1
这个优化将总执行时间从600毫秒加速到185毫秒。对我来说已经足够快，因为在这之后还有一些需要100毫秒的FFT，而我知道我无法加速它们。谢谢！ - bheklilr
2
最初有一点错误（见下文），这些应该更恰当地被缓存。
# These can be cached as they do not change.
base_in1 = in1[0]
base_in2 = in2[0]
for ctr in xrange(N):
    # these are being looked up several times. Look-ups take time in almost every
    # language. Look them up once and then use the new value.
    cin1 = in1[ctr]
    cin2 = in2[ctr]
    list1[ctr] = cin1 - base_in1 - ctr * c1
    list2[ctr] = cin2 - base_in2 - ctr * c2
    list3[ctr] = c3 - cin1
    list4[ctr] = c4 - cin2

（以下是错误）：

最初我认为可以通过缓存常量来解决此问题：

# these values never change
ctr1 = ctr * c1
ctr2 = ctr * c2
in10 = ctr1 + in1[0]
in20 = ctr2 + in2[0]
for ctr in xrange(N):
    # these are being looked up several times. That costs time.
    # look them up once and then use the new value.
    cin1 = in1[ctr]
    cin2 = in2[ctr]
    list1[ctr] = cin1 - in10
    list2[ctr] = cin2 - in20
    list3[ctr] = c3 - cin1
    list4[ctr] = c4 - cin2

但是正如 Tim 指出的那样，我在最初尝试中错过了 ctr。
实际上，像这样的查找只在一些解释性语言（如Python）中才会产生成本，例如Java就不需要这样做。但是在Python中确实可以获得很大的性能提升。 - Voo
@Voo 这取决于情况。如果你在谈论数组查找，那么我会同意你的观点，但大多数情况下，你更可能处理 List<T,T>，如果不正确地执行查找操作，它们可能是非常昂贵的。 - cwallenpoole
现在大多数编译器/即时编译器都会进行公共子表达式消除（CSE），因此会以与手动优化相同的方式优化代码。唯一的例外是volatile变量，但在这种情况下，手动更改已经改变了语义。现在我相信人们可以通过某种方式混淆代码以混淆编译器/即时编译器；）但通常应该可以工作。 - Voo
@Voo 当你使用List.get(2540)而你的List实际上是LinkedList时，问题就出现了。没有编译器可以为你解决这个问题，只能耗费时间来解决。 - cwallenpoole
如果编译器可以证明get没有副作用，它就可以并且会这样做。现在这并不一定是微不足道的，这取决于语言，所以你可能是正确的（在C++中很容易实现，感谢const，而Java中的JIT也应该能够实现）。 - Voo
1

优化取决于编译器，但有几件事情可以尝试。很高兴看到您正在对代码进行分析！

您可以尝试：

  1. 首先将in1 [ctr]和其他多次使用的表达式存储在变量中（尽管大多数编译器已经可以做到这一点，但谁知道呢）。

  2. 循环分裂（http://en.wikipedia.org/wiki/Loop_fission），以防您遇到缓存问题，交替使用大型数组。

1
据我所观察，Python 在连续的数学表达式方面表现不佳，会导致严重的减速。你最好的选择可能是像其他人建议的那样使用 numpy，这样代码就可以在 C 中运行。另一个可以尝试的 Python 优化方法是使用列表推导式。列表推导式通常比 map 更快。
in = in1[0]
list1 = [x - in - i * c1 for i, x in enumerate(in1)]

这种方法根本不涉及使用xrange（使用Python非常强大的迭代函数）。

使用timeit的示例。

>>> import timeit
>>> timeit.timeit(stmt="[x * 2 for x in xrange(1000)]", number=10000)
8.27007...
>>> timeit.timeit(stmt="map(lambda x: x * 2, xrange(1000))", number=10000)
19.5969...
>>> timeit.timeit(stmt="""lst=[0]*1000
for x in xrange(1000):
    lst[x] = x * 2
""", number=10000)
13.7785...
# this last one doesn't actually do what you want it to do, but for comparison
# it's faster because it doesn't have to store any data from the computation
>>> timeit.timeit(stmt="for x in xrange(1000): x * 2", number=10000)
6.98619...

（如果您需要帮助构建其他4个列表推导式，请在评论中提出）

编辑：一些timeit示例。

0
xrange()比itertools.count()更高效 :-/ - Aaron Digulla
0

只有在具有随机访问的情况下，地图才有用。在您的情况下，列表是正确的数据类型。

尝试从循环中提取常量in1[0] - ctr * c1和in2[0] - ctr * c2。哎呀。 ctr不是一个常量。您可以尝试x1 = c1，然后x1 += c1，但我认为在今天的CPU上，加法并不比乘法快多少。

然后，您应该查看数组模块或Numpy。与您的代码中创建list3不同，创建in1的副本，反转所有元素（*-1），然后将c3添加到每个元素中。数组/Numpy的大规模变异方法将使此过程更快。

除此之外，如果不涉及代码的其他部分，你几乎无法做任何事情。例如，你可以创建对象来返回必要的值，而不是实际计算list3和list4。但我猜你需要所有的值，所以这并没有什么帮助。

如果速度还不够快，你将不得不使用另一种语言或编写一个C模块。

0

使用numpy。循环被一些数组的差异所替代，其评估是在C中完成的。

0

你可以尝试将其重写为几个循环：

for ctr in xrange(N):
    list1[ctr] = in1[ctr] - in1[0] - ctr * c1

for ctr in xrange(N):
    list2[ctr] = in2[ctr] - in2[0] - ctr * c2

for ctr in xrange(N):
    list3[ctr] = c3 - in1[ctr]

for ctr in xrange(N):
    list4[ctr] = c4 - in2[ctr]

这听起来可能并不像傻瓜。测量一下吧。这种代码的一个问题可能是引用的局部性。如果你在内存中跳来跳去，就会逆向缓存。你可能会发现单独地快速遍历数组对缓存更友好。

你也可以考虑使用并行线程来执行它们。

创建四个范围比创建一个范围需要更多的时间，因此速度会变慢。使用四个线程可能会有所帮助。但我担心全局解释器锁会消耗大部分性能。 - Aaron Digulla
完全取决于数据，不是吗？ - Joe
1
由于GIL的存在，使用线程是没有意义的（在没有GIL的语言中也可能没有意义。400毫秒仍然可能太短，无法弥补创建线程的成本，但您需要进行分析才能确定）。正如@Joe所说，尝试一下，看看是否可行（创建xrange的成本几乎为零）。 - Jonathan Sternberg
将它们分成多个循环会使速度慢大约100毫秒。不过我还没有尝试过线程，我会告诉你它对速度的影响。 - bheklilr
并不完全是这样。所有操作都发生在内存中，没有线程执行任何阻塞IO操作，这意味着几乎没有并行执行。 - Aaron Digulla
0

使用列表推导式计算列表内容比使用for循环要快一些。

import random

N = 40000
c1 = 4
c2 = 9
c3 = 11
c4 = 8
in1 = [random.randint(1, 50000) for _ in xrange(N)]
in2 = [random.randint(1, 50000) for _ in xrange(N)]
list1 = [None for _ in xrange(N)]
list2 = [None for _ in xrange(N)]
list3 = [None for _ in xrange(N)]
list4 = [None for _ in xrange(N)]
in1_0 = in1[0]
in2_0 = in2[0]

def func():
    for ctr in xrange(N):
        list1[ctr] = in1[ctr] - in1_0 - ctr * c1
        list2[ctr] = in2[ctr] - in2_0 - ctr * c2
        list3[ctr] = c3 - in1[ctr]
        list4[ctr] = c4 - in2[ctr]

def func2():
    global list1, list2, list3, list4
    list1 = [(in1[ctr] - in1_0 - ctr * c1) for ctr in xrange(N)]
    list2 = [(in2[ctr] - in2_0 - ctr * c2) for ctr in xrange(N)]
    list3 = [(c3 - in1[ctr]) for ctr in xrange(N)]
    list4 = [(c4 - in2[ctr]) for ctr in xrange(N)]

然后是timeit的结果：

% python -mtimeit -s 'import flup' 'flup.func()'
10 loops, best of 3: 42 msec per loop
% python -mtimeit -s 'import flup' 'flup.func2()'
10 loops, best of 3: 34.1 msec per loop
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接