c++ - 对列表中任意元素的恒定时间访问 (C++)

Question

我目前正在研究一种算法的实现，我想证明它可以在恒定时间内工作，即使有非常多的元素。

不幸的是，我需要一个数据结构来存储元素。当元素的数量非常多，但对于我的算法来说不是不合理的高时，std::vector 和 std::valarray 都不会在恒定时间内访问任意元素，如您在此图中看到的那样。

是否有更好的数据结构来存储值？我可以实施任何技术来实现恒定时间访问吗？

Answer 1

对于高值，n很可能是：

您遇到了缓存问题。在某些时候，每次内存访问都会错过缓存，从而导致更长的内存负载。

您遇到内存分页的缓存问题。现代计算机内存以树状结构组织。每个内存访问都通过该树，使每个内存访问都O(log n)在n可寻址的内存空间中。您通常不会注意到它，因为该树的高密度和良好的缓存。然而，对于非常高n和随机的内存访问，这可能会成为一个问题。

例如，我的一个朋友证明了计数排序算法O(n log n)由于随机内存访问而具有时间复杂度。快速排序算法 - 用于比较 - 对内存的顺序访问非常好，并且分页开销要低得多。

底线是，您很可能会遇到架构/操作系统内存访问开销——除非您使用一些非常极端的方法（例如实现自己的操作系统），否则您将无法克服这些开销。