采纳算法

大家好 非常高兴见到今天 到场的各位 我是 Dave 之后的 40 分钟 是关于理解 和致敬 驱动我们的 程序运行的东西

我们将会聊到一些实用的建议 但这并不是一个关于 技巧 技术 或者任何具体算法的演讲 尽管我们仍会有所涉及

这个演讲主要的内容是 揭示一些根本的东西 它的潜力 已经在你的代码中有所体现 我希望至少对于你们之中的一些人 这标志着与编程实践 建立新关系的开始

就个人而言 当我发现这种方法时 我的生活和事业的航向 就由此改变 这就是为什么 我如此关心软件库 但它也是 我所编写过的具体代码的 每一部分之中的可靠性 可维护性以及性能表现的来源

但在我们开始之前 请允许我向你们介绍 我的一个朋友

他就是 Crusty

Crusty 是一个传统派 他不相信调试工具 也不爱使用集成开发环境 没错 他喜欢那种 80 × 24 的纯文本终端窗口 非常感谢

现在 Crusty 对最新的编程潮流 持悲观态度 所以想把他拖到 21 世纪 有时会比较费力 他总是有不同的想法

但是如果你仔细听 你肯定会学到点东西 有时他会有一些 神奇的表达方式 比如“编程揭示本真” 甚至可以说 有点玄幻了 为了理解他 我发现一种方法很有帮助 那就是写代码

所以最近我在编写 一个叫做《Shapes》的小程序

我希望将它创造成 一个全能矢量绘图程序 但目前为止 它只能让你 在无限画布上排列形状

现在 我想与你们讲一个 关于删除选择指令的故事 因为我从实现这一功能的过程中 学习到了很多

我想我们可能都 经历过这个过程的一部分 作为程序员 我们要学会 如何从数组中删除东西 每一个人都会从 做这种事情开始

刚刚这个就是删除选择指令

我们从 0 开始循环计数 当我们发现要删除的东西 我们就调用 remove(at: )方法 然后我们就可以继续循环 直到 哦 溢出了

数组会变短 但是当循环开始时 我们选择了固定的迭代次数 幸运的是 如果你使用 Swift 并测试你的代码 你不可能遗漏这个 Bug 因为程序会产生内中断 但如果你像我一样 是 C 语言出身的程序员 面对这种问题 你可能没那么幸运 好的 我们可以通过将 for 循环替换为 更难看的 while 循环 来修复它 这可以使我们在每一次迭代中 检查计数 但这里也有一个细微的 Bug

如果两个连续的元素被选中 它将会删除第一个 并且立即 跳过下一个 这个 Bug 更加的阴险 因为它隐藏了起来 除非你的测试碰巧 试运行了它 但是如果我们足够幸运注意到了它 我们便可以继续 用一个 else 代码块 来保护自增语句 再次修复 这个实现 那么 我们完成了吗 我们有把握确定 这次是正确的吗

我认为我可以自证 它能够运行

不管怎样 经过这次的严峻的考验 我们收获了什么 当然 我们将这个 九行的代码套路 牢记在脑中 这样我们就可以在想要 删除什么的时候 把它调出来 现在 我确定你们中的许多人 正控制着自己 不向我大声喊叫 因为有一个 更加优雅的方式可以用 我仍然记得 自己发现了 这个技巧的那一天 因为一旦你发现了它 你就不用 再用那九行套路代码了 迭代限制以及 下一个要检查的项的索引 像传送带一样不断滚动 因为 remove(at: i) 改变了数组中 i 之后的部分

但是如果你从后往前检查 你只会迭代数组中 你还没有改变的部分

干得漂亮 对吗 这就是我一直 使用的模式 因为它简洁并且从不失败 直到几个月前 一天早晨 我刚吃完 我的牛油果吐司 并漫不经心地摆弄我的 App 当我尝试从一个非常复杂的画布中 删除差不多一半的图形时

我的 iPad 卡死了 将近 3 秒钟 所以 我喝了一口 装在竹质随行保温杯里的 三倍浓度半因拿铁咖啡压压惊 开始考虑我的对策

