以太坊联合创始人维塔利克-布特林（Vitalik Buterin）发表了一篇题为 "内存访问是 O(N^(1/3)) "的新文章，对计算机科学中长期存在的关于如何测量内存访问的假设提出了挑战。传统上，内存操作在算法复杂度上被视为恒定时间或 O(1)。布特林认为这种模式存在缺陷，理论和实践都表明内存访问应被视为 O(N^(1/3))，即访问时间随内存大小的立方根而增加。
本文翻译自原文。点击此处阅读由我们的通讯员撰写的原文.
布特林认为，理解这一点可以改变开发人员的算法设计和性能优化方法，尤其是在密码学等领域，因为内存访问速度在这些领域起着至关重要的作用。
O(N^(1/3))模型的理论和经验基础
Buterin在分析中解释说，这种限制源于物理限制，尤其是光速和内存的空间分布。他使用了一个简单的模型：距离处理器的物理距离增加一倍，内存容量就会增加 8 倍，但访问内存所需的时间也会增加一倍。这种关系支持立方根缩放。
他将这一推理延伸到并行访问，即使可以同时访问多个内存单元，物理和能源限制仍然适用。在现实世界的计算中，从 CPU 寄存器到高速缓存和 RAM 等不同内存层所表现出的延迟模式都与这种立方根关系密切相关。
经验数据进一步支持了这一理论。在比较典型系统中不同类型内存的访问时间时，延迟时间的增长与内存大小的立方根近似，从而验证了布特林提出的模型。
对算法设计和优化的影响
布特林强调，这种视角的转变对于优化依赖于预计算的算法至关重要。在椭圆曲线运算或二进制域运算等加密程序中，开发人员通常会存储预计算表，以加快计算速度。在旧的 O(1) 模型下，扩展这些表似乎总是有益的。
然而，如果内存访问速度为 O(N^(1/3))，就会出现这样的情况：由于访问速度较慢，较大的表会适得其反。在 Buterin 的一次实验中，存储在高速缓存中的 8 位预计算表的性能优于存储在 RAM 中的 16 位大表，这说明在很多情况下，更快的访问速度比更大的存储空间更重要。
这对ASIC和GPU的设计有进一步的影响，在这些设计中，本地内存访问可以优化为恒定时间，但全局访问仍然受到物理原理的限制。
对加密行业的影响
Buterin 的发现可能会对区块链和加密工程产生重大影响。从散列函数到 zk-SNARK 和签名方案，许多加密算法都依赖于内存密集型操作。通过重新思考内存复杂性，开发人员可以实现更高效的加密协议、更快的区块链验证和优化的硬件实现。
随着行业朝着高性能计算和模块化区块链架构的方向发展，Buterin 的模型为创新提供了一个新的视角--在下一代加密基础设施中强调局部性、内存效率和现实的性能建模。
-
中国
-
中国台湾
-
丹麦
-
乌克兰
-
乌兹别克斯坦
-
乌干达
-
乌拉圭
-
也门
-
亚美尼亚
-
以色列
-
伊拉克
-
伊朗伊斯兰共和国
-
保加利亚
-
克罗地亚
-
刚果
-
刚果（金）
-
利比亚
-
加拿大
-
加纳
-
匈牙利
-
北马其顿
-
南非
-
博茨瓦纳
-
卡塔尔
-
卢旺达
-
卢森堡
-
印度
-
印度尼西亚
-
厄瓜多尔
-
叙利亚
-
古巴
-
吉尔吉斯斯坦
-
哈萨克斯坦
-
哥伦比亚
-
哥斯达黎加
-
喀麦隆
-
土耳其
-
坦桑尼亚
-
埃及
-
埃塞俄比亚
-
塔吉克斯坦
-
塞尔维亚
-
塞浦路斯
-
墨西哥
-
多米尼加共和国
-
奥地利
-
委内瑞拉
-
孟加拉国
-
安哥拉
-
尼日利亚
-
尼泊尔
-
巴勒斯坦
-
巴哈马
-
巴基斯坦
-
巴布亚新几内亚
-
巴拉圭
-
巴拿马
-
巴林
-
巴西
-
希腊
-
德国
-
意大利
-
拉脱维亚
-
挪威
-
捷克
-
摩尔多瓦
-
摩洛哥
-
文莱达鲁萨兰国
-
斯威士兰
-
斯洛伐克
-
斯洛文尼亚
-
斯里兰卡
-
新加坡
-
新西兰
-
日本
-
智利
-
柬埔寨
-
格鲁吉亚
-
比利时
-
毛里求斯
-
沙特阿拉伯
-
法国
-
波兰
-
波多黎各
-
泰国
-
津巴布韦
-
海地
-
澳大利亚
-
爱尔兰
-
爱沙尼亚
-
牙买加
-
特立尼达和多巴哥
-
玻利维亚
-
瑞典
-
瑞士
-
留尼汪
-
白俄罗斯
-
科威特
-
科特迪瓦
-
秘鲁
-
突尼斯
-
立陶宛
-
索马里
-
约旦
-
纳米比亚
-
缅甸
-
罗马尼亚
-
美国
-
老挝
-
联合王国
-
肯尼亚
-
芬兰
-
荷兰
-
莫桑比克
-
莱索托
-
菲律宾
-
萨尔瓦多
-
葡萄牙
-
蒙古
-
西班牙
-
赞比亚
-
越南
-
阿塞拜疆
-
阿富汗
-
阿尔及利亚
-
阿尔巴尼亚
-
阿曼
-
阿根廷
-
阿联酋
-
韩国
-
香港
-
马来西亚
-
马耳他
-
马达加斯加
-
黎巴嫩
-
黑山
- Forex
- Crypto
