随着时间的推移,我做了很多需要我使用list
的.append()
函数以及 numpy 数组numpy.append()
函数的事情。我注意到当数组的大小很大时,两者都增长得非常慢。
我需要一个动态增长的数组,其大小约为 100 万个元素。我可以自己实现这一点,就像std::vector
在C++中一样,通过添加无法从外部访问的缓冲区长度(保留长度)。但是我必须重新发明轮子吗?我想它应该在某个地方实现。所以我的问题是:Python中已经存在这样的事情吗?
我的意思是:Python 中是否有一种数组类型能够在大多数时间随着O(C)
的时间复杂度而动态增长?
numpy 数组的内存在其文档中有很好的描述,并且在这里讨论了很多。 列表内存布局也被讨论过,尽管通常只是与numpy形成对比。
numpy 数组具有固定大小的数据缓冲区。 "增长"它需要创建一个新数组,并将数据复制到其中。np.concatenate
编译的代码中执行此操作。np.append
以及所有stack
功能都使用concatenate
。
据我了解,列表有一个连续的数据缓冲区,其中包含指向模因中其他对象的指针。 Python 在该缓冲区中保留了一些可用空间,因此使用list.append
进行添加相对快速和容易。 但是当可用空间填满时,它必须创建一个新的缓冲区并复制指针。 我可以看到大型列表可能会变得昂贵。
因此,列表将存储每个元素的指针,以及内存中其他地方的元素本身(例如浮点数)。 相比之下,浮点数组将浮点数本身存储为其缓冲区中的连续字节。 (对象 dtype 数组更像是列表)。
迭代创建数组的推荐方法是使用append
构建列表,并在最后创建一次数组。 重复np.append
或np.concatenate
相对昂贵。
提到了deque
。 我对它如何存储数据知之甚少。 文档说它可以在开头添加元素,就像在结尾一样容易,但随机访问比列表慢。 这意味着它将数据存储在某种链表中,因此查找nth
元素需要遍历它前面的n-1
链接。 因此,在增长便利性和访问速度之间需要权衡。
将元素添加到列表的开头需要创建一个新的指针列表,新的指针位于开头。 因此,从常规列表的开头添加和删除元素比在末尾添加和删除元素要昂贵得多。
推荐软件超出了核心 SO 目的。 其他人可能会提出建议,但如果它被关闭,请不要感到惊讶。
有一些文件格式,如HDF5
,是为大型数据集设计的。 它们通过"分块"等功能适应增长。 并且有各种各样的数据库包。
两者都使用底层数组。相反,您可以使用collections.deque
专门用于在具有 O(1) 复杂度的两端添加和删除元素