这令人十分不安 我的意思是 这是一个 非常简单的操作 我的代码如此简洁 怎么可能出错呢

性能分析结果告诉我 红点就在这 但是除了这个 我一点头绪都没有 然后 就在这时 Crusty 在我身后经过 拿着一罐从当地超市买的 准备作为日常饮品的 杂牌咖啡

“卡住了？” 他说 “是的” 我叹了口气 并向他解释情况 “那么 你有为此 看过文档吗？”

显然我没有 所以我呼出了 remove(at: ) 的 “Quick Help（快速帮助）” Crusty 靠近了一点 “你的问题就在这” 他说 并在我华丽的 视网膜显示屏上留下了一个指纹

我用一块手工制作的 意大利超细纤维布 小心地擦掉了指纹 这时 Crusty 说 “小子 它告诉你了什么” “唔” 我说 “它说 移除一个元素 需要使用大量的步骤 而且与数组的长度成正比” 这的确有些道理 因为数组需要将 之后所有的元素 放入它们的新位置

“那么 这对你的删除选择指令 又有什么意义呢” 他问道

“呃” 我说 就在这时他拿出 一包薄荷糖 然后排成线放在我的桌子上 “你自己试一试”

所以我走完一遍流程 试图回答他的问题 “嗯 既然删除选择指令 需要进行 O(n) 个步骤 每一步都对应每一个已选的元素 而且你可以选择最多 n 个元素 那么总步数将与 n 的二次方成正比”

Crusty 继续说 “那可是二次方 小子 无论你用丑陋的方式正着走 还是穿着花哨的 裤子倒着来” 我那时才意识到 对于我的 10 到 20 个元素的 小型测试案例 我们只需使用 几百个步骤 由于每一步都运行迅速 一切看起来棒极了

但是问题是 它的延展性不足 50 的二次方是 2500 100 的二次方更能达到 10000 如果你所做的所有测试 都在这个狭小范围之内 那你可能永远发现不了问题 但是延展性很重要 因为人们正在使用他们的手机和 iPad 处理越来越多的数据 我们也一直提供带有 更多存储空间的设备 帮助他们这么做

你们要关心这一点 因为对你们的用户而言 延展性意味着可预测性 所以 我理解了问题所在 但是我仍然不能确定 我应该怎么解决它 “现在我该怎么办？” 我问 Crusty

“你知道吗 小伙子” 他一边说 一边把一粒薄荷糖放到嘴里 “有一个解决这个问题的算法”

我和他说 “听着 Crusty 我是一个 App 开发者

你说过你不做面向对象的东西 同样 我也不做算法 你关注在算法类中的 数据结构 因为你知道 找工作的时候 你的面试官会考你 但在真正的编程世界 区分大神和菜鸟的关键 是将控制器 委托 以及响应程序 连接在一起 构建一个工作系统的能力” “豆包” 他说 我不知道为什么他这么称呼我 “计算机是做什么的”

“它们计算” “那么 你的代码中的计算 在哪里呢”

“好吧” 我回答 “我想在我的代码里 我看不见什么东西像个算法” 但是 Crusty 不这么认为 “哦 你的 App 里面可全都是算法” 他说 接着将一本破旧的字典 扔在我的桌子上 “翻翻看” 在我镇定下来后 我小心地将书移到一边 在聚焦搜索栏中输入 “define: Algorithm (定义：算法)” Crusty 认为这是个巧妙的技巧

嗯 在计算或其他解决问题的 运算中 要遵循的过程或规则集

好吧 细想一下 这听起来像大多数的代码 但是我仍不能确定

“你有做过长除法吗” Crusty 问道 “那就是一个算法”

我又开始将它打到聚焦搜索中 但是他突然说 “在纸上算” 不想让自己难堪 我把话题转回到 我的代码上

“嗯” 我问 “所以 这个可以解决 我的代码性能问题的 神奇的算法是什么呢”

