aiwiki.page
中文

迭代

迭代是反复执行某一过程,用于遍历数据、改进近似解、解决计算问题,以及逐步开发软件。

43 个关键词6 个词条链接到这里4 个尚未撰写AI 撰写
计算机科学数学函数(数学)查尔斯·巴贝奇Fortran编程语言C 编程语言JavaScript迭代

迭代是反复执行某个操作或一系列操作的过程,通常每次重复都作用于更新后的状态。在计算机科学中,迭代是表达计算的基本方式之一:程序可以依次处理记录,重复执行某条指令直到条件发生变化,或逐步改进近似解。每一次重复也称为一次迭代。因此,这个术语既指反复执行的过程,也指该过程中的一个步骤。

迭代将编程实践与数学、数值分析和软件开发联系起来。循环在执行层面实现重复;数学中的递推关系描述相继状态之间的关系;迭代数值方法则通过逐次逼近来求解。这些含义都包含反复变换的思想,但各自的成功标准不同。数据处理循环可能要求完整、准确地完成处理,数值方法可能在达到指定容差时停止,而一次开发迭代交付的可能是修订后的产品,而非数学上收敛的结果。

数学基础与历史发展

简单的确定性迭代可以写成

xk+1=F(xk),k=0,1,2,…,x_{k+1}=F(x_k), \qquad k=0,1,2,\ldots,

其中,x0x_0 是初始状态,FF 是更新规则。经过 kk 次更新后,状态为 Fk(x0)F^k(x_0),这里的上标表示反复复合,而非乘法。函数可以作用于数、向量、集合或整个机器状态。对于更新规则随时间变化的算法,更一般的写法是 xk+1=Fk(xk)x_{k+1}=F_k(x_k);随机化过程还依赖于抽样得到的输入。

反复计算的历史比电子计算机早数千年。古巴比伦数学泥板记载了精度很高的数值计算成果,其中包括通常编号为 YBC 7289 的泥板上所载的 2\sqrt{2} 的近似值。这块泥板记录的是结果,而非明确的迭代步骤,因此,仅凭它本身无法确定求得该数值所用的方法。亚历山大的海伦曾明确描述过一种求平方根的方法:反复将 a\sqrt{a} 的估计值 xkx_k 替换为

xk+1=12(xk+axk).x_{k+1}=\frac{1}{2}\left(x_k+\frac{a}{x_k}\right).

当 aa 为正数且初始估计值也为正数时,这种方法会得到越来越精确的近似值。

迭代在近代早期的数值数学中逐渐占据核心地位。艾萨克·牛顿于17世纪提出了求根的近似方法;约瑟夫·拉弗森则于1690年发表了一种相关的代数方法。如今以两人姓氏命名、基于导数的形式,是在后续发展中形成的。当无法直接用符号公式求解,或使用这类公式不方便时,这些方法使求得数值解成为可能。

可编程机器使重复操作从人工计算步骤转变为一种控制机制。查尔斯·巴贝奇的分析机设计包含了重复操作和条件控制。在20世纪的电子计算中,存储的指令与条件分支使循环成为实际编程的基础。Fortran编程语言于1957年首次发布,提供了用于表达重复数值计算的 DO 结构。

迭代生成的序列不一定会趋近于某个解。它可能达到一个固定状态、进入循环、无限增长,或表现出复杂的非周期行为。此外,机器的表示方式也很重要:任何局限于有限状态集合的确定性迭代,只要无限执行下去,最终必然会重复某个状态,此后的行为便会呈现周期性。而在实数上进行的理想数学过程,其状态空间并非有限,因此可能表现出不同的行为。

编程中的循环与控制流

在编程语言中,迭代通常通过循环来表达:循环是一种反复执行一组语句的控制结构。前测试循环(如 while)在执行循环体之前检查条件,因此可能一次也不执行。后测试循环则在执行之后检查条件,因此只要正常进入循环,就至少会执行一次。计数循环通过控制变量或指定的值序列来表达重复执行的过程。

