data-structures - 无缓存数据结构和动态语言——有效吗？

Question

我最近一直在阅读有关缓存无视数据结构(如辅助缓冲区堆)的内容。这些数据结构通过将最近访问的元素保存在高速缓存中来工作，因此任何后续访问也更快。

这些数据结构中的大多数都是使用 C/C++ 等低级语言实现的。尝试将这些数据结构移植到像 Python 这样的动态语言是否值得，或者在虚拟机上运行的开销是否会破坏这些数据结构的所有性能优势？似乎是后者，但我想我会问问是否有人真的有这方面的经验。

Answer 1

在 C(或 C++)中，您可以对每个数据结构的确切大小进行细粒度控制。您还可以对存储分配进行细粒度控制。毕竟，您可以扩展 new 方法，直接使用 malloc 或构造内存以创建空间局部性。

在大多数动态语言(如 Python)中，您根本无法控制任何东西的确切大小，更不用说它的位置了。

在 Python 中，你可能有一些时间局部性，但你几乎没有或没有空间局部性。

可以通过简单的结果内存来增强时间局部性。这是一种非常常见的加速，以至于人们通常会包含一个内存装饰器，以将内存(时间局部性)与核心算法分开。

我不认为 C 或 C++ 无缓存实现可以转化为动态语言，因为我认为您没有足够的控制权。相反，只需利用记忆化来加速。

http://wiki.python.org/moin/PythonDecoratorLibrary#Memoize