知识卡片
局部性影响速度
内容
连续数组不只节省空间，也能利用CPU缓存局部性提升访问速度；链式结构表达灵活，却可能因对象分散而慢。发散：算法复杂度相同的结构，在现代硬件上也会因内存布局产生明显差距。
参考来源
- 位置：《你真的会写代码吗-2021》第4章《宝贵的内存：空间效率》"4.3.1"后关于缓存局部性的讨论（源文件：_epub-src/OEBPS/Text/0014.xhtml）
- 结论依据：原文明确"同样可以出于时间效率考虑使用它们，因为数组带来了缓存局部性（cache locality）的好处……内存中距离较近的数据（如数组）比随机分布的数据（如链表）的访问速度更快"，并解释这是CPU缓存按行加载相邻数据的结果。
- 原始内容：虽然我推荐使用普通数组是出于内存效率的考虑，但实际上，同样可以出于时间效率考虑使用它们，因为数组带来了缓存局部性（cache locality）的好处。简而言之，内存中距离较近的数据（如数组）比随机分布的数据（如链表）的访问速度更快。这得益于CPU缓存的组织结构……缓存将相邻的小块数据保存在一起。