🙋🏻‍♀️ 编者按：本文作者是蚂蚁集团前端工程师亦池，介绍了语雀图册功能背后的更整齐的瀑布流算法，还有一段和 chatGPT 纠缠的故事 🤪，一起来看看～

  🏞️ 介绍一下图册

先来看看我们语雀年前上线的图册功能：

欢迎大家使用图册更好的展示自己的图片，秀秀最近的摄影作品、po 一下最近的好吃的好玩的、晒几张靓照～ 

目前图册只是上了一个基础的初版，还有很多地方在体验和产品设计上也会继续优化，包括针对单张图的删除、排序，图册的尺寸调整，更快捷的把各种来源的图片放进图册里，大家有一些想法也欢迎提建议～

  开发故事

🧐 瀑布流能不能再整齐一些

瀑布流是一个不新鲜的布局方式了，看到这个我第一反应自然是使用社区的开源库按需裁剪一下用起来。刚发布时也是这么上线的。扒过代码参考的开源库有：

• https://github.com/bigbite/macy.js

• https://github.com/desandro/masonry

• https://github.com/xudafeng/autoresponsive-react

但第一版本其实回发生下图左侧尴尬的情况：肉眼可见我们要的是上图右侧的效果。

常见瀑布流算法的问题

原因：社区主流的瀑布流计算思路都是将已知高度的图片（实现上可以是图片加载完成后获取高度触发重新布局）分发了列容器里，每列记录实时高度，对于每一张新来的图片分发规则是放入最短的那一列。专业点说是贪心算法的思想。

所以当最后一张是长图时就会对布局的齐平性导致很大的冲击。（当然这不是说社区的方案都 low，开源产品可能更多考虑了普适情况，譬如可能无法提前知道所有图片尺寸信息，全部加载完再重新布局一次又给用户带来干扰，甚至是懒加载场景更不好优雅的展示处理。）

在语雀编辑器场景，我们对于要布局的那批图片是能拿到宽高信息的，完全可以对所有图片整体考虑，计算一个最优结果再渲染，可以做到不被最后一张长图影响整体。

一开始我觉得这是个单纯的算法问题，可以抽象成将一个数字数组拆分成 n 个数组，使每个数组的数字和尽量接近，我觉得应该是有一种经典算法来解决这类问题的，譬如动态规划、背包问题之类的。

这么经典的问题不如问 chatGPT 吧，此处插入一段和 chatGPT 纠缠的故事。结论是它没给我找到靠谱答案。感兴趣的可以展开后面章节的折叠块看看这个让人哭笑不得的过程 🙄。

💁‍♀️ 分析一下

chatGPT 没能给我正确答案，我又是个基础算法的渣渣，想先找个方向再进去研究怎么实现，于是请教了一下一个酷爱刷算法题的师妹，得到的方向是：“这是个负载均衡类型问题，具有 NP hard 复杂度，无法获得最佳解，只能求近似最优解，用动态规划的思想是没错的”。

啥是 NP hard 复杂度，可以看后面的【基础知识】章节的科普。我也不清楚怎么证明这真的是一个 NP hard 复杂度的问题，但基础知识告诉我这类复杂度的问题往往复杂度是阶乘级别的，就是不是我们常见的 O(n)、O(logn)、O(n^2) 这种经典算法的复杂度，他们的复杂度叫做有多项式解。阶乘级别意味着暴力穷举，这往往是计算机无法接受的时间，也毫无算法可言。

咱这个问题，求解最优解时，每一张图片的摆放都影响着后面图片的位置，每张图之间都有关联，想想似乎确实只有穷举才能真正的找到最优解。加上对师妹算法水平的信任，我开始把问题缩减到动态规划领域。

那就拆解子问题，先计算子问题的近似最优解。

🏄‍♀️ 解决方案

核心思想：

1. 计算平均值，让每一组的和尽量接近均值，最终每组和的差异才会最小

2. 将原数组 arr 从大到小排序，降低分组时便利查找的复杂度

