二维数组在内存中的行存储和列存储

04-19 1122阅读

（图片来源网络，侵删）

例题：

0. BaseAddress

1. 行存储方式（Row-major order）

2. 列存储方式（Column-major order）

3. 解方程找到 i 和 j

行存储和列存储方式的区别

行存储方式（Row-major order）:

列存储方式（Column-major order）:

优缺点

行存储方式的优点:

行存储方式的缺点:

列存储方式的优点:

列存储方式的缺点:

行存储方式的应用场景

列存储方式的应用场景

混合存储方式

另一道计算例题：

从填充的角度去理解上道题：

例题：

二维数组 N 的元素是 4 个字符（每个字符占一个存储单元）组成的串，行下标 i 的范围从 0 到 4，列下标 j 的范围从 0 到 5，N 按行存储时元素 N[3][5]的起始地址与 N 按列存储时元素（）的起始地址相同。

我们需要理解二维数组在内存中的行存储和列存储方式，并找到对应元素的地址。

0. BaseAddress

在内存中，BaseAddress 是数组的起始地址，即数组中第一个元素（通常是 N[0][0]）的内存地址。所有数组元素的地址计算都是基于这个起始地址进行的。

1. 行存储方式（Row-major order）

在行存储方式中，数组的元素是按行顺序存储的。对于数组 N[5][6]（行数为5，列数为6），元素 N[i][j] 在内存中的位置可以通过下面的公式计算： N[i][j] =BaseAddress + (i *列数+ j) *元素大小其中，元素大小是由于每个元素由4个字符组成，所以是 4 字节。

对于 N[3][5]，地址计算为：

N[3][5] = BaseAddress + (3 * 6 + 5) * 4

N[3][5] = BaseAddress + 23 * 4

N[3][5] = BaseAddress + 92

2. 列存储方式（Column-major order）

在列存储方式中，数组的元素是按列顺序存储的。对于同样的数组 N[5][6]，元素 N[i][j] 的地址计算公式变为：

N[i][j] = BaseAddress + (j * 行数 + i) * 元素大小

我们需要找到一个元素 N[i][j]，使得它在列存储方式中的地址与行存储方式中 N[3][5] 的地址相同：

N[i][j] = BaseAddress + (j * 5 + i) * 4 = BaseAddress + 92

(j * 5 + i) * 4 = 92 ===> (j * 5 + i) = 23

3. 解方程找到 i 和 j

我们需要找到满足 (j * 5 + i) = 23 的 i 和 j 的整数解，其中 i 的范围是 0 到 4，j 的范围是 0 到 5。通过试验或解方程，我们找到：

当 j = 4 时，( 4 * 5 + i = 23 ) 解得 ( i = 3 )。
因此，N[3][4] 是按列存储时与按行存储的 N[3][5] 起始地址相同的元素。

行存储和列存储方式的区别
1. 行存储方式（Row-major order）:
  - 数组元素按行顺序存储在内存中。
  - 对于二维数组 N[i][j]，元素 N[i][j] 的地址计算公式为： N[i][j] =BaseAddress + (i *列数+ j) *元素大小
  - 这是 C/C++、Java、Python 等多数编程语言采用的默认方式。
2. 列存储方式（Column-major order）:
  - 数组元素按列顺序存储在内存中。
  - 对于二维数组 N[i][j]，元素 N[i][j] 的地址计算公式为： N[i][j] = BaseAddress + (j * 行数 + i) * 元素大小
  - 这是 Fortran 和 MATLAB 等语言采用的方式。
优缺点