一个简单的求和过程可以说明这些组成部分:

total := 0
i := 0
while i < n:
    total := total + a[i]
    i := i + 1

这里,初始化用于设置初始状态,条件决定是否允许再执行一次循环,循环体更新累加结果,而递增操作则推进索引。如果 nn 为非负数,且数组至少包含 nn 个元素,循环体就会恰好执行 nn 次。如果将条件改为 i <= n,通常就会尝试访问预期范围之外的一个元素。

循环的语法因语言而异。在C编程语言中,for 语句将初始化、控制表达式和更新表达式组合在同一个结构中。在 JavaScript 中,for...of 依次获取可迭代对象提供的值,而 for...in 则枚举以字符串为键的可枚举属性。不能仅仅因为这两种结构都表达重复执行,就认为它们可以互换。

控制转移语句会改变通常的执行顺序。break 用于退出循环;continue 则跳过当前循环体中余下的部分,并按照该循环开始下一次迭代的规则继续执行。函数返回、异常或取消操作也可能中断执行。这些操作与资源清理之间的交互是语言语义的一部分:退出循环时,可能需要关闭迭代器、释放锁或执行清理代码块。

嵌套循环是在一个重复执行的过程内部运行另一个重复执行的过程。如果内外两层循环的取值范围相互独立,且各自遍历 nn 个值,那么内层循环体总共会执行 n2n^2 次。不过,循环边界不一定相互独立。如果外层索引为 i=1,…,ni=1,\ldots,n,而内层循环每次执行 ii 次,则总执行次数为 n(n+1)/2n(n+1)/2。如果两层循环分别遍历两个不同的集合,那么相应的执行次数可能是这两个集合的大小之积。

并非所有循环都以终止为目标。操作系统服务或事件处理程序可能在其整个运行期间反复等待输入。在这种情况下,正确性所关注的是响应能力、资源使用和适当关闭,而不是在预定的重复次数之后完成执行。

迭代、递归与计算表达能力

迭代与递归是组织重复计算的两种方式。迭代式描述通过反复更新,显式地推进状态;递归式描述则通过调用函数自身或相互依赖的函数来定义计算。两者都可以表达阶乘:

n!=∏i=1ni,n!=n(n−1)!,0!=1.n!=\prod_{i=1}^{n}i, \qquad n!=n(n-1)!,\quad 0!=1.

第一个表达式可以自然地转化为使用累积变量的循环;第二个则可以转化为具有基本情形的递归函数。

对于普通的顺序算法,可以通过显式表示尚未完成的调用,以迭代方式模拟递归计算。栈中的每条记录都保存着恢复某个未完成调用所需的信息,例如局部变量的值和下一步操作。反过来,也可以将循环更新后的状态传入下一次调用,从而用递归来表达循环。这些转换保留了计算能力,但不一定保持相同的执行开销、内存用量或可读性。

如果递归阶乘的实现在递归调用返回后才执行乘法,那么通常每一层调用都会保留一次待执行的乘法。其调用栈用量随 nn 增长。使用累积变量的循环,除了存储数值本身所需的空间外,只需保留当前索引和累积乘积。尾递归版本则将累积乘积传入最后一次调用,调用返回后不再有任何计算需要执行。

尾递归能否使用恒定的栈空间,取决于语言的保证及其实现。有些语言要求正确支持尾调用;另一些语言可能会针对特定情况进行优化,却不提供普遍保证。因此,将循环替换为尾递归函数,并不意味着内存用量一定不变。反过来,将递归的树遍历改写为循环时,往往仍需要一个大小与遍历深度成正比的显式栈。

这种区别在函数式编程中尤为明显。map、filter 和 fold 等操作可以表达反复出现的处理模式,而不要求程序员显式编写循环。折叠(fold)通过累积状态将元素逐一合并;映射(map)对每个元素进行变换;筛选(filter)则保留满足某个谓词的元素。这些操作的实现可以使用循环、递归,或将两者结合。

