数组是一种数据结构,它将元素与索引集合中的位置关联起来。在常规实现中,数组将大小相同的元素存储在连续的内存位置中,因此可以根据索引直接计算出元素的地址。数组是表格、数值网格、图像缓冲区以及计算机科学中许多其他表示形式的基础。
“数组”一词有两个密切相关的含义:一是由编程语言定义的索引集合,二是一种特定的存储组织方式。这两种含义并不总是一致。有些语言层面的数组可以动态增长,可以包含对不同类型对象的引用,也可以有空缺的位置;其底层实现不一定采用单个连续的内存块。反过来,连续存储的数组也可能隐藏在更高层的容器内部。要理解数组的性能和语义,就必须区分集合对外呈现的行为与其物理表示。
索引集合与地址计算
一维数组可以建模为从有限整数索引区间到值的映射。长度为 、下界为 的数组,其有效索引为 。数组的长度是元素个数,而不是最大的有效索引。采用从零开始的索引时,有效区间为 到 ;采用从一开始的索引时,则为 到 。有些语言还允许显式指定下界,包括负值。
对于常规的连续存储数组,设 为首个元素的地址, 为单个元素占用的存储空间大小,以字节为单位。元素 的地址为
这个公式解释了数组最具代表性的访问特性:定位一个元素只需进行固定次数的算术运算,而无须遍历它之前的元素。例如,若数组的起始字节地址为 1000,每个元素占用四个字节,且索引从零开始,那么索引为 6 的元素起始地址就是 1024。该公式的前提是地址和偏移量均可表示,且数组已被合法分配。
存储槽大小相同,并不意味着数组最终表示的每个值都必须具有相同的大小。引用数组使用大小固定的引用槽,每个引用可以指向一个单独分配的对象。因此,数组可以直接访问长度不同的字符串,而不必将字符串本身内嵌存储在数组中。此时,连续存储的是引用序列,而不一定是被引用的对象。
索引集合和元素类型是数组逻辑描述的一部分。存储地址、元素步长、分配所有权及边界等信息,则可能属于实现层面的元数据。如果这些信息无法在静态阶段确定,就可以由运行时描述符携带。相比之下,一些编译型语言允许由编译器确定其中的大部分信息,从而无须为每个数组单独设置运行时描述符。
数组通常与关联集合有所区别:关联集合的键可以是任意值,而不必是有限整数区间内的位置。因此,以整数为键的哈希表并不会仅仅因为键是数字就成为常规数组。同样,数学中的序列规定了值及其顺序,但不规定内存布局、可变性或计算成本。数组这一概念将这种有序、按索引组织的抽象,与能够以低成本按位置访问元素的实现方式联系起来。
操作及其计算成本
对数组的标准分析采用随机存取机模型。在这一模型中,读取一个机器字、进行基本的地址运算以及访问一个地址都只需常数时间。在这些假设下,读取或替换已有数组元素需要 时间。这是对时间复杂度的描述,并不保证在实际硬件上每次访问所耗费的纳秒数都相同。
遍历全部 个元素需要 时间。在未排序的数组中查找某个特定值,最坏情况下也需要 时间,因为可能必须检查每一个元素。有序数组可以使用二分查找,每一步都将剩余候选区间缩小一半,所需的比较次数为 。这种改进依赖于维持元素的有序性,以及具备合适的比较操作;仅靠连续存储并不能实现。
插入有几种不同的含义。替换已有位置上的值只需常数时间,但在保留所有现有元素的前提下,向有序列的序列中插入一个新值,通常需要移动后续元素。对于长度为 、基于数组实现的序列,在位置 之前插入元素可能需要移动 个元素。类似地,删除也会将后续元素向序列开头移动。因此,即使已有足够的存储空间,这两种操作的最坏情况成本仍为 。
如果序列中元素的顺序无关紧要,删除时也可以用最后一个元素替换被删除的元素,并缩短逻辑上的序列。该操作只需要常数次元素移动。它会改变元素顺序,也可能使关于哪个索引对应哪个对象的假设失效。因此,复杂度的说法取决于操作的确切约定,而不只是容器的名称。
“移动一个元素”的成本也需要加以说明。移动一个机器整数或一个引用通常被视为常数时间操作。移动一个内嵌存储的大型记录则涉及更多字节,而复制对象还可能触发编程语言所定义的行为。如果比较操作本身开销很大,那么比较次数与总运行时间就是不同的衡量指标。因此,可以从元素访问次数、比较次数、传输的字节数或对象操作次数等方面,分析在数组上运行的算法。
除去描述信息和内存分配的额外开销,存储 个固定大小元素的数组占用 空间。额外的工作存储空间则取决于算法。有些排序算法在原有存储空间内重新排列元素,而归并排序的实现通常会使用辅助数组。数组这种表示方式本身并不能决定算法是否稳定、是否原地执行,或对于特定工作负载是否高效。
多维数组、形状与视图
多维数组将索引元组与值关联起来。数组的秩是索引维度的数量,而形状则给出每个维度的大小。形状为 的二维数组包含 12 个元素。虽然这样的数组可以表示数学上的矩阵,但步长、所有权和可变视图等存储概念与矩阵的数学性质是不同层面的概念。
常规内存采用线性寻址,因此必须将多维索引转换为一维偏移量。对于一个从零开始索引、具有 行和 列的数组,按行优先顺序存储时,地址为
而按列优先顺序存储时,地址为
行优先存储将同一行中相邻的元素存放在一起;列优先存储则将同一列中相邻的元素存放在一起。这两种布局都不会改变给定索引对所对应的逻辑值,但会影响哪些遍历顺序能够访问相邻的内存位置。
通用的步长表示法为每个维度存储一个以字节为单位的步长 。若第 维的索引下界为 ,则地址公式为
这种表示法不仅支持连续的矩形数据块。每隔一个元素选取一次所得到的子数组,其步长可以是原来的两倍。反向视图可以使用负步长,并相应调整起始地址。二维数组的转置通常只需交换维度及其对应的步长即可表示,无须移动底层元素。
切片用于选取数组的一部分,但不同语言的处理方式有所不同:有的会创建独立副本,有的则会创建共享现有存储空间的视图。使用视图时,通过一个数组对象写入的更改,可能通过另一个数组对象也能观察到。某些选取操作,尤其是使用任意索引列表的操作,更适合通过将元素收集到新数组中来实现,而不是用单个步长公式来表示。同样,重塑形状在某些情况下只需修改元数据,在另一些情况下则需要复制数据。
矩形数组也不同于数组的数组。一个矩形 数组的各行长度一致,并且可以占用一块连续的内存。由行引用组成的数组则可以指向分别分配的各行,而且各行的长度可能不同。这种锯齿状表示适合不规则数据,但访问元素时可能需要额外执行一次引用查找。它的各行在内存中也不一定相邻。因此,索引语法看起来相同,并不意味着存储布局或性能也相同。
动态数组与摊还增长
动态数组将数组式的索引访问与长度可变的逻辑序列结合起来。它通常维护一块底层存储空间、当前长度 和容量 ,其中 。长度表示当前有效元素的数量;容量表示已分配的存储空间最多能容纳多少个元素,超过这一数量就需要分配更大的空间。不能将这些量与底层存储块的固定大小混为一谈。
当 时,追加操作会将元素放入下一个可用位置,并将长度加一。当 时,典型实现会分配一个更大的存储块,将现有元素迁移过去,再按照语言的内存管理规则释放或弃用旧存储块。增长因子属于实现策略。接近 1.5 或 2 的增长因子很常见,但不同容器和运行时版本采用的容量增长序列未必相同。
按几何级数增长可以得到一个重要的总量界。如果每次扩容都将容量翻倍,那么历次扩容中迁移的已有元素总数正比于
因此,在连续执行 次追加操作的过程中,迁移工作的总量为 ,所以通过摊还分析可得,追加操作的时间复杂度为 。但触发重新分配的单次追加操作仍可能耗时 。摊还常数时间描述的是将一系列操作的总成本分摊后的结果;它并不保证最坏情况下的延迟,也不需要任何概率假设。
每次增加固定数量的存储位置,情况则有所不同。如果容量每次只增加一,那么追加 个元素可能导致约 个元素被迁移,总工作量为 。几何增长通过保留富余容量避免了这种情况。如果事先知道最终大小,预留空间可以减少重新分配的次数,不过在某些语言中,构造有效元素与预留尚未使用的存储空间是两种不同的操作。
缩容策略同样重要。如果每次删除后都立即减小容量,那么在插入和移除交替进行的工作负载下,就可能反复扩容和缩容。实现可以保留原有容量,也可以仅在空间利用率降至某个较低阈值以下时才缩容。将扩容与缩容的阈值分开设置,可以避免容量在同一边界附近来回变化。
重新分配的影响不仅限于复制成本,还涉及语义。指向旧存储空间的指针、引用、迭代器或视图可能失效,具体取决于语言和容器。元素迁移也可能调用构造函数或执行其他操作,而不只是复制字节。因此,动态数组在保留按索引直接访问这一核心优势的同时,也引入了有关容量、所有权、元素生命周期和引用稳定性的策略。
不同编程语言中的数组语义
编程语言使用类似数组的语法来表达多种不同的抽象。它们的差异包括:边界是否属于类型的一部分、元素是否内联存储、长度能否改变,以及是否检查越界访问。仅凭表达式 a[i],几乎无法判断这些性质。语言规范规定了可观察的行为;运行时或编译器则可以从符合规范的多种表示方式中作出选择。
在 C编程语言中,数组包含固定数量、类型相同且连续存储的元素。在许多表达式中,数组表达式会转换为指向其首元素的指针,但数组与指针并不是同一种对象。例如,直接对数组对象使用 sizeof,得到的是整个数组的大小;而对指针使用它,得到的则是指针的大小。数组形式的形参声明会被调整为指针形参,因此,仅凭这样的声明,函数并不会接收到完整的数组。
C 语言也说明了访问操作可能不包含边界信息。指向某个元素的指针通常不携带该元素所在数组的长度。程序必须通过接口的其他部分,或利用程序中其他已知信息来获取长度。C 语言的多维数组是以数组为元素的数组;其行主序组织方式正是这种嵌套、连续的存储布局所决定的。
其他一些语言更明确地区分固定大小的数组与可增长的容器。C++ 提供内置数组、std::array 和 std::vector,它们在所有权和大小调整行为上有所不同。Rust 区分固定大小的数组、借用的切片和可增长的向量。Java 数组的长度在创建时便已固定,索引访问会进行边界检查;Java 的多维数组则是由数组引用组成的数组,因此各行可以具有不同的长度。这些区别不仅影响一般应用程序的行为,也影响互操作性。
Python 的内置列表是一种可调整大小的序列,在 CPython 中通常实现为对象引用数组,而不是紧密存储对象实际数据的数组。专门的数值计算库则提供元素类型一致、具有明确形状和步长的多维数组。JavaScript 的 Array 采用索引属性和长度语义,允许存在空位:某个索引处不存在属性,与该处存在属性但值为 undefined,在可观察行为上有所不同。相比之下,JavaScript 的类型化数组在二进制存储之上提供固定格式的数值元素访问。
Fortran编程语言支持多维数组、显式边界、数组表达式和数组区段,元素按列主序排列。这些特性使数组运算成为数值程序的核心,而不只是基于指针算术建立的一套惯例。在这些语言中,名称相似的特性可能提供不同的保证,因此,在理解复杂度声明或在独立编译的组件之间交换数据时,语言层面的约定至关重要。
存储层次结构与硬件性能
当访问模式与存储层次结构相适应时,数组尤其高效。现代处理器通常不会仅从主存中单独取出所请求的一个字节,而是将数据块传入 CPU 缓存,使相邻数据一同可用。因此,顺序遍历紧密排列的数组可以高效利用取回的每个数据块,而沿着引用访问分散的对象,则可能需要多次互不相关的数据传输。
以 64 字节的缓存行和每个元素占 8 字节的数组为例,一个对齐的缓存行可以容纳八个元素。顺序遍历时,只需填充一次缓存行,就可能用到其中全部八个元素。如果每个元素都位于单独分配的内存中,并且分属不同的缓存行,那么同样的遍历可能需要传输多得多的数据。实际性能取决于对齐方式、缓存组织、预取机制,以及还有哪些数据共用这些缓存行,因此,这个例子说明的是局部性,而不是普遍适用的速度比。
连续访问也有利于硬件预取器和单指令多数据执行。向量指令可以同时处理多个相邻数值,而可预测的流式访问则使未来的内存请求更容易被预判。不过,编译器仍需有依据确认向量化不会改变程序语义:迭代之间的依赖关系、可能存在的混叠、对齐要求以及浮点运算规则,都可能阻止或改变这种转换。数组为这些优化提供了可能,但并不保证它们一定会发生。
对于多维数组,循环顺序可能决定相邻两次访问的位置是彼此接近,还是相距甚远。在按行优先存储的矩阵中,沿一行扫描会访问连续元素,而沿一列扫描时,每次访问都会跨过一整行的宽度。缓存分块将计算重新组织为若干子问题,使各子问题所需的数据能够留在缓存中。在矩阵乘法中,目标不仅是减少算术运算次数,还包括在数值离开高速存储器之前,尽可能多地复用它们。
记录的布局还带来了另一种选择。结构体数组将完整记录连续存储,例如依次存储每个粒子的 x, y, z 坐标。数组结构体则将所有 x 坐标存放在一起,所有 y 坐标存放在一起,所有 z 坐标存放在一起。前者适合需要使用整条记录的操作;对于只处理大量记录中同一个字段的操作,后者则可能提高带宽利用率,并有利于向量化。
在并行计算中,使用连续存储时需要注意共享问题。不同线程可能更新处于同一缓存行中的不同元素,从而引发缓存一致性通信,这种现象称为伪共享。在图形处理器上,如果相邻线程的请求可以合并为更少的内存事务,通常就能获得更高的内存吞吐量。这些效应解释了为什么索引访问在理论上的 开销,会与不同访问模式在实际性能上的巨大差异并存。
边界、所有权与正确性
只有当索引属于数组的索引集合,且底层存储仍然有效时,对数组的访问才是有效的。对于从零开始编号的数组,通常的边界条件为
将数组长度与最后一个有效索引混淆,会导致常见的差一错误。若循环使用 而非 ,就会尝试访问数组末尾之外的一个位置,除非循环体内有其他逻辑阻止这次访问。
未经检查的越界写入可能引发缓冲区溢出,破坏相邻的存储区域或程序控制数据。越界读取可能泄露无关数据,也可能导致程序故障。对索引进行检查的语言通常会通过异常、恐慌(panic)或其他规定的机制拒绝此次访问。而在 C 和 C++ 中,许多无效访问会导致未定义行为,因此编译器可以假定有效的程序不会执行这些访问,并据此进行优化。
边界检查并不意味着源代码中的每次访问都必须对应一次独立的机器级比较。编译器有时能够证明循环的所有迭代都不会越界,从而消除冗余检查。将索引、数组长度和计算进度联系起来的循环不变量,为这类变换提供了推理依据。无法完成证明时,运行时检查则用于保证语言所要求的行为。
如果地址计算发生溢出,仅仅保证索引不越界还不够。像 这样的内存分配大小计算,如果使用无法表示其数学乘积的整数类型求值,就可能得到错误的偏小结果。于是,程序实际分配的存储空间可能小于后续索引操作所假定的大小。合并多个维度的大小,或在有符号与无符号索引类型之间转换时,也会出现类似问题。要保证正确性,既需要逻辑索引有效,也需要存储相关计算的结果可表示且有效。
所有权会带来另一类风险。切片或指针所指向的位置可能原本位于边界之内,但对应的存储空间后来已被释放或替换。动态数组的重新分配是这一问题的常见来源。垃圾回收可以使仍可达的对象保持存活,但不会自动防止非预期的共享修改,也无法防止容器接口所规定的所有视图失效情形。
最后,在并发计算之间共享数组时,需要为相互冲突的访问制定规则。即使写入没有越界,只要另一个执行线程在缺少必要同步的情况下访问同一位置,仍然可能发生数据竞争。因此,对数组操作程序进行形式验证时,需要同时考虑多项性质:索引有效、所有权或生命周期得到维护、同步恰当,以及最终内容与预期计算之间的关系。
数组作为基础构件与科学数据的表示方式
许多数据结构的对外接口并不以位置操作为主,但仍以数组为基础。栈可以利用动态数组的末端执行入栈和出栈操作。循环缓冲区使用固定分配的存储空间,索引到达末端后会回绕到起点,从而支持类似队列的行为,而不必在移除元素后移动所有剩余元素。哈希表通常使用数组来存储桶、条目或控制信息,不过其查找语义基于键,而不是序列中的位置。
二叉堆是另一个例子。在从零开始索引的数组表示中,位置 处节点的子节点位于 和 ,前提是这些位置存在;非根节点的父节点位于 。这些索引公式编码了完全二叉树的结构,无须为每条边显式存储一个指针。堆的有序性不变量则是另一项独立性质,由其更新算法负责维护。
在数值计算中,数组用于表示向量、矩阵、采样函数以及更高维的数据。图像可以按高度、宽度和颜色通道这几个维度存储。声音信号可以使用采样位置和声道这两个维度。机器学习系统可以通过增加一个批次维度来表示一批图像。各维度的含义由应用决定;存储描述符记录的是各维度的大小和步长,不一定标明它们在科学上的含义。
稠密数组为每个位置分配空间,包括值为零的位置。对于规模庞大且绝大部分值为零的数据,可以改用稀疏矩阵表示,将非零值与辅助索引一同存储。例如,压缩稀疏行存储格式使用多个数组,分别保存数值、列索引和行边界偏移量。当数据足够稀疏时,这种方式可以节省空间,但也使简单的稠密寻址被对压缩表示的搜索或按索引遍历所取代。
数组也是面向列的数据库处理的基础。将同一字段的值集中存放,可以让查询扫描该字段或对其进行聚合,而不必读取完整记录。空值标记、压缩编码和变长字段会引入辅助数组及偏移量,因此,数据库中的一列并不总是一个简单的、由固定大小的应用数据值组成的数组。
这些应用既体现了数组表示的优势,也揭示了它的局限。当位置具有稳定含义、遍历操作频繁,或存储紧凑性十分重要时,数组尤其适用。如果工作负载主要涉及中间插入、要求对象地址保持稳定,或索引空间极其稀疏,则链式、树形、分段或哈希结构可能更合适。混合设计往往在各组件内部保留数组,同时改变连接这些组件的组织方式。
历史发展与数组编程
在电子计算发展的早期,数组就已占据重要地位,因为科学计算天然涉及表格、向量和矩阵。存储程序计算机提供了可寻址的内存,而指令和寻址约定使程序能够计算出所需数值所在的位置。变址寻址减少了为表中每个位置分别编写指令的需要,将数学中的下标与机器可以反复执行的操作联系起来。
IBM 于 1957 年交付的首个 Fortran 编译器,使程序员能够使用面向科学与工程工作的高级表示法来操作数组。借助多维数组和下标引用,程序员可以表达数值计算,而无须手动将每次数组访问转换为汇编层面的地址运算。Fortran 的列优先存储顺序成为数值计算库沿用至今的接口约定,也影响了用其他语言编写的软件与这些库交换矩阵数据的方式。
ALGOL 60 进一步将数组发展为语言层面的对象,支持声明索引边界和多维索引。它对索引边界的处理表明,从零开始索引是一种设计选择,而非定义数组的数学性质。后来的语言在灵活的索引边界、编译期大小信息、运行时描述符以及简单的机器级表示之间,采取了不同的折中方案。
C 语言于 20 世纪 70 年代初诞生于贝尔实验室,其数组与指针运算紧密相连。这种设计直接暴露了存储布局和地址操作,为系统编程和紧凑的接口提供了支持。由此形成的约定通过操作系统、二进制接口和库产生了广泛影响。受其影响,数组对象与指向元素的指针之间的区别,也一直是编程语言教学中的一个常见话题。
另一条发展脉络围绕着数组编程展开。在这种范式中,整个数组都可以作为操作数,而不只是供逐个访问元素的容器。肯尼斯·E. 艾弗森于 1962 年出版的《一种编程语言》(A Programming Language)介绍了一套表示法,APL 便是在此基础上发展而来的。APL 及后来的面向数组的系统强调归约、转置以及对整个集合进行组合运算等操作。在这些系统中,数组的形状和秩成为表达算法的核心要素。
后来的数值计算环境和库将面向数组的思想带入了科学计算、数据分析和机器学习领域。整数组语法能够描述计算,而不必指定执行该计算所用的具体嵌套循环。实现系统随后可以选择向量指令、并行内核或经过优化的库例程来执行计算。与此同时,这些系统之间的互操作性仍然取决于沿袭自早期传统的具体细节:元素的表示方式、行优先或列优先的存储顺序、索引约定、步长,以及底层存储的所有权。