O(1)随机访问的神话

在这一系列文章中,Emil Ernerfeldt认为,对于大型数据结构,不存在O(1)随机访问之类的问题。 处理器缓存的影响导致大约O(√N)的性能。

RAM的神话,第一部分
如果您学习过计算机科学,那么您就会知道如何进行复杂度分析。 您会知道,通过…进行迭代… www.ilikebigbits.com

在下一篇文章中,Emil提供了关于为什么我们看到O(√N)的理论论证。 他用一个图书馆的例子来说明他的观点:

通常,适合图书馆的书籍数量N与图书馆半径r的平方成正比,我们写成N∝r² 。 由于取书的时间Tr成正比,我们可以写成N∝T²T∝√NT = O(√N)

RAM的神话,第二部分
在上一篇文章中,我测量了随机内存访问,发现它们大致遵循O(√N)。 但为什么? 显然…… www.ilikebigbits.com

在下一篇文章中,Emil得出结论,内存访问应该是可预测的,这有助于处理器在程序访问内存之前将内存预取到缓存中。 通过这种推理,应避免随机访问,因为这会导致较差的缓存性能。

RAM的神话,第三部分
在第一部分中,我测量了随机存储器访问的开销,发现它大约为O(√N)。 在第二部分中,我… www.ilikebigbits.com

在本文中,Emil阐明了一些概念。 他还添加了用于基准测试的代码的链接。

RAM的神话,第四部分
欢迎来到RAM神话的另一期! 在第一部分点击reddit之后,它引发了很多评论。 是… www.ilikebigbits.com