使用Cython构建未知长度的1维数组/列表/向量的最高效方法？或者这根本不应该这样做？

Question

我有一个对时间要求很高的模型，是用Cython写的。我的Cython扩展的主要功能里有一个循环，根据Cython的性能分析工具（它用黄色阴影显示Python调用的次数），唯一“黄色”的部分就是我在往一个Python列表里添加数据的地方。（因为我是在Python脚本中调用这个Cython函数，所以必须输出一个Python对象。）这是我函数的基本思路（其他部分都不是重点，我已经测试过这个函数的每一部分，添加操作是瓶颈）：

from libc.math cimport log
def main(some args):
    cdef (some vars)

    cdef list OutputList = []

    # NB: all vars have declared types
    for x in range(t):
        (do some Cythonic stuff, some of which uses my cimport-ed log)
        if condition is True:
            OutputList.append(x) # this is the only 'yellow' line in my main loop.
    return OutputList # return Python object to Python script that calls main()

不幸的是，我不知道我的输出数组/列表/向量（不管我最后用什么）有多长。不过，我可以把它设置为52560，这也是我在其他Python代码中调整到的长度。我希望在不设置输出数组长度的情况下获得显著的速度提升，但如果这影响了我的性能，我也愿意放弃这个想法。

我还尝试过在Cython中使用C++来利用C++的数据结构（比如向量、队列等），但这样做就不能方便地导入纯C的log函数。我在Cython的文档/维基上看到可以写一个“适配器”模块来在C++ Cython中使用纯C函数，但我不知道该怎么做，也找不到相关的信息。

总之，我欢迎所有符合我问题的建议：

在Cython中，构建一个未知大小的列表/数组/向量的最佳方法是什么？或者有没有什么明显的替代方案（比如使用已知长度的可迭代对象），能解决我这个未知长度的问题？

更新

C++容器确实在项目赋值方面显示出了速度提升，而项目赋值又比往列表和numpy数组中添加数据要快。最佳的方法是使用C++容器，同时能够导入纯C函数……这样就可以避免因为需要查找libc.math以获取快速的log函数而导致的性能下降。

Answer 1

你可以先计算一下有多少个元素符合你的条件，然后再为这些元素分配一个足够大的numpy数组。

# pseudo code
def main(): 
   count = 0
   for i in range(t):
       if criteria: 
            count += 1

   cdef numpy.ndarray[count] result

   int idx =0
   for i in range(t):
      if criteria:
          idx += 1
          result[idx] = value

Answer 2

build1darray.pyx:

• 指定了索引变量的类型
• 关闭了安全检查
• 可以使用多个CPU（这在处理大数据时很有用）

#cython: boundscheck=False, wraparound=False
from libc.math cimport log

from cython.parallel cimport prange

import numpy as pynp
cimport numpy as np

# copy declarations from libcpp.vector to allow nogil
cdef extern from "<vector>" namespace "std":
    cdef cppclass vector[T]:
        void push_back(T&) nogil
        size_t size()
        T& operator[](size_t)

def makearray(int t):
    cdef vector[np.float_t] v
    cdef int i
    with nogil: 
        for i in range(t):
            if i % 10 == 0:
                v.push_back(log(i+1))

    cdef np.ndarray[np.float_t] a = pynp.empty(v.size(), dtype=pynp.float)
    for i in prange(a.shape[0], nogil=True):
        a[i] = v[i]
    return a

第二部分的代码大约只占第一部分循环的1%，所以在这种情况下优化速度没有意义。

在我的系统上，<math.h>里有extern "C" { ... }，所以libc.math.log可以正常工作。

可以使用PyArray_SimpleNewFromData()来避免复制数据，但这样需要自己管理数组的内存。

Answer 3

在CPython中，给Python列表添加元素的操作已经做得很优化了。Python并不是为每个元素单独分配内存，而是逐步增加指向列表中对象的指针数组。所以，单纯切换到Cython并不会给你带来太大的帮助。

你可以在Cython中使用C++的容器，方法如下：

from libc.math cimport log
from libcpp.list cimport list as cpplist

def main(int t):

    cdef cpplist[int] temp

    for x in range(t):
        if x> 0:
            temp.push_back(x)

    cdef int N = temp.size()
    cdef list OutputList = N*[0]

    for i in range(N):
        OutputList[i] = temp.front()
        temp.pop_front()

    return OutputList  

你需要测试一下这样做是否能加快速度，但可能效果不会太明显。

另一种方法是使用numpy数组。在这方面，Cython在优化代码上表现得很好。所以如果你能接受用numpy数组作为主函数的返回值，你可以考虑这样做，并用一些Cython代码来替代构建和填充OutputList的过程，直接分配和填充一个numpy数组。

想了解更多信息，可以查看这个链接：http://docs.cython.org/src/tutorial/numpy.html

如果需要帮助，请随时问我。

更新：如果你在两个循环中避免方法查找，代码应该会稍微快一些：

from libc.math cimport log
from libcpp.list cimport list as cpplist

def main(int t):

    cdef cpplist[int] temp

    push_back = temp.push_back
    for x in range(t):
        if x> 0:
            push_back(x)

    cdef int N = temp.size()
    cdef list OutputList = N*[0]

    front = temp.front()
    pop_front = temp.pop_front()
    for i in range(N):
        OutputList[i] = front()
        pop_front()

    return OutputList