从报数游戏看计算机程序的可扩展性

关于可扩展性的定义，本着不重复造轮子的心态，见 yishuiliunian 的这篇文章。

报数游戏的典型形式是：从 1 开始报数，如果报到某个数以及其倍数（比如 3 及 3 的倍数）那么你报「过」或者其他什么词。这个游戏可以继续扩展，比如变成 3 和 5 的倍数报「过」、不报「过」而是报该数减去 7 的数等等。

我们先专注于基本款。逢 3 报过，写一个程序。这里（以及之后的一段时间内）我决定使用 JavaScript 因为 JavaScript 宇宙第一。我们默认入口函数是 main, 尽管其实 JS 没有入口函数这个说法，但是为了统一性我们就这么定义一下好了。

function main() {
  for (let i = 0; i < 20; i++) {
    if (i % 3 == 0) {
      console.log("过");
    } else {
      console.log(i);
    }
  }
}

输出的值为：

搞定。

如果现在我们要在 3 或 5 的倍数时报「过」呢？

那么我们就得把程序改成如下形式：

function main() {
  for (let i = 0; i < 20; i++) {
    if (i % 3 === 0 || i % 5 === 0) {
      console.log("过");
    } else {
      console.log(i);
    }
  }
}

目前看来还好。但是如果说逢 3 说「过」、逢 5 说「跳」、3 和 5 的倍数则说「giao」，又要怎么改呢？

这时候先骂一句产品经理又乱改需求，然后意识到现在我们需要把一些内容拆开了：

function main() {
  for (let i = 0; i < 20; i++) {
    if (i % 3 === 0 && i % 5 !== 0) {
      console.log("过");
    } else if (i % 5 === 0 && i % 3 !== 0) {
      console.log("跳");
    } else if (i % 3 === 0 && i % 5 === 0) {
      console.log("giao");
    } else {
      console.log(i);
    }
  }
}

这时候代码看起来已经显得十分冗长了。然后产品经理说：用户反馈说希望可以自定义两个数和应该报什么，以及我们的调研显示现在报数游戏会有 3 个数来增加难度，希望你能够跟进一下。哦对了，后面这个需求可能还会继续变更，请别再匿名骂我了谢谢。

这时候任何程序员都会开始预见到按照当前这个模式，这段代码会不断地膨胀、质量会不断下降、速度会不断变慢。我们判断 2 个数的时候，就需要 4 个分支，每个分支都判断 2 次，如果再加一个数，那么就需要变成 8 个分支，每个分支判断 3 次。分支数量基本上就是 \(2^n\), 判断次数则是 \(n\cdot{}2^n\). O(2^n) 的时间复杂度谁受得了啊！况且这还是判断本身，你还需要再乘以需要判断的数字数量。

这个问题怎么突然就 O(2^n) 了呢？这说明该代码不具有可扩展性。我们在上面的代码中引入了重复的判断、重复的代码块。

所以我们应该怎么解决这个问题呢？伪·素数筛么？

一个简单的方法就是先把问题分割成为小块，保存之前做的判断，然后再用在后面，而不是每次都单独判断一下：

function main() {
  let isMultipleOf3, isMultipleOf5;
  for (let i = 0; i < 20; i++) {
    isMultipleOf3 = i % 3 === 0;
    isMultipleOf5 = i % 5 === 0;
    if (isMultipleOf3 && !isMultipleOf5) {
      console.log("过");
    } else if (isMultipleOf5 && !isMultipleOf3) {
      console.log("跳");
    } else if (isMultipleOf3 && isMultipleOf5) {
      console.log("giao");
    } else {
      console.log(i);
    }
  }
}

我们虽然没削减分支数量，但是判断数量倒是削减了，现在代码中不会出现重复的判断了，算是一个小小的进步。但是要给这个代码添加新功能显然仍旧头疼，因为你需要更改变量名、更改数字、更改输出的文字，而且这些更改必须要能够及时反映在文档或者注释上，以及任何一个忘记更改的地方（虽然现在有重构工具使得这样的事情基本不会再发生）都会导致整个代码的崩溃。

