在Cython中遍历数组，列表比np.array更快吗？

Question

简而言之：在Cython中，为什么（或何时）迭代NumPy数组比迭代Python列表更快？

一般来说：

我以前用过Cython，并能够大大加速原始的Python实现，但是弄清楚需要做什么似乎并不容易。

考虑以下三个sum()函数的实现。它们存储在名为'cy'的Cython文件中（显然，有np.sum()，但这与我的观点无关...）

原始Python代码：

def sum_naive(A):
   s = 0
   for a in A:
       s += a
   return s

使用预期输入为Python列表的Cython函数：

def sum_list(A):
    cdef unsigned long s = 0
    for a in A:
        s += a
    return s

Cython与一个期望numpy数组的函数。

def sum_np(np.ndarray[np.int64_t, ndim=1] A):
    cdef unsigned long s = 0
    for a in A:
        s += a
    return s

就运行时间而言，我预期 sum_np < sum_list < sum_naive，然而，以下脚本却证明了相反的情况（为了完整性，我添加了 np.sum()）。

(Note: This is the translated text with the same HTML tags and formatting preserved.)

N = 1000000
v_np = np.array(range(N))
v_list = range(N)

%timeit cy.sum_naive(v_list)
%timeit cy.sum_naive(v_np)
%timeit cy.sum_list(v_list)
%timeit cy.sum_np(v_np)
%timeit v_np.sum()

结果为：

In [18]: %timeit cyMatching.sum_naive(v_list)
100 loops, best of 3: 18.7 ms per loop

In [19]: %timeit cyMatching.sum_naive(v_np)
1 loops, best of 3: 389 ms per loop

In [20]: %timeit cyMatching.sum_list(v_list)
10 loops, best of 3: 82.9 ms per loop

In [21]: %timeit cyMatching.sum_np(v_np)
1 loops, best of 3: 1.14 s per loop

In [22]: %timeit v_np.sum()
1000 loops, best of 3: 659 us per loop

发生了什么事？为什么Cython + NumPy很慢？

P.S.
我确实使用了
＃cython：boundscheck=False
＃cython：wraparound=False

- Tomer Levinboim

---

我不知道Cython是否可以加速针对数组的“for a in A”类型循环，也许为a定义一个类型会起到奇效。但我认为加速的正确（或者至少更常见）方法是像这样：'cdef int j; for j in range(len(A)): s += A[j]'。 - Jaime

Answer 1

在Cython中有一种更好的实现方式，至少在我的机器上能击败np.sum，因为它避免了类型检查和其他numpy通常在处理任意数组时需要执行的操作：

#cython.wraparound=False
#cython.boundscheck=False
cimport numpy as np

def sum_np(np.ndarray[np.int64_t, ndim=1] A):
    cdef unsigned long s = 0
    for a in A:
        s += a
    return s

def sum_np2(np.int64_t[::1] A):
    cdef:
        unsigned long s = 0
        size_t k

    for k in range(A.shape[0]):
        s += A[k]

    return s

接下来需要考虑的是时间：

N = 1000000
v_np = np.array(range(N))
v_list = range(N)

---

%timeit sum(v_list)
%timeit sum_naive(v_list)
%timeit np.sum(v_np)
%timeit sum_np(v_np)
%timeit sum_np2(v_np)
10 loops, best of 3: 19.5 ms per loop
10 loops, best of 3: 64.9 ms per loop
1000 loops, best of 3: 1.62 ms per loop
1 loops, best of 3: 1.7 s per loop
1000 loops, best of 3: 1.42 ms per loop

您不希望通过Python样式遍历numpy数组，而是使用索引访问元素，因为这可以被转换为纯C，而不是依赖于Python API。

- JoshAdel

---

对于一维数组，使用[::1]是否比使用[:]有任何实际好处？ - Veedrac

我撤回了之前的评论。我不确定为什么会有这样的改进，但它是无法再现的。现在我得到了大约650微秒而不是621微秒。谢谢Josh！（并且+1给size_t） - Tomer Levinboim

"[::1]" 表示该内存沿该维度是连续的，并且在我的机器上对这个例子似乎确实有一点差异。 - JoshAdel

这虽然降低了该方法的灵活性，因为您不能再像 sum_np2(v_np[::3]) 这样传递 strided slice 给它，否则会出现错误，指出数组在内存中不是连续块。 - JoshAdel

Answer 2

a是无类型的，因此需要将Python类型和C类型进行大量转换。这可能会很慢。JoshAdel正确指出，您应该迭代一个范围，而不是一个列表。 Cython将把索引转换为C，这是快速的。使用cython -a myfile.pyx将为您突出显示这些内容; 您希望所有循环逻辑都是白色的，以获得最大的速度。注意，np.ndarray [np.int64_t，ndim = 1] 已过时，并已弃用，取而代之的是更快，更通用的long [:] 。

- Veedrac