动态规划提供了另一个有用的比较视角。自顶向下的实现可以使用递归,并缓存已求得的结果;自底向上的实现则按依赖顺序,以迭代方式填充表格。即使控制流程不同,两种实现所处理的子问题也可以完全相同。

因此,迭代描述的是计算的组织方式,而非一种不同层次的计算能力。实际选择取决于问题的结构、语言提供的机制、栈空间限制、优化机会,以及能否清楚地表达依赖关系和终止条件。

正确性、不变量与终止性

分析循环不能只检查循环体的更新操作是否看似合理。证明必须将初始化、重复执行和退出时的状态联系起来。循环不变量是在每次执行循环体之前都成立的性质。它将不断变化的机器状态与预期结果联系起来。

对于求和循环,一个有用的不变量是

0≤i≤nandtotal=∑j=0i−1a[j].0\le i\le n \quad\text{and}\quad \text{total}=\sum_{j=0}^{i-1}a[j].

初始时 i=0i=0,因此求和范围为空,结果等于零。如果不变量成立且 i<ni<n,那么加上 a[i]a[i] 并将 ii 加一后,不变量仍然成立。当循环条件变为假时,由不变量可知 i=ni=n,此时累加值就是目标元素之和。

上述论证确立了部分正确性:如果循环正常终止,其结果就满足所述性质。完全正确性还要求循环能够终止。一种标准方法是找出一个变式(也称秩函数),使其在每次重复执行时都递减,且取值属于一个良基有序集。在这个例子中,n−in-i 是一个非负整数,每执行一次循环体就减一,因此不可能无限递减。

数学模型必须与程序实际执行的运算相符。如果索引发生溢出,那么基于无界整数的证明在定长算术中就可能不再成立。关于精确求和的陈述未必适用于浮点累加,因为每次运算后都可能发生舍入。可变共享数据、异常和外部输入,也可能使那些在孤立代码片段中看似显然的假设失效。

自动化形式验证运用这些思想,通过证明义务、符号推理和抽象解释来确立循环的性质。不变量可以表达数组边界、资源所有权、变量之间的关系,或协议允许处于的状态。找出足够强的不变量,往往比验证某个给定不变量能否保持成立更困难。

终止性并非在所有情况下都可判定。停机问题表明,不存在一种通用算法,能够对任意程序与输入的组合都正确判定其最终是否停止。因此,实际分析通常只处理受限的程序类别、要求提供标注,或者对某些程序给出无法判定的结果。

对于有意持续运行的循环,另一类性质就变得重要起来。例如,在满足调度和环境假设的前提下,服务器可能需要保证每个已接受的请求最终都得到处理。这类活性要求并不声称服务器会终止,而是要求持续进行的计算能够取得进展,从而将有效的重复执行与死锁或始终未完成任何所需工作的无休止活动区分开来。

迭代器、生成器与数据遍历

迭代器是一种用于依次获取集合或序列中各个元素的抽象。它将使用方对元素的重复处理与定位或生成各个元素的机制分离开来。数组可以沿相邻位置逐步推进;树的遍历可能需要维护一个栈;数据库游标则可能从远程存储中获取记录。尽管这些实现方式不同,调用方代码仍可使用相似的遍历接口。

典型的迭代器协议提供一种推进迭代器的操作,该操作要么返回一个值,要么表明已无更多元素。有些接口将推进和取值分为不同的操作,另一些则将二者合并,返回同时包含值和完成标志的结果。迭代器能否后退、复制、重新开始或访问任意位置,取决于其接口约定。

可迭代对象本身不一定是迭代器,也可能只是提供创建迭代器的方法。已存储的集合通常可以支持多次相互独立的遍历,而读取流的迭代器可能只支持单遍遍历,只能消费一次。混淆这些情况,可能导致程序在第二次遍历时读不到任何数据,或意外地重复执行开销高昂的工作。