3. 遍历原数组 arr，从目标的 n 个分组的第一组开始装数据，直到它接近均值停止。这里注意接近的意思不是 <=avg，而是在均值临界点，加上一个值 num1 < avg 后，和均值的差值是 delta，往前遍历找(意味着 num2 > num1) 第一个没被分组的数据 num2 放入当前组后，num2 - avg < delta，如果是的则装 num2，否则装 num1。确保装的是最接近均值的数。

4. 对于最后一个分组 n-1 要装数据时，需要确保 arr 的每一个数据都被分配完，并且各组结果最小，所以最后一组的策略不参考平均值，而是按和最小的分组去塞 arr 里的每一个数据。

另外注意，对于已经分好组的数据打个标，以免被重复分组。

这里我们是在拆解子问题

• 把复杂的分组后每组方差最小的问题，转化为让每组和最接近平均值的问题，将整体的问题拆解成了 n 个组的问题

• n 个组塞值时，又是一个找数据使它最接近均值的子问题

其中为了降低复杂度不搞遍历的最优，确实只做到了近似最优解。譬如放值前先做了排序，只要当前数据放进去 < avg都先无脑放，就会出现，譬如剩下的数据有[48, 25, 25], 均值是 50，本来我们可以放[25,25]得到最接近均值的数据，但现在只放入了 48。

🤪 图片场景的特殊考虑因子

当我把一个纯数学解放入瀑布流场景时，发现事情并没有这么简单，算法的最优还是要为图片展示场景效果的最优做一些让步。

参差感

譬如你看这个是最优解么？

因为我们先做了排序，并且按排序的数据顺序做分配，所以长图它它它它都跑到同一列去了。

这个视觉上没有了参差美可受不了。

于是在接近最优的做法上妥协一步。先把排序前 n 的数据挨个放到 n 组，让个高的先均匀分布。

结合保留用户本来的顺序，是不是舒服一些：