“那么 如果你愿意 让我用一下你的打字机” 他说 “这个东西怎么用 哦 这是一个触控板 我会尽量不碰它 所以首先 你要删掉这些 愚蠢的代码

然后 shapes.removeAll (where: { $0.isSelected}) 嗯 试试合不合身” 然后 Crusty 离开了 去洗他的咖啡机的拉花缸 留下我去琢磨 我的代码里到底 发生了什么 首先 我检查过并且发现 性能问题确实解决了 太棒了

我不想再听一遍 Crusty 唠叨说看文档 所以我弹出 removeAll(where: ) 的 “Quick Help” 然后我发现它的复杂度 也与集合的长度 成正地变化 就像 removeAt 一样 但是由于我不必 把它放入循环中 那么它就变成了我整个 运算的复杂度

现在 我想让你们 直观地理解 这能带来什么不同 O(n) 表示算法运行的时间 与问题的大小 成线性关系 这个图是一条直线

然后 这个橙色线是 n 的二次方的形状

正如你所见 线性算法也许在小型问题中 表现稍差 但他最终比 二次方算法运行更快

很棒的是 不管你用线性算法 的成本有多高 如果你继续放更大的问题尺寸 你总是会找到 一个线性算法会赢 并且在后面 一直赢的点

所以 我们正在讨论的是 延展性 而不是绝对的性能

好了 我的延展性问题终于解决了 但我真的很想看看 标准程序库如何改进 我倒着来的删除方法

Crusty 提醒我说 Swift 是开放源码 所以我可以把它 放在他口中的“嬉皮士网”上 也就是我们其他人所知的 GitHub

现在 我注意到的第一件事 便是点注释 它是所有 “Quick Help” 的来源 描述了算法的功能以及复杂度 接下来 结果是 removeAll(where) 不是什么 常规的方法 它是一个通用的算法 这意味着 它可以在各种不同的集合上运行

这取决于很多因素 重新排列元素的能力 它来自于 MutableCollection 改变长度和结构的能力 它来自于 RangeReplaceableCollection 它是由一些其他的 O(n) 算法构成的 第一个是 halfStablePartition 它将所有 满足某些谓词的元素 移动到末尾 并告诉我们后缀从哪里开始

halfStable 正如其名 表明了 它保留了不移动的 元素的顺序 但是它也可以打乱 移动到最后的元素 有些时候 这不是很重要 因为第二个算法 removeSubrange() 无论如何也会 删除子区间

我们都见过这个 部分区间的标记吗 它是一种非常方便的 方式来编写扩展到 集合末尾的范围

好的 现在 removeSubrange 是 库全局 API 的一部分 因此你可以在网上找到它的文档 但是 halfStablePartition 是一个运行的细节 现在 我们不打算 一一介绍 但是这里有一些 值得注意的地方

首先 它一开始 调用另一个算法 firstIndex(where: ) 来查找属于后缀的 第一个元素的位置

接下来 它设置了一个循环变量 j 有一个循环 然后这个循环指数 j 在每次迭代中 会从前向后移动一位

所以 可以肯定的是 j 只对元素进行了一次传递 你几乎可以从这里看到 量级和复杂度 最后 由于该方法 需要重新排列元素 但不更改 集合的长度或结构 因此它只依赖于对 MutableCollection 的遵循 所以 这就是我学到的第一堂课

熟悉 Swift 标准库中的内容

它包含一组 提供文档描述 和性能特征的算法

虽然我们看了一点执行过程 你也可以从中学到很多东西 但由于它是设计好的 所以你不必用我之前的笨方法

官方文档会告诉你 需要知道的一切 以便有效地使用该库 你甚至可以在那找到 一个 Playground 教程

我知道 Swift 中有很多内容 所以它的确可能看起来很吓人 但是你不需要记住一切 知道那里有什么 以及如何找到它将 为你省下很多精力

