用Cython做list/dict的惯用方法？

Question

我的问题是：我发现用St++映射和向量处理粗C++的数据集通常比使用Cython更快（并且内存占用更少）。

我认为，这种速度损失的一部分是由于使用了Python列表和dict，而且在Cython中使用不那么麻烦的数据结构可能有一些技巧。例如，这个页面（http://wiki.cython.org/tutorials/numpy）展示了如何通过预先定义ND数组的大小和类型，使numpy数组在Cython中运行得非常快。

问：有没有什么方法可以对列表/听写进行类似的处理，例如，大致说明您希望在列表/听写中包含多少个元素或（键、值）对？也就是说，在Cython中，有没有一种惯用的方法将列表/听写转换为（快速）数据结构？

如果不是，我想我只需要用C++编写，然后用Cython导入包装。

Answer 1

在Python中，类似C++的操作通常会比较慢。{{CD1}}和^ {< CD2}}实际上实现得很好，但是使用Python对象获得了很多开销，这些对象比C++对象更抽象，并且在运行时需要更多的查找。

顺便说一下，std::vector的实现方式与list非常相似。std::map实际上是以一种方式实现的，当它的大小变大时，许多操作都比dict慢。对于每一个合适的大型示例，dict克服了它比std::map慢的常数因子，并且实际上将更快地执行查找、插入等操作。

如果你想使用std::map和std::vector，没有什么能阻止你。如果要将它们公开给Python，就必须自己包装它们。如果这种包装消耗了你希望节省的全部或大部分时间，不要感到震惊。我不知道有什么工具能帮你自动完成。

有一些C API调用来控制对象的创建和一些细节。您可以说“创建一个至少包含这么多元素的列表”，但这并不能提高列表创建和填充操作的总体复杂性。当你试图改变你的列表时，它当然不会改变太多。

我的建议是

• 如果你想要一个固定大小的数组（你说的是指定一个列表的大小），你可能实际上需要一个类似numpy数组的东西。

• 我怀疑在代码中使用std::vector代替list进行替换会得到任何想要的加速。如果你想在幕后使用它，它可能会给你一个令人满意的尺寸和空间改善（我当然不知道没有测量，你也不知道）。;) ).

• dict实际上做得很好。我绝对不会尝试在Python中引入一个基于std::map的新的通用类型，它在许多重要操作的时间上具有更糟糕的算法复杂性，并且至少在一些实现中为用户留下了dict已经有的一些优化。

  如果我真的想要一个更像std::map的东西，我可能会使用一个数据库。如果我想储存在dict中的东西（或者说，我储存在list中的东西）变得太大，以至于我无法在记忆中感到舒适，我通常会这样做。Python在stdlib中有sqlite3和所有其他主要数据库的驱动程序。

Answer 2

C++不仅是因为向量和元素的静态声明，而且是因为使用模板/泛型，向量指定只有EEM>包含某个类型的元素，例如具有三个元素的元组的向量。Cython做不到最后一件事，而且听起来很重要——它必须在编译时强制执行，不知怎么的（运行时的类型检查是Python已经做的）。所以现在，当你在Cython中从列表中弹出某个内容时，无法预先知道它是什么类型，而将它放入类型变量中只会添加一个typecheck，而不是speed。这意味着在这方面无法绕过Python解释器，在我看来，这是Cython在非数值任务中最关键的缺点。

解决这个问题的手动方法是用一个cdef类将python list/dict（或者std：：vector）与一个特定类型的元素或键值组合进行子类化。这相当于模板生成的代码。只要在Cython代码中使用生成的类，它就应该提供改进。

使用数据库或数组只是解决了一个不同的问题，因为这涉及到将任意对象（但具有特定类型，最好是cdef类）放入容器中。

而且std：：map不应该与dict进行比较；std：：map按排序顺序维护键，因为它是一个平衡树，dict解决了另一个问题。更好的比较是dict和Google的hashtable。

Answer 3

Cython现在支持模板，并且附带了一些STL容器的声明。

见http://docs.cython.org/src/userguide/wrapping_CPlusPlus.html#standard-library

他们举了一个例子：

from libcpp.vector cimport vector

cdef vector[int] vect
cdef int i
for i in range(10):
    vect.push_back(i)
for i in range(10):
    print vect[i]