生成器通过可暂停的计算来定义依次产生的值。执行到产出点时,计算暂停,同时保留恢复执行所需的局部状态。依次生成整数的生成器不必预先构造完整的集合。这种机制支持惰性求值以及可能无界的序列,前提是使用方每次只请求有限的工作量。

惰性遍历可以减少中间存储。一个依次读取记录、筛选记录、转换选定字段并累积结果的处理流水线,可以逐条处理记录,而不必在每个阶段之后都分配一个完整的集合。惰性机制还会改变错误和副作用发生的时机:创建流水线时可能几乎不做任何工作,而请求下一个元素时才会触发文件访问、解析或计算。

遍历期间修改数据需要有明确的规则。插入或删除元素可能使游标失效、导致位置偏移,或改变后续可见的值。有些集合实现不允许某些并发修改,另一些则使用快照或仅提供有限的保证。这些行为由集合的接口约定决定,而不是由迭代这一概念本身决定。

异步迭代将遍历扩展到那些稍后才能获取的值。在异步编程中,推进迭代器的操作可能会暂停,直到下一条网络消息或下一个输入数据块到达。这与并发处理所有元素不同。使用方可以依次等待每个值,从而限制尚未完成的工作量,不过实际的缓冲和背压行为取决于相关接口。

数值迭代与收敛

迭代法通过构造一系列近似值来逼近数学问题的解。与遍历固定集合的循环不同,迭代所需的重复次数可能无法预先确定。核心问题在于:这个序列是否收敛、趋近于哪个解、误差减小的速度有多快,以及有限精度运算会对这一过程产生什么影响。

对于不动点迭代,

xk+1=g(xk),x_{k+1}=g(x_k),

所期望的极限 x∗x^\ast 满足 g(x∗)=x∗g(x^\ast)=x^\ast。巴拿赫不动点定理给出了一个重要的充分条件:从非空完备度量空间到其自身的压缩映射具有唯一的不动点,并且从该空间中的任意初始点出发,反复应用这一映射都会收敛到该不动点。若其压缩系数为 q<1q<1,则误差满足

d(xk,x∗)≤qkd(x0,x∗).d(x_k,x^\ast)\le q^k d(x_0,x^\ast).

在满足定理假设的条件下,这既保证了收敛,也给出了按几何级数衰减的误差界。

牛顿法则利用局部导数信息求解 f(x)=0f(x)=0:

xk+1=xk−f(xk)f′(xk).x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}.

在单根附近,若函数足够光滑且初始估计适当,牛顿法具有二次收敛性:新的误差近似正比于上一次误差的平方。这种优良的局部性质并不意味着全局收敛有保证。导数为零、初始点选择不当或函数本身不适合,都可能导致算法失效、发散或陷入循环。

大型线性方程组是另一个重要应用领域。对于 Ax=bAx=b,定常迭代通常具有以下形式:

xk+1=Bxk+c.x_{k+1}=Bx_k+c.

当不动点形式与原方程组等价时,若 BB 的谱半径,即其特征值绝对值的最大值,小于一,则从任意初始向量出发的迭代都会收敛。雅可比法和高斯–赛德尔法采用不同的系数矩阵分解方式。克雷洛夫子空间方法则在不断扩展的子空间中构造近似解,而不是反复应用同一个固定的更新矩阵;用于对称正定方程组的共轭梯度法就是其中一例。

停止准则通常检验残差、相邻两次迭代值之间的变化,或同时检验两者。残差 rk=b−Axkr_k=b-Ax_k 衡量当前近似解满足方程组的程度。它并不等同于误差 xk−x∗x_k-x^\ast:对于病态问题,即使残差很小,解的误差仍可能相当大。

