python - Cython 从现有数组和变量创建新数组的最快方法是什么

Question

假设我有一个数组

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

和一个变量:我的变量 = 4创建新数组的最快方法是什么:

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

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

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

我是 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部分，打败array one吗？

Answer 1

与“普通”python 相比，Cython 使我们能够更多地访问 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 是如何追加元素的:通常，it over-allocates ，因此 append() 的摊销成本为 O(1)，但是在 array.copy 之后，新数组正好是所需数量的元素，并且下一个 append 调用重新分配。我们需要更改它(有关所用函数的说明，请参阅 here):

  %%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!