增加列表理解中多个 for 循环的时间

Question

我正在寻找一种方法来缩短 Python 3.5 在列表理解中执行两个 for 循环所需的执行时间，如下所示：

[[(k1-k2)**power for k2 in range(m,n)] for k1 in range(m,n)]

Answer 1

所以，我开始使用您当前的方法，发现虽然它确实有效，但速度很慢。我的第一次尝试涉及简单地 t运行s 将您的列表理解转化为带有 numpy 数组的 suitable 方法。这比你原来的方法快了大约三倍，但就在那时我注意到了一些非常漂亮的东西：这是一个对称的 Toeplitz matrix。来自该维基页面：

In linear algebra, a Toeplitz matrix or diagonal-constant matrix, named after Otto Toeplitz, is a matrix in which each descending diagonal from left to right is constant.

我首先使用了 Toeplitz 矩阵的默认 scipy 实现，但这种方法对于您的问题来说是不必要的缓慢。于是自己写了一个类似的做法，也就是下面的第三次尝试。

方法论

I 运行每种方法进行 10 次测试，每个单独的测试包含 1000 次运行。我将参数设置为m = 10, n = 100。结果可以在下面的 table 中找到：

    Your approach       Numpy #1     Numpy #2     Numpy #3
1        4.573965       1.432406     1.060242     0.186767
2        4.341466       1.432237     1.060404     0.186872
3        4.442438       1.434460     1.144850     0.183120
4        4.318919       1.456928     1.072072     0.185626
5        4.249392       1.450684     1.072217     0.183273
6        4.202730       1.508863     1.070299     0.183019
7        4.224226       1.457543     1.065354     0.183591
8        4.234505       1.432971     1.082438     0.185711
9        4.256538       1.431828     1.080051     0.184290
10       4.241055       1.557204     1.083070     0.185845

AVG      4.308523       1.459512     1.079100     0.184811
STD      0.117433       0.041693     0.024538     0.001521

scipy Toeplitz 方法（table 中的 Numpy #2）几乎比您当前的方法快四倍，但所有这些结果与第三种也是最后一种方法相比相形见绌：比您最初的实施速度快了 23 倍！

现在，既然你对时间复杂度感兴趣，我让 n 变化，保持 m = 10。每种方法的结果可以在下图中找到：

显然，第三种方法是正确的选择！

代码

完整代码：

import timeit
import numpy as np
from scipy.linalg import toeplitz


def your_approach(m, n):
    print("\n\tlist comprehension")
    k = range(m, n)
    for i in range(1, 11):
        start = timeit.default_timer()
        for j in range(1, 1001):
            data_list_comp = [[(k1 - k2) ** 2 for k2 in k] for k1 in k]
        print("\t{}".format(timeit.default_timer() - start))
    return data_list_comp


def numpy1(m, n):
    print("\n\tnumpy")
    k_n = np.array(range(m, n))
    for i in range(1, 11):
        start = timeit.default_timer()
        for j in range(1, 1001):
            data_numpy = [list((k_n - x) ** 2) for x in k_n]
        print("\t{}".format(timeit.default_timer() - start))
    return data_numpy


def numpy2(m, n):
    print("\n\ttoeplitz")
    k_n = np.array(range(0, n - m)) ** 2
    toep = toeplitz(k_n)
    for i in range(1, 11):
        start = timeit.default_timer()
        for j in range(1, 1001):
            data_numpy = [list(toep[:, i]) for i in range(n - m)]
        print("\t{}".format(timeit.default_timer() - start))
    return data_numpy

def numpy3(m, n):
    print("\n\ttoeplitz2")
    k_n = list(np.array(range(0, n - m)) ** 2)  # can obviously be done without numpy, but I was a bit lazy. :)
    for i in range(1, 11):
        start = timeit.default_timer()
        for j in range(1, 1001):
            data_numpy = [(k_n[i::-1] + k_n[1:-i]) if i != 0 else k_n for i in range(0, n - m)]
        print("\t{}".format(timeit.default_timer() - start))
    return data_numpy

m = 10

for n in [25, 50, 100, 150, 200]:
    assert your_approach(m, n) == numpy1(m, n) == numpy2(m, n) == numpy3(m, n)

增加列表理解中多个 for 循环的时间

Boosting time for multiple for loops in list comprehensions

python

performance

multithreading

list-comprehension

time-complexity

方法论

代码