写对代码的利器——“循环不变性”

本文来自我的大规模数据系统专栏《系统日知录》，专注存储、数据库、分布式系统、AI Infra 和计算机基础知识。欢迎订阅（长按下图识别二维码）支持，解锁更多文章。你的支持，是我前行的最大动力。

初学者在构建复杂代码时，往往会吃不准——我这样写对吗？本文就从”不变性“（invariants）的角度，给大家一些增加信心的”打开方式“。

如果大家看过算法导论，应该对这个词不陌生。粗略来说，在算法中，循环不变性（loop invariants）指的是在迭代三个关键环节（初始化、迭代中、结束时）上维持某种性质的不变。

以三种基本排序（冒泡排序、选择排序和插入排序）为例：

我们将整个数组分为两部分，前半部分有序，后半部分无序。则只要我们能够保持前半部分一直有序：

1. 初始化：只有一个元素，一定有序。
2. 迭代中：每次挪入一个新元素，仍然保持前半部分有序：
   1. 冒泡：每次从无序集合中冒出一个最小的值，放到有序集后面，则有序集一定仍然有序。
   2. 选择：每次从无序集合中选出一个最小的值，交换到有序集最后，则有序集仍然有序。
   3. 插入：每次将边界处的元素插入到有序集中合适的位置，保持其仍然有序。
3. 结束时：可得，有序集扩张到了整个数组，即我们排好序了。

通过在迭代的三个环节中保持有序集的一直有序，我们可以很有信心：我们最后得到的数组一定是有序的。聪明的你可能已经感觉到了，这不就是数学归纳法吗？对，只不过数学归纳法可以对任意规模进行归纳，而在算法迭代中，通常有个结束条件。

这其实有一种”拆解“的思想在里面。我们人脑通常很难记太多的上下文，所以通常会通过拆解的方法来降低所面临问题的复杂度。对于循环不变性来说，就是找到一种解决该问题的合适性质，然后通过在循环的三阶段中维持该性质，我们就不至于陷入海量的细节中去出不来。

排序算法相对比较简单，对其妙用可能还体会不深，下面就用一道 LeetCode 上稍微复杂一点的算法题：Sort Colors 为例来再次体会下循环不变性的运用。题目如下：

      给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，
使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

    

看到这里，如果有条件，可以先停下来，自己做下这道题，要求时间复杂度为 O(n)，空间复杂度为 O(1) 。

      void sortColors(vector<int>& nums) {
      int r = 0;           // [0, r) is red
      int b = nums.size(); // [b, nums.size()) is blue
      
      int i = 0;           // [r, i) is white, and [i, b) is unsorted
      while (i < b) {
          if (nums[i] == 0) { // red
              swap(nums[r++], nums[i++]);
              // r++, append the red to the red set, then expand the r
              // i++, we get a white from the former nums[r] which is white
              // then we should expand i
          } else if (nums[i] == 2) {
              swap(nums[--b], nums[i]);
              // we put an blue in the front of the blue set after expand
              // we get a unsorted one from the former nums[b], so i stays
          } else {
              ++i;
              // expand white set and shrink unsroted sort
          }
      }
  }

    

我们很容易想到多指针法，且最后不加注释的代码非常简单，寥寥数行。但是你会发现：

1. 初始化条件很难写对
2. 迭代时指针是否增减很难得当
3. 结束条件等于是否加也陷入纠结

我以前常用特殊 case 来确定上述三个点的写法，但是发现在这道题中失灵了，太多 case 要想了，老容易忘记一些点、按下葫芦浮起了瓢。

但如果，我们使用上面提到的循环不变性，使用指针将数组分为几个区间，且全部左闭右开，在这个：

      [0, red)：红色

[red, i)：白色
[i, blue)：未定

[blue, n)：蓝色

    

当然，这里用了一个技巧，将迭代指针 i 放到 red 和 blue 间，其实放到 blue 之后是最符合直觉的，但是在维持不变性时会增加很多交换。这技巧倒也符合直觉：将红色和蓝色往两边扔，中间自然剩下白色了。

找到了上述需要维持的”不变性“，我们在初始化、迭代维持和终止条件确定方面就非常”有法可依“了。可以看上面代码注释了解更多细节，这里就不赘述了。

除了循环不变性之外，我们在工程中其实也常用到不变性的思想，只是我们没有往这边去靠。

接口

接口通常包含一组操作集，这些操作集就定义了某种“性质”。而无论接口之下做何种实现，都要保证提供这些操作，这便是要维持“不变性”。有了这种不变性保证，所有接口的依赖方，就可以不必担心你如何实现，只需要面向接口进行编程即可。这给了我们将来进行“平替”的极大灵活性。

比如，使用 fuse 来实现一套用户态文件系统，不管底层如何实现（即使实现为分布式的），最终都可以 mount 到 linux 目录树中。

测试

测试通常包括一些用例集，这些用例集定义了我们代码需要满足的“行为”。如果测试用例覆盖足够完善，我们在进行代码重构时，即使进行了大幅度的修改，但只要保证测试都能跑过，我们就很有信心——我们的重构没有大问题。即，这些完善的测试集给我们的代码逻辑保证了逻辑上的“不变性”。

从某种程度上来说，测试从外部定义了我们系统的“边界”。

数据

众所周知，并发编程、分布式编程都很难写对。但如果我们能保证数据的“不变性”（当然，这里有点偷换概念了，英文中其实是 immutable）。就可以放心的对同一份数据进行反复读取、多次实验。

通过维持 “不变性”，可以让我们隔离复杂度——就像森林中的防火带，阻断火势蔓延。其实，这就是编程中抽象封装思想的另一个侧面。这些工程化的东西，本质上是为了适应人类的“认知方式”造出来的，让我们可以大规模的协作，来构建宏伟的建筑；让我们的知识可以代际累积，不断拓展科学的前沿。

题图故事