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

Question

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

不幸的是，我需要一个数据结构来存储元素。当元素的数量非常多时，但对于我的算法而言并非不合理的高，std::vector 和 std::valarray 都不会在恒定时间内访问任意元素 as you can see in this graph .

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

Answer 1

对于较高的 n 值，很可能是:

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

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

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

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