RAM如何以O(1)的速度访问内存中的任何位置

我们被教导RAM内存的抽象是一个很长的字节数组.而对于CPU来说,访问它的任何部分需要相同的时间.什么是能够同时访问4千兆字节(在我的计算机上)的任何字节的设备？因为这对我来说似乎不是一项微不足道的任务.

我曾经问同事和我的教授,但是没有人能够指出如何通过简单的逻辑门实现这项任务,如果它不仅仅是一个棘手的逻辑门组合,那又是什么呢？

我个人的猜测是你可以以O(log(n))速度访问任何内存,其中n将是内存的大小.因为每个门都将内存分成两部分,然后向你发送内存访问指令,将内存分成两个门.但这需要很多门.我无法提出任何其他有根据的猜测,我甚至不知道我应该在Google中查找的设备名称.

请帮助我痛苦的好奇心,并提前感谢.

编辑<这是我学到的!

从你的引用"RAM可以将单元格地址X的值发送到某些输出引脚",这里是每个人都跳过(再次)对我来说不重要的事情.我看到它的方式,为了构建一个由64个引脚决定从2 ^ 64中取出哪个字节的门,每个引脚需要将整个可能的存储器范围分成两个.如果索引0处的位是0 - >则地址在存储器0-2 ^ 64/2处,否则地址在存储器2 ^ 64/2-2 ^ 64处.等等,然而,内存提取将通过的门(让我们称之为)将是64,(一个常数).然而,所需的门数量是N,其中N是存在的存储器字节数.

仅仅因为有64个引脚,这并不意味着您仍然可以将其解码为2 ^ 64范围内的单次提取.内存控制中有4 GB的内存和4 GB的内存吗？

现在这可以改进,因为当我越来越多地阅读这个内存是如何构建时,如果你将内存放入一个带有sqrt(N)行和sqrt(N)列的矩阵中,那么获取内存的门数量就会增加将需要经历的是O(log(sqrt(N)*2)并且所需的门数将是2*sqrt(N),这要好得多,我认为这可能是商业秘密.

/编辑<

Nemo.. 7

到底是什么,我不妨回答这个问题.

是的,在物理世界中,内存访问不能是恒定的时间.

但它甚至不能成为对数时间.您想到的O(log n)电路最终涉及某种二进制(或其他)树,并且您无法在3D Universe中创建具有恒定长度线的二叉树.

无论您的技术的"每单位体积比特"容量是多少,存储n位需要一个半径为O(n ^(1/3))的球体.由于信息只能以光速传播,因此访问球体另一端的位需要时间O(n ^(1/3)).

但即使这是错误的.如果你想谈谈我们宇宙的实际局限性,我们的物理学朋友们说,你可以在任何球体中存储的绝对最大位数与球体的表面积成正比,而不是它的体积.因此,包含n位信息的最小球体的实际半径是O(sqrt(n)).

正如我在评论中提到的,所有这些都是没有实际意义的.我们通常用于分析算法的计算模型假设恒定访问时间RAM,它与实际中的事实足够接近,并允许对竞争算法进行公平比较.(虽然从事高性能代码工作的优秀工程师非常关心局部性和内存层次......)