我正在读一篇article关于缓存不经意数据结构的好处,我发现自己想知道 Python 实现 (CPython) 是否使用这种方法?如果没有,是否存在技术限制?
最佳答案
我想说这与内置(标准库)Python 数据结构几乎无关。
在 Python 中创建新的数据类型意味着创建一个类,它不是底层基元类型或方法指针的基本包装器,而是一种特定类型的结构,它具有来自以下位置的许多附加元数据: Python 对象数据模型。
Python 中没有原生树数据结构。有列表、数组和基于数组的哈希表(dict、set),以及这些的一些扩展,例如在
collections
模块中。第三方树/trie/等,如果适合预期用途,实现可以免费提供缓存无关的实现。这将包括 CPython C 级实现,例如使用自定义扩展模块或通过 Cython 等工具。NumPy
ndarray
是一种连续数组数据结构,用户可以为其选择数据类型(即理论上,用户可以选择一种奇怪的数据类型,该数据类型不容易制成机器架构缓存大小的倍数)。对于固定数据类型,也许可以改进一些定制(对于 array.array 来说也是如此),但我想知道有多少数组/线性代数算法受益于某种定制的缓存遗忘性——通常,这些类型的库被编写为假设使用特定的数据类型,例如 int32 或 float64,特别是基于缓存大小,并采用动态内存重新分配(例如加倍)来分摊某些操作的成本。例如,您的链接文章提到,查找数组上的最大值是“本质上”缓存不经意的......因为它是连续的,您可以最大限度地利用您读取的每个缓存行,并且您只读取最少数量的缓存行。也许为了将数组视为堆或其他东西,您可以聪明地重新安排内存布局以达到最佳状态,而不管缓存大小如何,但是通用数组的作用不是像基于一个非常特殊的用例(具有堆属性的数组)。
简而言之,我会把问题转向你,并说,考虑到 Python 中的标准数据结构,你是否看到动态调整大小、动态类型和(也许是最重要的)通用随机访问模式之间的特定权衡假设与有缓存不经意的实现支持它们?
关于python - Python 实现是否使用缓存不经意的数据结构?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48752374/