如何在Cython中最快地从现有数组和变量创建新数组

Question

假设我有一个数组

from array import array
myarr = array('l', [1, 2, 3])

还有一个变量：myvar = 4，创建一个新数组的最快方法是什么：

newarray = array('l', [1, 2, 3, 4])

您可以假设所有元素都是“长”类型的。

我尝试创建一个新数组并使用array.append()方法，但不确定这是否是最快的方法。我考虑使用memoryview，例如：malloc(4*sizeof(long))，但我不知道如何将一个较短的数组复制到内存视图的一部分，然后将最后一个元素插入到最后一个位置。

我对Cython相当陌生。感谢任何帮助！

更新：

Cython:[100000循环，3次取最佳值：每个循环5.94微秒]

from libc.stdlib cimport malloc

def cappend(long[:] arr, long var, size_t N):
    cdef long[:] result = <long[:(N+1)]>malloc((N+1)*sizeof(long))
    result.base[:N] = arr
    result.base[N] = var
    return result

数组: [1000000次循环，3次中的最佳表现: 每次1.21微秒]

from array import array
import copy
def pyappend(arr, x):
    result = copy.copy(arr)
    result.append(x)
    return result

列表追加： [1000000 次循环，3 次中的最佳结果：每次 480 纳秒]

def pylistappend(lst, x):
    result = lst[:]
    result.append(x)
    return result

有希望改进Cython部分并击败数组部分吗？

- Weiwen Gu

---

你是否真的在使用Cython - 就像这个东西 - 还是把它和其他东西混淆了？另外，为什么选择array.array数组？不清楚你为什么需要它们。 - user2357112

根据文档，可能只需要克隆和追加。 - user2357112

你可能想在变量上放置显式类型。 - user2357112

@user2357112 是的，我正在使用Cython。我使用array.array作为类型强制数组。我也可以使用np.array。问题是一样的。我不确定这是否是最快的纯C实现，没有Python类型检查的开销。另外，假设我将变量定义为“long”。 - Weiwen Gu

这是你不应该经常做的事情 - 它从来不会真正快速，因为它通常必须复制旧数组中的所有数据。list 是最快的选项的原因是它被设计为可调整大小，因此分配比所需空间更多的空间以便有足够的空间进行扩展。如果你想要快速的东西，那么你应该做同样的事情。 - DavidW

Answer 1

Cython比“普通”的Python更能够访问array.array的内部，因此我们可以利用它来加速代码：

1. 对于您的小示例，通过消除大部分开销，几乎可以提高7倍。
2. 通过消除不必要的数组复制，可以将较大输入的速度提高2倍。

继续阅读以获取更多详细信息。

---

“这样为小输入优化函数有点不寻常，但并非没有（至少在理论上）的意义。”

“因此，让我们以您的函数作为基准线开始：”

a=array('l', [1,2,3])
%timeit pyappend(a, 8)
1.03 µs ± 10.4 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

lst=[1,2,3]
%timeit pylistappend(lst, 8)
279 ns ± 6.03 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

我们必须意识到：我们所测量的不是复制成本，而是开销成本（Python 解释器、调用函数等），例如，无论 a 有 3 个元素还是 5 个元素都没有区别：

a=array('l', range(5))
%timeit pyappend(a, 8)
1.03 µs ± 6.76 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

在数组版本中，我们有更多的开销，因为我们通过copy模块进行间接引用，我们可以尝试消除这个问题：

def pyappend2(arr, x): 
      result = array('l',arr)                   
      result.append(x)                               
      return result

%timeit pyappend2(a, 8)
496 ns ± 5.04 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

那会更快。现在让我们使用Cython，这将消除解释器的成本：

 %%cython
 def cylistappend(lst, x):      
     result = lst[:]                                  
     result.append(x)                            
     return result

 %%cython
 from cpython cimport array
 def cyappend(array.array arr, long long int x):
      cdef array.array res = array.array('l', arr)
      res.append(x)
      return res   

 %timeit cylistappend(lst, 8)
 193 ns ± 12.4 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
 %%timeit cyappend(a, 8)
 421 ns ± 8.08 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Cython 版本对于 list 大约快了 33%，对于 array 快了大约 10%。构造函数 array.array() 需要一个可迭代对象，但是我们已经有了一个 array.array，所以我们使用来自 cpython 的功能来访问 array.array 对象的内部并稍微改进一下情况：

 %%cython
 from cpython cimport array
 def cyappend2(array.array arr, long long int x):
     cdef array.array res = array.copy(arr)
     res.append(x)
     return res

 %timeit cyappend2(a, 8)
 305 ns ± 7.25 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

下一步，我们需要了解如何使用array.array添加元素：通常情况下，它会过度分配，因此append()的摊销成本为O(1)，但是在array.copy之后，新数组恰好包含所需数量的元素，并且下一个append将调用重新分配。我们需要改变这一点（有关使用的函数的说明，请参见此处）：

  %%cython
  from cpython cimport array
  from libc.string cimport memcpy
  def cyappend3(array.array arr, long long int x):
           cdef Py_ssize_t n=len(arr)
           cdef array.array res = array.clone(arr,n+1,False)
           memcpy(res.data.as_voidptr, arr.data.as_voidptr, 8*n)#that is pretty sloppy..
           res.data.as_longlongs[n]=x
           return res

 %timeit cyappend3(a, 8)
 154 ns ± 1.34 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

与你的函数类似，内存是过度分配的，所以我们不再需要调用resize()。现在我们比list快，几乎比原始的Python版本快7倍。

---

让我们比较更大的数组大小的时间（a=array('l',range(1000))，lst=list(range(1000))，其中数据复制占据了大部分运行时间）:

  pyappend             1.84 µs  #copy-module is slow!
  pyappend2            1.02 µs
  cyappend             0.94 µs  #cython no big help - we are copying twice
  cyappend2            0.90 µs  #still copying twice
  cyappend3            0.43 µs  #copying only once -> twice as fast!

  pylistappend         4.09 µs # needs to increment refs of integers
  cylistappend         3.85 µs # the same as above

现在，消除array.array的不必要复制，可以得到我们期望的因子2。

---

对于更大的数组（10000个元素），我们看到如下内容：

  pyappend             6.9 µs  #copy-module is slow!
  pyappend2            4.8 µs
  cyappend2            4.4 µs  
  cyappend3            4.4 µs  

现在这两个版本已经没有区别（如果放弃较慢的复制模块）。原因是对于这么大数量的元素，“array.array”的行为已经改变：当进行复制时，会过度分配内存，从而避免第一次“append()”后的重新分配。

我们可以很容易地进行检查。

b=array('l', array('l', range(10**3)))#emulate our functions
b.buffer_info()
[] (94481422849232, 1000)
b.append(1)
b.buffer_info()
[] (94481422860352, 1001) # another pointer address -> reallocated
...
b=array('l', array('l', range(10**4)))
b.buffer_info()
[](94481426290064, 10000)
b.append(33)
b.buffer_info()
[](94481426290064, 10001) # the same pointer address -> no reallocation!

- ead

---

非常好的答案和详细的分析！非常感谢。 - Weiwen Gu