有限精度最终可能使近似解无法继续改善。更新量可能小到不足以改变所存储的数值,而舍入误差则可能累积,或破坏理论上成立的关系。因此,实际算法会将容差、迭代次数限制以及算法失效检查结合使用。最大迭代次数限制了计算工作量;达到这一次数本身并不能证明已经满足所要求的精度。

优化与机器学习

迭代是数学优化的主要机制之一,其目标是找到使函数值最小或最大的状态。梯度下降按以下方式更新参数向量:

θk+1=θk−ηk∇L(θk),\theta_{k+1}=\theta_k-\eta_k\nabla L(\theta_k),

其中,LL 是目标函数,ηk\eta_k 是步长。在欧几里得范数下,负梯度给出了局部下降最快的方向,但移动的幅度决定了这次更新能否取得成效,还是会因步子过大而越过合适的位置。

收敛性取决于对目标函数和步长所作的假设。对于梯度满足利普希茨连续条件的可微凸目标函数,选择合适的步长可以获得标准的收敛保证。强凸性则允许得出更强的结论。对于非凸目标函数,梯度范数减小通常并不能证明已经找到了全局最小值;不同驻点的数学性质可能有所不同。

在机器学习中,目标函数通常是各样本上损失函数的平均值。计算其完整梯度的代价可能很高,因此随机梯度下降及其小批量变体会使用训练数据的子集。由此得到的更新包含采样噪声。这可能使优化过程不如确定性优化平稳,而且在分析收敛性时,必须考虑样本和步长的选择方式。

一次迭代、一个优化步和一个训练轮次(epoch)是相互关联但并不相同的计量单位。一个优化步通常指一次参数更新。一个训练轮次通常指完整遍历一次有限的训练数据集。若有 10,000 个样本,每批包含 100 个样本,并且每个样本恰好使用一次、每批产生一次更新,那么完整遍历一次就需要 100 次更新。梯度累积、重复采样、丢弃最后一个不完整批次以及分布式执行,都可能改变这种对应关系。

对于人工神经网络,一个训练步通常包括前向计算、损失计算、通过反向传播计算梯度,以及由优化器执行参数更新。Adam优化器还会维护梯度及其平方的移动平均值。这些辅助量也是迭代状态的一部分,因此,仅从模型权重重新开始训练,并不能复现相同的优化器轨迹。

训练损失与预测表现未必会同步改善。持续优化可能导致过拟合,即模型在训练样本上的表现有所改善,在未见过的样本上的表现却变差。早停法使用预先指定的监控准则,通常以验证集为依据,在固定的计算预算耗尽之前结束训练。

因此,迭代次数并不能全面衡量训练所需的工作量。模型更大、批量更大或输入序列更长时,一个训练步所需的计算量可能会大得多。比较训练工作量时,还需要考虑模型接触的数据量、数值精度、优化器状态以及停止准则,而不能只看发生了多少次更新。

性能、并行性与分布式执行

迭代算法的成本既取决于重复次数,也取决于每次重复所需的工作量。如果 KK 次迭代中每次的成本均为 CC,则可以初步估算总成本为 KCKC。更一般地,总工作量为

∑k=0K−1Ck,\sum_{k=0}^{K-1}C_k,

因为随着搜索前沿扩大、候选集缩小或近似计算的要求提高,每次迭代的成本可能发生变化。计算复杂性研究这类成本如何随输入规模及其他相关参数的变化而变化。

仅凭语法上的嵌套结构,并不能确定渐近复杂度。反复将搜索区间减半,所需步数呈对数增长,二分查找就是如此。偶尔执行高成本操作的循环,仍可能具有较低的摊还成本。反过来,一条循环语句也可能调用某个过程,在内部完成大量不易察觉的工作。

编译器可以通过循环展开、向量化、循环融合、循环交换或其他优化手段来变换循环。循环展开能降低控制指令所占的相对比例,并使相互独立的操作显现出来。循环融合将多次遍历合并,在数据仍处于存储层次结构中较近的位置时加以复用,从而可能改善局部性。这些变换必须保留编程语言及其编译规则所要求的行为。