那有没有更好的解决思路呢？更有经验的程序员会意识到，倍数和其对应的值其实是一个「配置」，它们是可以独立于核心逻辑的。报数游戏的核心逻辑是把数字根据一定的规则映射到字符串上，至于这个规则是什么，我们可以随时更改，但是核心逻辑——映射，是不会变化的。

现在我们把核心逻辑和规则分割开来，具体而言，写个函数：

function mapper(n) {
  let isMultipleOf3 = i % 3 === 0;
  let isMultipleOf5 = i % 5 === 0;
  if (isMultipleOf3 && !isMultipleOf5) {
    return "过";
  } else if (isMultipleOf5 && !isMultipleOf3) {
    return "跳";
  } else if (isMultipleOf3 && isMultipleOf5) {
    return "giao";
  } else {
    return ""+i;
  }
}

function main() {
  for (let i = 0; i < 20; i++) {
    console.log(mapper(i));
  }
}

看起来似乎并没有什么改进。但我们这样写使得我们可以专注于逻辑本身，至少让团队的其他人可以不把主函数搞乱。

现在我们考虑这样一个性质：当一个数既可以被 3 整除，又可以被 5 整除时，它必然可以被 15 整除。

那么，我们可以利用这个性质来进一步减少判断：

function mapper(n) {
  let out = "" + n;
  if (n % 3 === 0) {
    out = "过";
  }
  if (n % 5 === 0) {
    out = "跳";
  }
  if (n % 15 === 0) {
    out = "giao";
  }
  return out;
}

现在对于 n 个数，只需要判断 (2^n) - 1 次了。这是这个问题的（局部）最优情况了。

我们之前提到了规则是一个「配置」，是一个数据，我们能否真的把判断逻辑变成一个配置呢？毕竟我们现在想要的是这样的效果：

3 的倍数 -> "过"
5 的倍数 -> "跳"
15 的倍数 -> "giao"
其他 -> 数字本身

那么，借助 JavaScript 的平凡对象，我们可以修改映射函数，使其包含上面的映射关系：

function mapper(n) {
  const factors = [{in: 3, out: "过"}, {in: 5, out: "跳"}, {in: 15, out: "giao"}];
  let out = "" + n;
  factors.forEach(pair => out = n % pair.in ? out : pair.out);
  return out;
}

现在，我们已经将 factors 变成了配置。随着需求的进一步变化，这个配置可以增加数字、减少数字、改变映射值；可以从前端通过输入框传入或者从文件中读取。由于 JavaScript 的函数是一等公民，out 成员也可以是一个返回字符串的函数，我们届时还可以实现减 7 等更奇葩的操作。注意到当前的实现要求 factors 必须是严格增序的，这样才能实现 15 可以覆盖 3 和 5 的输出结果。要修正这一个问题，按照 in 成员排个序就行了。

那么，从现在看来，我们的程序似乎就没有问题了，对么？

如果哪一天我们需要支持 2 进制的报数呢？如果哪一天我们要支持 16 进制报数呢？任意进制呢？如果哪一天 1 + 1 = 3 了我们也要提供支持呢？如果……

我们可以继续对以上问题提供抽象，但是没有任何抽象是无代价的。抽象的代价一方面来自性能，函数调用、对象的成员访问、数组的遍历都需要更多时间，这可能比暴力堆一堆的 if 的性能更低；另一方面来自理解，任何抽象层都会屏蔽细节，也会同时创造知识壁垒，对于不熟悉这个设计方式的人，我们的映射函数会给他们带来更多的心智负担。如果我们无限制地增加抽象层的话，最终它会变成「企业级 FizzBuzz」这样荒诞的代码。

对了，如果你在准备面试，那么最后的那一段代码就是标准答案，请直接背下来，谢谢。如果你还在学校，那么培养自己的「未来洞察」能力很重要——在软件的世界里面，一切都可能会变，但一切又都会固定不变：你所学习的具体技术可能会随着时间流逝而过时、被抛弃，但是你所掌握的算法设计、软件架构的一般模式、更靠近数学的那一部分则会是永恒的，直到如量子计算机这种永远处在「下一个十年」的全新的计算架构广泛应用。

发表回复 取消回复

发表回复取消回复