关于数组在内存中的存放

由腾讯的一个笔试题牵涉的知识点，自己之前没有接触过，就总结了一下：

题目原文：

在程序设计中，要对两个16K×16K的多精度浮点数二维数组进行矩阵求和时，行优先读取和列优先读取的区别是（）
A、没区别
B、行优先快
C、列优先快
D、2种读取方式速度为随机值，无法判断

【解析】若在内存中,则数据可以”随机存取”,但内存数据被读取或写入时,所需要的时间与这段信息所在的位置无关.但是在读取和写入磁盘时,其所需要的时间与位置就会有关系.因为在BASIC,PASCAL和C/C++语言中,数组的存放是按照行优先来存放的,按行号第一行第二行…以此类推.本体关键是考察内存抖动的问题,如果按列访问则需要跳过一大串内存地址,这样可能需求的内存地址不在当前页中则需要进行页置换,这样便需要硬盘IO,减低速度.

【知识点】

一、关于多维数组在内存中的存放问题（出处多维数组在内存中的存放）

1、数组（向量）——常用数据类型
    　一维数组（向量）是存储于计算机的连续存储空间中的多个具有统一类型的数据元素。
    　同一数组的不同元素通过不同的下标标识。
       （a₁,a₂,…,a_n)

2、二维数组
    　二维数组A_mn可视为由m个行向量组成的向量，或由n个列向量组成的向量。
       
    　二维数组中的每个元素a_ij既属于第i行的行向量，又属于第j列的列向量。

3、多维数组
    　三维数组A_mnp可视为以二维数组为数据元素的向量。四维数组可视为以三维数组为数据元素的向量……
    　三维数组中的每个元素a_ijk都属于三个向量。四维数组中的每个元素都属于四个向量……

4、数组的顺序存储方式
    　由于计算机内存是一维的，多维数组的元素应排成线性序列后存人存储器。
    　数组一般不做插入和删除操作，即结构中元素个数和元素间关系不变化。一般采用顺序存储方法表示数组。
（1）行优先顺序
    　将数组元素按行向量排列，第i+1个行向量紧接在第i个行向量后面。
　　【例】二维数组A_mn的按行优先存储的线性序列为：
    a₁₁,a₁₂,…,a_1n,a₂₁,a₂₂,…,a_2n,……，a_m1,a_m2,…，a_mn

  注意：
    　①PASCAL和C语言中，数组按行优先顺序存储。
    　②行优先顺序推广到多维数组，可规定为先排最右的下标。

（2）列优先顺序
    　将数组元素按列向量排列，第i+1个列向量紧接在第i个列向量后面。
　　【例】二维数组A_mn的按列优先存储的线性序列为：
    a₁₁,a₂₁,…,a_m1,a₁₂,a₂₂,…,a_m2,……，a_1n,a_2n,…，a_mn

  注意：
    　①FORTRAN语言中，数组按列优先顺序存储。
    　②列优先顺序推广到多维数组，可规定为先排最左的下标。

5、数组元素的地址计算公式
（1）按行优先顺序存储的二维数组Amn地址计算公式
        LOC(a_ij)=LOC(a₁₁)+[(i-1)×n+j-1]×d
    其中：
　　①LOC(a₁₁)是开始结点的存放地址（即基地址）
　　②d为每个元素所占的存储单元数
　　③由地址计算公式可得，数组中任一元素可通过地址公式在相同时间内存取。即顺序存储的数组是随机存取结构。

（2）按列优先顺序存储的二维数组Amn地址计算公式
          LOC(a_ij)=LOC(a₁₁)+[(j-1)×m+i-1]×d

（3）按行优先顺序存储的三维数组Amnp地址计算公式
      LOC(a_ijk)=LOC(a₁₁₁)+[(i-1)×n×p+(j-1)×p+k-1]×d

（4）下界不为1的二维数组的地址计算公式
　　①二维数组A[c1..d1,c2..d2]的地址计算公式：
      LOC(a_ij)=LOC(a_c1c2)+[(i-c1)×(d2-c2+1)+j-c2]×d
 　②下界为0的二维数组的地址计算公式（C语言中使用）
      LOC(a_ij)=LOC(a₀₀)+[i×(d2+1)+j]×d
   注意：
    　以下讨论的数组存储结构都以C语言下标表示。

二、关于缺页中断的问题

由于程序可能会远大于内存，需要引入虚拟内存。基本思想是：每个程序都拥有自己的地址空间，这个空间被分割成很多块，每一块称作为一个页面，每一页有连续的地址范围，这些页被映射到物理内存，但并不是所有的页都必须在内存中才能运行程序。当程序引用到一部分在物理内存中的地址空间时，由硬件立刻执行必要的映射，而当程序引用到一部分不在内存的地址空间时，由操作系统负责将缺失的部分装入物理内存并重新执行失败的指令。如果一个页面没有映射，内存管理单元注意到它没有映射时，使CPU陷入到操作系统，这个陷阱称为缺页中断。

三、内存抖动的问题