这里依旧不是最佳效果，因为只取了前 n个，试想我们如果是 3 组，5 个长图，还是有一组全是长图。但长与短的边界实在无法敲定，除非再搞个每张图片高度的均值，大于均值一定阈值的数据先均匀分布到n组，但这种操作的数据越多，越影响到底部整体的平齐效果。所以还是只选了和组数相同的前n张这么处理。我估摸着大多数用户在文档里的图片是个辅助，不会搞出特别大数量级还夹杂很多长短分明的图。当前能保持一定数量级 (<10）展示上不会有太大问题。

排序

尽量得保证用户原图的顺序，所以需要记录原图的顺序，然后在分组完成后：

1. 每列里按原图顺序重排下顺序

2. 列与列之间按第一个图的顺序重排下顺序

能做到尽量接近原顺序但不绝对。

纯数字上[[25], [25], [25,25]]和[[25,25], [25], [25]]的分组没有差别。但是图片场景又不一样了：

这排列总透着一股奇怪于是再让步牺牲一下复杂度：

装最后一组数据分配余数之前，先把分配好的分组，先排序，组与组的和相等时优先放入排前面的数组。

当前版本优缺点

目前至少是在最平齐和图片参差感之间谋求的一个较优解，但绝不是最优解，理论上此类问题不穷举遍历获得不了最优解。但我们可以通过优化局部策略，使它更靠近最优解。不过一定是优于贪心算法把每张图放入高度最小列的做法。这里如果有深入研究过瀑布流的小伙伴有更优的方案，欢迎提供，让语雀的瀑布流更整齐～

做事情咱也不能只说好的，对问题缄口不言，目前的问题有：

• 前面也说过，如果大量图片，并且存在 分组张数n 的与其他图片长度拉开巨大差距的图片，排版还是不够有参差感

• 先按大小排序，后分组，会对原图顺序造成偏差，很难复原严格的行列顺序，但用户还是能一定程度的干预排序，只是无法满足一定要求图A和图B不放入同一列这种诉求。从这个角度说，顺序上不如贪心算法方案更接近原顺序，贪心方案的最后一张长图问题其实可以通过主动拖拽顺序把长图放到前面来解决掉，但是这对用户的理解力要求太高了。

anyway，以下的数据哪个算法也无法救 🥲。目前列数是根据展示区宽度弹性计算的，这种想优雅可能要触发列数的改变规则了。

chatGPT 的插曲

第 1 轮

一开始它给了我个贪心算法的不是最优解，得让它进阶

第 2 轮

看上去很高深，但这测试数据结果不对啊。我换个说法？是不是不能理解什么叫数字加和尽量接近

第 3 轮

结果不对，继续让他换个解法

第 4 轮

还是肉眼可见的不对，虽然我肉眼分的也不是最优解，最后我的算法告诉我是可以分成三组和都是 80 的：[80], [32, 32, 12, 3, 1], [30, 21, 20, 9]

那么问题在哪呢，我尝试问了它一个很简单的问题：

原来加和都求不对，我放弃它了。。。

综上：chatGPT 能高效省事让你偷懒，但前提是你得能区分出它的答案靠不靠谱，如果你都不知道真相的问题仍给他，就会被忽悠了也不知道。另外别想用它帮你写笔试题了，它只根据语义生成，但并不真的运行代码，给的代码和结果可能完全不匹配。

📔 基础知识

资料：

• P 问题、NP 问题、NP 完全问题和 NP 难问题：https://zhuanlan.zhihu.com/p/73953567

• 什么是 P 问题、NP 问题和 NPC 问题｜Matrix67: The Aha Moments：http://www.matrix67.com/blog/archives/105

• 动态规划入门：https://www.diguage.com/post/dynamic-programming/

• 五大基本算法之动态规划算法 DP dynamic programming：https://houbb.github.io/2020/01/23/data-struct-learn-07-base-dp

• 看一遍就理解：动态规划详解：https://juejin.cn/post/6951922898638471181

复杂度被分为两种级别：一种是O(1),O(log(n)),O(n^a)等，我们把它叫做多项式级的复杂度，因为它的规模 n 出现在底数的位置；另一种是O(a^n)和O(n!)型复杂度，它是非多项式级的，其复杂度计算机往往不能承受

P 问题：如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于 P 问题 NP 问题：NP 问题不是非 P 类问题。NP 问题是指可以在多项式的时间里验证一个解的问题。NP 问题的另一个定义是，可以在多项式的时间里猜出一个解的问题 NPC 问题：同时满足下面两个条件的问题就是 NPC 问题。首先，它得是一个 NP 问题；然后，所有的 NP 问题都可以约化到它。NPC 问题目前没有多项式的有效算法，只能用指数级甚至阶乘级复杂度的搜索。NP-Hard 问题：它满足 NPC 问题定义的第二条但不一定要满足第一条。NP-Hard 问题同样难以找到多项式的算法，但它不列入我们的研究范围，因为它不一定是 NP 问题。即使 NPC 问题发现了多项式级的算法，NP-Hard 问题有可能仍然无法得到多项式级的算法

约化：(Reducibility，有的资料上叫“归约”)。简单地说，一个问题 A 可以约化为问题 B 的含义即是，可以用问题 B 的解法解决问题 A，或者说，问题 A 可以“变成”问题 B。通过对某些问题的不断约化，我们能够不断寻找复杂度更高，但应用范围更广的算法来代替复杂度虽然低，但只能用于很小的一类问题的算法。

  next：拼图

接下来我们还会上线更灵活的拼图能力。拼图算法可以实现任何尺寸的图片，保持原比例不裁剪，用户任意摆放位置，最终绘制成整齐的矩形，这个算法实现也远比瀑布流复杂。

譬如你可以这样：

也可以拖成这样：

还可以拖成这样：

甚至拖成这样：

等等等等...... 随意组合排序，最终都能整齐。 

等上线后我再写写拼图的故事～