现在 在我们继续之前 我想指出 当 Crusty 做出此更改时 在代码中发生的其他事情 这两个中哪一个最直接地 描述了它的意义 现在 我必须先通读 并思考第一个 才能知道它在做什么 嗯 也许我最好加个注释 好的 看起来怎么样 哦 即使有了评论 反向迭代仍旧有点棘手 而且我也不想 有人因为他们不理解而破坏 这个代码 所以我最好解释一下 好的 当我们一一澄清时 Crusty 改过的代码实际上更好理解 因为它有一个 尾随闭包语法 现在 让我们深呼吸 然后再看

哪一个更明显是正确的

即使带有这些评论 我仍然需要通读第一个 去明白它其实和第二个 做的是同样的事 但是效率更低

使用这个算法可以使代码 在各个方面都做得更好 所以 这是你的代码的 一个准则 也是一个目标 是由 Sean Parent 首先提出的

每当你编写一个循环时 就用对某个算法的调用 来替换它 如果你找不到对应的算法 就自己做一个算法 然后用这个算法来执行循环

实际上 现在对你来说 这似乎是不现实的 但是在谈话的最后 我希望它不再是这样

不过为了获得一点动力 回想一下上一次 你看到乱得像面条一样的代码的时候 是不是充满了循环

我打赌一定是 好吧 大功告成 我已经使代码 变得更短 更快 在各个方面都更好 我准备今天到此为止 “感谢你的帮助 Crusty” 我说 同时系上 我定制的皮革邮差包上的钛制钩环 但他怀疑地看着我 然后说 “你不认为你可能在别的地方 犯过那样的错误吗”

我叹了口气 把包放下 开始追踪我代码中的循环

然后我发现 在处理层级命令的 文件中 有很多 放到最前 放到最后 向前移动一层 也就是把选定的图形移到 前面的图形上

让我们来多做几次吧 向后移动 放在选定的图形下面 最后 在左边的图形列表中拖拽 现在 这些操作听起来非常简单 直到你意识到 它们都需要对多个选定的图形进行操作 这些图形在列表中 甚至可能都不是连续的

因此结果表明 在操作完成后 将所有选定的元素 放在一起 才是有意义的

所以 当你把图形向前移动时 你把选定的最前面的图形 放在紧邻它的图形前面 然后你把所有其他的图形 放在它后面

当你向后移动图形时 你把选定的最后面的图形 放在紧邻它的图形后面 然后把其他的图形 放在它前面

如果你没有完全跟上 不要担心 我们会回头再讲 但我只想说 我有一些精心设计的代码 来正确地处理所有这些细节 就足够了

例如 这是 bringToFront() 当我看到它时 我十分地确定 这些图形有一个 O(n) 的循环 还包含两个 O(n) 的运算 remove(at:) insert(at:) 这就产生了 没错 n 的二次方

事实上 同样的问题 出现在每一个 我其他的四个命令中

这里的所有执行 都对数组进行循环 执行插入和删除操作 这意味着它们都是二次的 现在 我有点气馁 所以我问 Crusty 他是否愿意和我一起看

他说 “我不能待太晚” 他说 “我今晚有一个 交际舞聚会 但是我想 我们还是抓紧继续吧” 我在 bringToFront() 这里停下来

Crusty 的第一个问题是

“它到底是做什么的”

“好吧” 我说 “这是个 while 循环 j 跟踪插入点 i 跟踪我们正在 查看的元素 “用语言 而不是用代码” Crusty 说“描述它”

“好吧 我们来看看 它将选定的图形移动到前面 保持它们的相对顺序” “把它写在点注释上 然后读给我听”

我是一个手速超快的打字员

“将选定的图形移动到前面 保持它们的相对顺序” “听起来熟悉吗” Crusty 说

就在那时我意识到 它很像 halfStablePartition 但它是完全稳定的 我开始激动起来 “你觉得这个叫什么” 我不得不猜 “stablePartition” “没错 我最喜欢的一个 你可以在这个 Swift 开源项目中 找到一个 执行文件” 因此 我把文件拖进了我的项目中 同时 Crusty 含糊地说 我们添加的注释 应该在一开始就写上 我开始编写代码

写了这么多 就又遇到了一个问题

