关于可扩展性的定义,本着不重复造轮子的心态,见 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);
}
}
}
输出的值为:
1
2
过
4
5
过
7
8
过
10
11
过
13
14
过
16
17
过
19
20
搞定。
如果现在我们要在 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」这样荒诞的代码。
对了,如果你在准备面试,那么最后的那一段代码就是标准答案,请直接背下来,谢谢。如果你还在学校,那么培养自己的「未来洞察」能力很重要——在软件的世界里面,一切都可能会变,但一切又都会固定不变:你所学习的具体技术可能会随着时间流逝而过时、被抛弃,但是你所掌握的算法设计、软件架构的一般模式、更靠近数学的那一部分则会是永恒的,直到如量子计算机这种永远处在「下一个十年」的全新的计算架构广泛应用。
Your comments will be submitted to a human moderator and will only be shown publicly after approval. The moderator reserves the full right to not approve any comment without reason. Please be civil.