1 c++ stdvector valarray constant-time
我正在研究一种算法的实现,我想表明它可以在恒定时间内工作,即使有很多元素也是如此.
不幸的是,我需要一个存储元素的数据结构.当元素的数量非常高,但对我的算法而言并非不合理时,std :: vector和std :: valarray都不会在常量时间访问任意元素,如此图所示.
是否有更好的数据结构来存储值？是否有任何技术可以实现以实现恒定时间访问？
对于高值,n它很可能是:
你正在遇到一个缓存问题.在某些时候,每次内存访问都会丢失缓存,从而导致更长的内存负载.
您正在使用内存分页来解决缓存问题.现代计算机存储器以树状结构组织.每个存储器存取经过那棵树,使每一个内存访问O(log n),其中n是可寻址内存空间.你通常不会注意到它,因为树的高度和良好的缓存.但是,对于非常高n且随机的存储器访问,这可能成为问题.
例如,我的一位朋友证明,O(n log n)由于随机存储器访问,计数排序算法具有时间复杂性.快速排序算法 - 用于比较 - 具有非常好的顺序访问内存,并且分页开销要低得多.
最重要的是,您最有可能达到架构/操作系统内存访问开销 - 除非您使用某种非常极端的方法(例如实现您自己的操作系统),否则您将无法克服这些问题.