你看 stablePartition 使用了一个谓词 它表示是否将元素 移动到集合的后缀中 所以 要把东西搬到后面 我需要执行 bringToFront()

我看向 Crusty

“脑补一下” 他说

于是 我闭上眼睛 看着那些未被选中的图形 聚集在后面 这就给了我答案 我猜 sendToBack 会更加简单 因为我们只需 反转谓词 我们将选定的图形 移动到后面 现在 我正准备执行 向前移动的命令 我想 Crusty 会和我一样 急于继续 考虑到他晚上的计划 但他阻止了我 “刹车 Snuffy

我不想错过开场探戈 但你不打算看看 它能不能延展尺寸吗”

他有道理 所以我弹出 stablePartition 的 “Quick Help” 然后看到它的复杂度 是 O(n log n) 为了有一个 O(n log n) 的概念 我们不妨看看 O(log n) 它从开始很快就进入 平稳状态 n 越大 它增长的越慢 越接近一个常数 所以当你乘 n 时 你所得到延展性图像 与 O(n) 的并不同 但是随着它的增长它 越来越接近线性

所以 O(n log n) 通常被认为 和 O(n) 差不多 我对此十分开心 所以我们继续处理 bringFoward() 现在 就像我们之前说过的 bringFoward() 将最前面选定的图形 向前移动一层 并将后面的其他 被选定的图形聚集起来

但是 Crusty 根本不喜欢 这种思考方法 “刚开始的时候 那个绕来绕去的东西 让那行代码 像是在跳狐步舞狐步舞” 他说 “你并不需要它” 当我茫然地看着他的时候 他又拿出了薄荷糖

用他五根灵活的手指 执行了 bringForward() 指令

“看到了吗” 他问

我感觉就像 明知道“赌徒三张”是一个陷阱 但我还是踩了进去 “看着熟悉吗”

“不”

他用手帕盖住了前几个

“现在呢” 就在这时我意识到 这就是另一个 stablePartition

好吧 我明白了 我想

如果我们找到选定的 最前面的图形 然后移动到它前面图形的位置 并隔离从那里开始的数组的部分 我们可以对它进行分区

“但是，你如何只修改 集合中的一部分呢” 我问 Crusty

“你难道没听说过切片吗” 他说 同时接管了键盘

“shapes

好了 把它放在你的算法里 然后进行变换” 我立即照做

因此 人类关于如何 正确有效地 计算事物的知识 要比计算机早几千年 至少可以追溯到古埃及 自从计算机发明以来 这一领域的工作 出现了爆炸式增长

如果标准库没有 你所需要的 那么你需要做的 可能是测试 阅读文档 通常更正后还要检查一下 要学会如何在网络上 搜索适用于 你的问题领域的研究

好的 回到代码上来 我对这个切片很感兴趣 当我检查它的类型时 我发现它不是一个数组 由于我们是在一个数组上 使用了 stablePartition bringToFront 以及 sendToBack 现在我们还在一个数组切片上使用它 所以我大胆猜测 它一定是通用的 “当然是 stablePartition 和特定的数组有什么关系”

“没错 没有联系 说到这 豆包 bringForward() 与图形和选择 又有什么关系呢”

“嗯” 我说 “它作用于图形 然后将选定的图形 移到前面” “没错 也没关系” 他听都没听便说道

“你能在一排薄荷糖上 执行向前移动吗

当然 你可以 所以 这和图形 没有关系”

嗯 “你是在建议我们让它 变得通用吗” 我问道 “难道它不早就是 通用的了吗” 用一个新问题回答了这个问题 Crusty 回答道 “唔 你打算怎样 测试这个方法”

“好的” 我说 “我会创造一个画布 我会添加一些随机的图形 我会选定它们中的一些 然后最终” 但我的话没有说完 因为我知道 这是个坏主意 如果我就这么做 我真的会测试我的功能吗 还是我会测试 画布和不同图形的初始化设定 addMethod() 方法 再或者测试 各种形状的 isSelected 属性是否 计算出来 我的确应该建立测试用例 但是理想情况下 那段代码不应取决于其他 我需要再测试的代码