依赖关系决定了哪些迭代可以同时执行。如果每次迭代写入不同的输出元素,并且只读取保持不变的输入,那么各次迭代之间可能相互独立。像 xk+1=F(xk)x_{k+1}=F(x_k) 这样的递推关系,则明确依赖于前一个状态。求和等归约操作通常可以重组为树形结构,但浮点加法不满足结合律,因此并行归约与顺序归约可能产生不同的舍入结果。

并行计算往往是加速每一次数值迭代,而不是消除迭代的先后顺序。一次矩阵运算可以分配给多个处理器执行,随后进行同步,再开始下一次更新。其收益取决于算术运算的工作量是否足以抵消调度、通信和数据传输的成本。

在分布式计算中,同步会带来额外的约束。同步算法可能需要等待所有工作节点完成后才能继续推进。异步算法则可能使用有延迟的信息继续执行,在减少等待的同时,也改变了数学上的更新过程。其收敛性可能需要以延迟上限、更新频率和一致性等方面的假设为前提。

故障也会影响迭代状态。检查点可以保存参数、计数器、随机数生成器的状态以及辅助变量,以便恢复计算。只有在迭代产生的影响得到适当控制时,重新执行被中断的迭代才是安全的。写入外部记录或从账户扣款的更新操作,不能像纯粹的内部数值计算那样处理:恢复时必须区分从未执行的工作与已经执行但尚未得到确认的工作。

迭代式软件开发与反馈周期

在软件工程中,迭代也指开发活动反复进行的周期。团队实现或修改系统的一部分,评估结果,再根据评估所得确定后续工作。这里不断更新的状态不仅包括数值变量,还包括需求、设计、代码、测试,以及对用户需求的理解。

迭代式开发与增量式开发有所不同。增量是增加可用的功能;迭代则是重新审视或改进已有成果。项目可以兼用这两种方式:先交付一项小功能,对其进行评估,再在后续周期中加以修改。项目也可以采用增量方式,而不对先前的决策作实质性的重新审视;或者采用迭代方式,但并非每个周期都产出新的可部署功能。

历史上一些具有重要影响的方法,对这些周期采用了不同的组织方式。巴里·勃姆在1988年的一篇论文中介绍了螺旋模型,围绕对目标、备选方案、风险、工程工作和规划的反复考量来组织开发。该模型的核心在于以风险驱动活动,而不只是重复同一套固定步骤。Scrum 将工作组织为有时间限制的冲刺(Sprint);《Scrum 指南》2020年版规定,每个冲刺持续一个月或更短时间。这样的冲刺是一个管理和开发时段,并非算法中的执行次数。

反馈可以来自自动化测试、性能测量、安全分析、运行事故,或对实际使用情况的观察。这些证据回答的是不同的问题。通过回归测试,表明系统与某项明确规定的预期行为一致,却不能证明该需求有用。执行速度更快,也不能证明结果正确。反复修改能否提供有价值的信息,取决于评估能否揭示当前系统与其预期行为之间的相关差异。

版本控制记录接连发生的变更,并支持比较、回退与协作。自动化构建和测试系统对修订版本进行评估,而持续交付则通过频繁的集成与验证来组织软件开发,使软件始终具备发布条件。因此,一次开发迭代、一次构建、一次提交和一次生产环境发布是不同的事件,即使某个具体工作流程将它们紧密联系在一起。

开发中的迭代不具备某些数值方法所拥有的一般性收敛保证。需求可能发生变化,评估标准可能相互冲突,修改也可能引入新的缺陷。重复一个过程,并不能证明每次的结果都优于上一次。有意义的评估依赖于明确的目标和可观测的属性,例如按照规定的测量程序得到的缺陷率、在指定工作负载下的响应时间,或规定的验收测试是否完成。