内存与缓存

数组和链表两种数据结构分别代表了“连续存储”和“分散存储”两种物理结构。实际上，物理结构在很大程度上决定了程序对内存和缓存的使用效率，进而影响算法程序的整体性能。

计算机存储设备

计算机中包括三种类型的存储设备：硬盘（hard disk）、内存（random-access memory，RAM）、缓存（cache memory）。

它们有各自的用途与特性：

• 硬盘：
  • 用途：长期存储数据，包括操作系统、程序、文件等。
  • 特性：断电后数据不会丢失
  • 容量：较大，TB级别
  • 速度：较慢，几百到几千 MB/s
• 内存：
  • 用途：临时存储当前运行的程序和正在处理的数据。
  • 特性：断电后数据会丢失
  • 容量：较小，GB级别
  • 速度：较快，几十GB/s
• 缓存：
  • 用途：存储经常访问的数据和指令，减少CPU访问内存的次数
  • 特性：断电后数据会丢失
  • 容量：非常小，MB级别
  • 速度：非常快，几十到几百GB/s

我们可以将计算机存储系统想象为如图所示的金字塔，越靠近金字塔顶端的存储设备的速度越快、容量越小、成本越高。

总的来说，硬盘用于长期存储大量数据，内存用于存储程序运行中正在处理的数据，而缓存则用于经常访问的数据和指令，以提高程序运行效率。三者共同协作，确保计算机系统高效运行。

在程序运行时，数据会从硬盘中被读取到内存中，供CPU计算使用。缓存可以看做CPU的一部分，它通过智能地从内存加载数据，给CPU提供高速的数据读取，从而显著提升程序的执行效率，减少对较慢内存的依赖。

数据结构的缓存效率

缓存虽然在空间容量上远小于内存，但它比内存快得多，在程序执行速度上起着至关重要的作用。由于缓存的容量有限，只能存储一小部分频繁访问的数据，因此当CPU尝试访问的数据不在缓存中时，就会发生缓存未命中（cache miss），此时CPU不得不从速度较慢的内存中国加载所需数据。

缓存未命中发生越少，CPU读写数据的效率就越高，程序性能也就越好。我们将CPU从缓存中成功获取数据的比例称为缓存命中率，用这个指标来衡量缓存效率。

为尽可能达到更高的效率，缓存会采取以下数据加载机制。

• 缓存行：缓存不是单字节地存储与加载数据，而是以缓存行为单位。相比于单个字节的传输，缓存行的传输形式更加高效。
• 预取机制：处理器会尝试预测数据访问模式（如顺序访问、固定步长访问等），并根据特定模式将数据加载至缓存之中从而提升命中率。
• 空间布局性：如果一个数据被访问，那么它附近的数据也可能近期被访问。因此缓存在加载某一数据时，也会加载其附近的数据，以提高命中率。
• 时间布局性：如果一个数据被访问，那么它在不久的将来很可能再次被访问。缓存利用这一原理，通过保留最近访问过的数据来提高命中率。

实际上，数组和链表对缓存的利用效率是不同的，主要体现在以下几个方面。

• 占用空间：链表元素比数据元素占用空间更多，导致缓存中容纳有效数据量更少。
• 缓存行：链表数据分散在内存各处，而缓存是“按行加载”的，因此加载到无效数据的比例跟高。
• 预取机制：数组比链表数据访问模式更具“可预测性”，即系统更容易猜出即将被加载的数据。
• 空间布局性：数组被存储在集中的内存空间中，因此被加载数据附近的数据更有可能即将被访问。

数组具有更高的缓存命中率，因此它在操作效率上通常优于链表。使得在解决算法问题时，基于数组实现的数据结构更受欢迎。

注意：高缓存效率并不意味着数组在所有情况下都优于链表。实际应用中选择哪种数据结构，应根据具体需求来决定。