如果我可以将薄荷糖向前移 那么我也应有可能 用 Playground 中的整数 做一些随机的事 就像这样 用 bringForward() 方法 把能被 3 整除的数提到前面来

现在 在频谱的另一端 我应该可以向它抛出 大量随机生成的测试数据 并确保算法的 可扩展性 只要代码与画布和图形 绑定在一起 这些事情就都不会简单

所以 我向 Crusty 承认他是对的 并开始把这个非通用的 bringForward() 变成通用的算法

第一步是将它 从画布中解耦出来 并将其移动到图形数组中

当然 这个数组就是 shapes 所以我必须用 self 把它替换掉 然后我通过传递一个谓词 将它从选择中解耦出来 该谓词指示是否应该将选定的图形 向前移动

一切都在正常编译着 太棒了 此时 我很高兴地发现 在 shapes 上没有依赖 我可以删除 where 子句了 非常好 我想 现在 我可以在任何数组中 执行 bringForward 了

我看了看 Crusty 他一直在角落里 安静地练习恰恰舞 但他似乎认为我还

没有结束

“bringForward() 和数组 有什么关系”他问 “好吧 的确没有” 我叹了口气 然后开始思考 如何移除这个依赖

让我们看看 这有一个 stablePartition() 需要遵循 MutableCollection 所以 也许我只需要将它移动到 MutableCollection 中 嗯 我想 显然索引类型 与 int 类型不匹配 好吧 这应该很好修复 对吧

你是这么做的吗

不要这么做

它编译好了 但是 Crusty 突然停止了跳舞 我知道有些不对劲 “什么” 我说 “菜鸟总是这样做” Crusty 边摇着头边说

“首先 你让它与 0 的比较 这对于数组切片来说是错误的 所以 你知道数组切片 它们的索引不是 从 0 开始的吗 所有切片的索引 从它们被切片的 底层集合中的 相应索引开始 这种关系十分关键 如果你想要用切片 组成通用算法 所以它真的很重要”

好吧 我知道要修正这个问题 只需将它与开始索引 进行比较

但是真正的问题是 “bringForward() 与拥有整数索引 有什么关系” 我打断了他 “是的 我知道” “我必须在 i 之前 得到索引 我可以用减法获得”

Crusty 只是叹了口气 然后又将薄荷糖拿了出来

然后 他把两个手指 放在桌子上 像小人一样走啊走 直到右手指向 第一块绿色的薄荷糖 “整支舞中都没有 向后的舞步” 他说 之后我意识到 Crusty 刚刚向我展示了一个新的算法

“我们叫它 indexBeforeFirst 吧”

“现在 这里的诀窍是 保持注意力集中 假设有人已经为你写了它” 然后他把我们不需要的 代码都删掉了 像这样 这样

“predecessor 就是第一个 在谓词被满足之前的元素 前面的索引

现在 快来看看这读起来 多么动人”

如果你看到了这个代码 你就会发现他是对的

删除所有无关的细节 包括图形 选择 数据以及整数 给我留下更清晰的代码 因为它只处理 问题的本质 “我已经向你展示了 indexBeforeFirst 是如何工作的 试一试你能不能写出来” 他说 所以 我想我现在开始 跟得上他了 因为我第一次做对了 我说过 我是个手速超快的打字员 好吧 所以 返回第一个 successor 与谓词匹配的索引 我非常兴奋地看到 这进展得有多么顺利

“好吧 Crusty” 我说 “让我们做下一个”

“你难道没有忘记什么事吗 豆包” 他问道 我不知道 他在说什么 代码很简洁 而且运行正常

“语义 小子 我怎么能从其他代码中使用它们 如果我不知道 它们是什么意思呢” 于是我意识到 每一次我们使用新的算法 我们都依靠他的文档 得出关于 我们自己代码的 意义和效率的结论

因为大多数算法都是 由其他算法构建的 所以它们依赖于相同的东西 最近 我正在面试一位 未来的实习生并且问他 关于文档的作用 他以一个我不会忘记的 短语开始 “哦 它实在太重要了” 他说