行存储方式的优点:
- 局部性优化：在处理行相关的数据时，由于数据连续存储，可以更好地利用 CPU 缓存，提高访问效率。
- 简单直观：与多数编程语言的默认数组遍历顺序一致，编程时较为直观。
  行存储方式的缺点:
  - 在需要频繁访问列数据的情况下，可能会导致较多的缓存未命中，降低性能。
    行存储方式的主要缺点通常是在需要频繁访问列数据的场景中性能降低。这种性能下降主要由以下几个因素引起：
    1. 缓存未命中（Cache Misses）:
      - 现代计算机系统使用缓存来减少访问主存储器的时间。缓存工作基于局部性原理，包括时间局部性和空间局部性。行存储方式优化了对行数据的空间局部性，因为连续的行数据被存储在连续的内存地址中。
      - 然而，当访问列数据时，数据元素在内存中是间隔存放的。例如，在二维数组中，访问同一列的下一个元素需要跳过整行的元素。这种存储方式导致每次列数据访问可能都会引发缓存未命中，因为需要的数据并不在缓存中连续存储。
    2. 内存带宽利用不足:
      - 当处理器从内存中读取数据时，它通常会一次读取一个“字块”（word block），这是一定数量的连续字节。在行存储中，如果执行的是列操作，那么每次内存读取可能只用到很少的相关数据，而其余数据则被浪费，这导致内存带宽利用率低下。
    3. 预取策略的效率降低:
      - 现代处理器使用预取策略来预测接下来可能需要的数据，并提前从内存中加载到缓存中。行存储方式在进行列访问时，预取器可能难以正确预测接下来需要哪些数据，因为这些数据在内存中不是连续的。
    4. 多线程和并行处理的复杂性增加:
      - 在多线程环境中，如果多个线程需要访问同一数组的不同列，行存储方式可能导致更频繁的缓存行冲突和无效化，这会降低并行执行的效率。
    列存储方式的优点:
    - 优化列操作：在需要频繁处理列数据的应用中（如某些数学和统计操作），可以更有效地利用 CPU 缓存，提高性能。
      列存储方式的缺点:
      - 在处理行数据时可能效率不如行存储方式。
        行存储方式的应用场景
        
        游戏开发:
        
        在游戏开发中，经常需要快速访问和更新对象的属性，如位置、速度等，这些属性通常在对象的数据结构中按行顺序存储。行存储方式可以快速加载整个对象的数据，优化性能。
        
        应用程序开发:
        
        许多应用程序，如客户管理系统或电子商务系统，需要处理大量的事务数据，这些数据通常按行进行访问和更新。行存储方式使得这些操作更为高效。
        
        传统关系数据库:
        
        大多数关系数据库系统（如 MySQL, PostgreSQL）在处理交易型查询时使用行存储，因为这些查询通常涉及到多个列的少量行。
        列存储方式的应用场景
        
        大数据分析和数据仓库:
        
        在数据仓库和大数据分析中，列存储方式允许快速读取大量数据的特定列，这对于执行统计分析和报告非常有用。例如，如果一个分析师只需要访问销售数据中的“销售额”和“日期”列，列存储可以大幅减少需要读取的数据量。
        
        科学计算和工程应用:
        
        在科学计算中，经常需要对大型矩阵进行列操作，如矩阵乘法和其他线性代数运算。列存储方式可以提高这些操作的效率。
        
        现代列式数据库:
        
        一些现代数据库系统，如 Apache Cassandra 和 Google Bigtable，采用列存储方式来优化读取大量数据的特定列的性能，特别适用于读密集型的应用场景。
        混合存储方式
        
        一些现代系统甚至采用混合存储方式，结合行存储和列存储的优点，以适应多变的数据访问模式。例如，南大通用 GBase数据库和Microsoft SQL Server 的某些版本就支持这种混合模式，可以根据应用需求动态优化数据存储和访问。
        
        总结来说，选择行存储还是列存储取决于数据访问模式。了解和选择合适的存储方式可以显著影响程序的性能和效率。
        
        另一道计算例题：
        
        设有数组 A[i,j]，数组的每个元素长度为 3 字节，i 的值为 1 到 8，j 的值为 1 到 10，数组从内存首地址 BA 开始顺序存放，当以列为主序存放时，元素 A[5,8]的存储首地址是 BA+？
        
        此数组是一个8行10列的数组，元素大小为3字节，但i，j分别都是从1开始计数的。
        
        如果死套公式，列存储：
        
        A[i][j] = A[5][8] = BA + (j * 行数 + i) * 元素大小 = BA + （8*8+5）*3 = BA + 69*3 = BA + 207。就会得到错误答案。
        
        我们的来计算元素 A[5,8] 的地址是基于列主序存储的正确公式，但是在计算过程中有一点小错误需要纠正。公式本身是正确的，但应用时需要注意细节。让我们一步步来检查和应用这个公式：
        
        在此题中，正确公式是：A[i][j] = BaseAddress + ((j-1)* 行数 + (i-1)) * 元素大小
        
        这里的 (i) 和 (j) 是从1开始的索引，因此要计算以0为基的索引，我们需要从 (i) 和 (j) 中分别减去1。
        
        对于元素 A[5,8]，使用以下参数：
        
        (i = 5) i-1=4
        (j = 8) j-1=7
        行数 = 8（因为 (i) 的范围是1到8）
        元素大小 = 3 字节
        将这些值代入公式中 A[5][8] = BA + (7 * 8 + 4) * 3 = BA + 180字节。
        因为我们是从1开始计数的，而在计算内存地址时需要以0为基数。这样的细节在处理数组和内存地址计算时非常重要。
        
        从填充的角度去理解上道题：
        
        在列主序存储中，数组的元素是按列填充的，也就是说，首先填充第一列的所有行，然后是第二列的所有行，依此类推。
        
        给定的数组 A[i, j] 的维度是 i = 1 到 8 和 j = 1 到 10，每个元素占用 3 字节。我们需要找到元素 A[5,8] 的存储首地址。
        
        按列主序，第一列的元素 A[1,1], A[2,1], ..., A[8,1] 都先被存储，每个元素占用 3 字节。因此，第一列占用的总字节数是 8 * 3 = 24 字节。同理，每列都占用 24 字节。
        
        元素 A[5,8] 位于第 8 列，第 5 行。要找到这个元素的地址，我们需要先计算前 7 列的总字节数，然后加上到第 5 行的偏移量。
        
        前 7 列占用的字节总数 = 7 列 × 24 字节/列 = 168 字节
        在第 8 列中，前 4 行占用的字节 = 4 行 × 3 字节/行 = 12 字节
        因此，元素 A[5,8] 的存储首地址 = 基地址 BA + 168 字节 + 12 字节 = BA + 180 字节。
        
        所以，元素 A[5,8] 的存储首地址是 BA + 180 字节。