“我们正在构建这些抽象的塔” 我在向你们复述他的话 “我们之所以能够成功构建 而无需经常检查 下面层级的内容 是因为我们构建的部分 是有文档记录的” 现在 作为一名 App 开发者 你正在一个塔尖上工作 这个塔贯穿了 你的系统框架 DOS 一直延伸到硬件 这是基于物理定律的

但是一旦你调用了 你自己的方法 它就成为你的基础的一部分 所以 请为你的代码写文档 顺便说一下 那位实习生被录用了

他就坐在那里 所以 我接受了提示 并把 Crusty 的新算法写入了文档 这意味着 我们可以忘记 它如何实现 并使用它 因为我们知道 “Quick Help” 拥有我们所需要的一切

现在 我也记录了 bringForward

酷

现在 因为它似乎 解决了我所有的问题 在这时 我真的很好奇 想看看在 stablePartition 里 发生了什么

结果是我得到了很好的回报 因为这是一个非常漂亮 而且有指导意义的算法

这个公共的方法 获取集合计数 并将其传递给这个 helper 方法 该 helper 方法使用“分而治之”的策略

首先 它会处理基本情况 当计数小于 2 时 我们便结束了 我们只需要弄清楚 分区点是在 集合的开始处 或者在集合的末尾 接下来 我们将集合 分成两部分

现在 在这一点上 你必须暂时相信 算法是有效的 因为我们要用 stablePartition() 处理 左半边和右半边 现在 如果你看一下这两端 你会发现 所有东西都在正确的位置 但是这个中心区段 有两个部分 需要交换

现在 它们不会总是 和在这个例子中一样长 幸运的是 “有一个算法可以使用” 我们叫它 rotate() 好的

我不打算在这里深入讨论 rotate 算法 但是它真的很漂亮 如果你感兴趣 你可以在与 stablePartition 同样的文件中 找到它的实现方法 好的

回到图形

现在 这个烂摊子实现了 在图形列表中拖放 这一直是我最复杂 和 Bug 最多的运算之一

我的策略是 分配临时缓冲区

然后在插入点之前 对 shapes 进行循环 提取选定的图形 并调整插入点 然后在不调整插入点的情况下 分别对其余的图形 进行循环 提取选定的图形 最后 重新插入它们

老实说 我有点害怕触碰代码 因为我觉得我终于做对了 距离我最后一次发现新 Bug 已经差不多有 一个星期了 但是我现在已经在这个过程中 做得很好了 所以我试着把操作可视化一次完成 嘿 看起来很熟悉 让我们再看看 嗯

假设我们先做这个 然后分别处理 各个部分

没错 这就是两个 带有反转谓词的 stablePartition 所以 这个通用的算法 被压缩到了这两行 而这是 Canvas 上剩下的 现在 让我们把它放在 旧代码旁边看看

还不错 但是我们得到了 一个可重复使用的 高效文档化的通用算法 这是非常棒的 好的 这是一种需要习得的技能 审视特定于你的 App 领域的细节 了解你的代码从根本上在做什么 并在可重复使用的通用代码中 捕获这些细节 这需要实践

但是 为什么要那么麻烦呢 实践得到的答案是 因为它们是从无关的细节中 解耦出来的 通用的算法更加 可重复使用 经得起考验 甚至比对应的非通用代码 更加简洁 但我也认为 对于任何真正喜欢编程的人来说 这都是非常有益的

它是对真与美的追求 而不是抽象的 不可触及的真理 因为实际硬件的约束 让你保持诚实

就像 Crusty 常说的 “编程揭示本真” 因此 将你的计算视为 具有类型 和 App 体系结构的 具有权利和义务的 VIP 标识它 给它一个名字 对它进行单元测试 并记录它的语义和性能 最后 我想把 Sean Parent 的建议 包括上下文引用一下 作为结束语 “如果你想要提高 组织中的代码质量 请将所有的代码标准 替换为一个目标 不要单独写循环”

谢谢大家 [ 掌声 ]