?????♀? 編者按：本文作者是螞蟻集團前端工程師亦池，介紹了語雀圖冊功能背后的更整齊的瀑布流算法，還有一段和 chatGPT 糾纏的故事 ??，一起來看看～

????? 介紹一下圖冊

先來看看我們語雀年前上線的圖冊功能：

歡迎大家使用圖冊更好的展示自己的圖片，秀秀最近的攝影作品、po 一下最近的好吃的好玩的、曬幾張靚照～?

目前圖冊只是上了一個基礎(chǔ)的初版，還有很多地方在體驗和產(chǎn)品設(shè)計上也會繼續(xù)優(yōu)化，包括針對單張圖的刪除、排序，圖冊的尺寸調(diào)整，更快捷的把各種來源的圖片放進圖冊里，大家有一些想法也歡迎提建議～

??開發(fā)故事

?? 瀑布流能不能再整齊一些

瀑布流是一個不新鮮的布局方式了，看到這個我第一反應自然是使用社區(qū)的開源庫按需裁剪一下用起來。剛發(fā)布時也是這么上線的。扒過代碼參考的開源庫有：

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

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

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

但第一版本其實回發(fā)生下圖左側(cè)尷尬的情況：肉眼可見我們要的是上圖右側(cè)的效果。

常見瀑布流算法的問題

原因：社區(qū)主流的瀑布流計算思路都是將已知高度的圖片（實現(xiàn)上可以是圖片加載完成后獲取高度觸發(fā)重新布局）分發(fā)了列容器里，每列記錄實時高度，對于每一張新來的圖片分發(fā)規(guī)則是放入最短的那一列。專業(yè)點說是貪心算法的思想。

所以當最后一張是長圖時就會對布局的齊平性導致很大的沖擊。（當然這不是說社區(qū)的方案都 low，開源產(chǎn)品可能更多考慮了普適情況，譬如可能無法提前知道所有圖片尺寸信息，全部加載完再重新布局一次又給用戶帶來干擾，甚至是懶加載場景更不好優(yōu)雅的展示處理。）

在語雀編輯器場景，我們對于要布局的那批圖片是能拿到寬高信息的，完全可以對所有圖片整體考慮，計算一個最優(yōu)結(jié)果再渲染，可以做到不被最后一張長圖影響整體。

一開始我覺得這是個單純的算法問題，可以抽象成將一個數(shù)字數(shù)組拆分成 n 個數(shù)組，使每個數(shù)組的數(shù)字和盡量接近，我覺得應該是有一種經(jīng)典算法來解決這類問題的，譬如動態(tài)規(guī)劃、背包問題之類的。

這么經(jīng)典的問題不如問 chatGPT 吧，此處插入一段和 chatGPT 糾纏的故事。結(jié)論是它沒給我找到靠譜答案。感興趣的可以展開后面章節(jié)的折疊塊看看這個讓人哭笑不得的過程 ??。

???♀? 分析一下

chatGPT 沒能給我正確答案，我又是個基礎(chǔ)算法的渣渣，想先找個方向再進去研究怎么實現(xiàn)，于是請教了一下一個酷愛刷算法題的師妹，得到的方向是：“這是個負載均衡類型問題，具有 NP hard 復雜度，無法獲得最佳解，只能求近似最優(yōu)解，用動態(tài)規(guī)劃的思想是沒錯的”。

啥是 NP hard 復雜度，可以看后面的【基礎(chǔ)知識】章節(jié)的科普。我也不清楚怎么證明這真的是一個 NP hard 復雜度的問題，但基礎(chǔ)知識告訴我這類復雜度的問題往往復雜度是階乘級別的，就是不是我們常見的 O(n)、O(logn)、O(n^2) 這種經(jīng)典算法的復雜度，他們的復雜度叫做有多項式解。階乘級別意味著暴力窮舉，這往往是計算機無法接受的時間，也毫無算法可言。

咱這個問題，求解最優(yōu)解時，每一張圖片的擺放都影響著后面圖片的位置，每張圖之間都有關(guān)聯(lián)，想想似乎確實只有窮舉才能真正的找到最優(yōu)解。加上對師妹算法水平的信任，我開始把問題縮減到動態(tài)規(guī)劃領(lǐng)域。

那就拆解子問題，先計算子問題的近似最優(yōu)解。

???♀? 解決方案

核心思想：

1. 計算平均值，讓每一組的和盡量接近均值，最終每組和的差異才會最小

2. 將原數(shù)組 arr 從大到小排序，降低分組時便利查找的復雜度

3. 遍歷原數(shù)組 arr，從目標的 n 個分組的第一組開始裝數(shù)據(jù)，直到它接近均值停止。這里注意接近的意思不是 <=avg，而是在均值臨界點，加上一個值 num1 < avg 后，和均值的差值是 delta，往前遍歷找(意味著 num2 > num1) 第一個沒被分組的數(shù)據(jù) num2 放入當前組后，num2 - avg < delta，如果是的則裝 num2，否則裝 num1。確保裝的是最接近均值的數(shù)。

4. 對于最后一個分組 n-1 要裝數(shù)據(jù)時，需要確保 arr 的每一個數(shù)據(jù)都被分配完，并且各組結(jié)果最小，所以最后一組的策略不參考平均值，而是按和最小的分組去塞 arr 里的每一個數(shù)據(jù)。

另外注意，對于已經(jīng)分好組的數(shù)據(jù)打個標，以免被重復分組。

這里我們是在拆解子問題

• 把復雜的分組后每組方差最小的問題，轉(zhuǎn)化為讓每組和最接近平均值的問題，將整體的問題拆解成了 n 個組的問題

• n 個組塞值時，又是一個找數(shù)據(jù)使它最接近均值的子問題

其中為了降低復雜度不搞遍歷的最優(yōu)，確實只做到了近似最優(yōu)解。譬如放值前先做了排序，只要當前數(shù)據(jù)放進去 < avg都先無腦放，就會出現(xiàn)，譬如剩下的數(shù)據(jù)有[48, 25, 25], 均值是 50，本來我們可以放[25,25]得到最接近均值的數(shù)據(jù)，但現(xiàn)在只放入了 48。

?? 圖片場景的特殊考慮因子

當我把一個純數(shù)學解放入瀑布流場景時，發(fā)現(xiàn)事情并沒有這么簡單，算法的最優(yōu)還是要為圖片展示場景效果的最優(yōu)做一些讓步。

參差感

譬如你看這個是最優(yōu)解么？

因為我們先做了排序，并且按排序的數(shù)據(jù)順序做分配，所以長圖它它它它都跑到同一列去了。

這個視覺上沒有了參差美可受不了。

于是在接近最優(yōu)的做法上妥協(xié)一步。先把排序前 n 的數(shù)據(jù)挨個放到 n 組，讓個高的先均勻分布。

結(jié)合保留用戶本來的順序，是不是舒服一些：

這里依舊不是最佳效果，因為只取了前 n個，試想我們?nèi)绻?3 組，5 個長圖，還是有一組全是長圖。但長與短的邊界實在無法敲定，除非再搞個每張圖片高度的均值，大于均值一定閾值的數(shù)據(jù)先均勻分布到n組，但這種操作的數(shù)據(jù)越多，越影響到底部整體的平齊效果。所以還是只選了和組數(shù)相同的前n張這么處理。我估摸著大多數(shù)用戶在文檔里的圖片是個輔助，不會搞出特別大數(shù)量級還夾雜很多長短分明的圖。當前能保持一定數(shù)量級 (<10）展示上不會有太大問題。

排序

盡量得保證用戶原圖的順序，所以需要記錄原圖的順序，然后在分組完成后：

1. 每列里按原圖順序重排下順序

2. 列與列之間按第一個圖的順序重排下順序

能做到盡量接近原順序但不絕對。

純數(shù)字上[[25], [25], [25,25]]和[[25,25], [25], [25]]的分組沒有差別。但是圖片場景又不一樣了：

這排列總透著一股奇怪于是再讓步犧牲一下復雜度：

裝最后一組數(shù)據(jù)分配余數(shù)之前，先把分配好的分組，先排序，組與組的和相等時優(yōu)先放入排前面的數(shù)組。

當前版本優(yōu)缺點

目前至少是在最平齊和圖片參差感之間謀求的一個較優(yōu)解，但絕不是最優(yōu)解，理論上此類問題不窮舉遍歷獲得不了最優(yōu)解。但我們可以通過優(yōu)化局部策略，使它更靠近最優(yōu)解。不過一定是優(yōu)于貪心算法把每張圖放入高度最小列的做法。這里如果有深入研究過瀑布流的小伙伴有更優(yōu)的方案，歡迎提供，讓語雀的瀑布流更整齊～

做事情咱也不能只說好的，對問題緘口不言，目前的問題有：

• 前面也說過，如果大量圖片，并且存在 分組張數(shù)n 的與其他圖片長度拉開巨大差距的圖片，排版還是不夠有參差感

• 先按大小排序，后分組，會對原圖順序造成偏差，很難復原嚴格的行列順序，但用戶還是能一定程度的干預排序，只是無法滿足一定要求圖A和圖B不放入同一列這種訴求。從這個角度說，順序上不如貪心算法方案更接近原順序，貪心方案的最后一張長圖問題其實可以通過主動拖拽順序把長圖放到前面來解決掉，但是這對用戶的理解力要求太高了。

anyway，以下的數(shù)據(jù)哪個算法也無法救 ??。目前列數(shù)是根據(jù)展示區(qū)寬度彈性計算的，這種想優(yōu)雅可能要觸發(fā)列數(shù)的改變規(guī)則了。

chatGPT 的插曲

第 1 輪

一開始它給了我個貪心算法的不是最優(yōu)解，得讓它進階

第 2 輪

看上去很高深，但這測試數(shù)據(jù)結(jié)果不對啊。我換個說法？是不是不能理解什么叫數(shù)字加和盡量接近

第 3 輪

結(jié)果不對，繼續(xù)讓他換個解法

第 4 輪

還是肉眼可見的不對，雖然我肉眼分的也不是最優(yōu)解，最后我的算法告訴我是可以分成三組和都是 80 的：[80], [32, 32, 12, 3, 1], [30, 21, 20, 9]

那么問題在哪呢，我嘗試問了它一個很簡單的問題：

原來加和都求不對，我放棄它了。。。

綜上：chatGPT 能高效省事讓你偷懶，但前提是你得能區(qū)分出它的答案靠不靠譜，如果你都不知道真相的問題仍給他，就會被忽悠了也不知道。另外別想用它幫你寫筆試題了，它只根據(jù)語義生成，但并不真的運行代碼，給的代碼和結(jié)果可能完全不匹配。

?? 基礎(chǔ)知識

資料：

• P 問題、NP 問題、NP 完全問題和 NP 難問題：https://zhuanlan.zhihu.com/p/73953567

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

• 動態(tài)規(guī)劃入門：https://www.diguage.com/post/dynamic-programming/

• 五大基本算法之動態(tài)規(guī)劃算法 DP dynamic programming：https://houbb.github.io/2020/01/23/data-struct-learn-07-base-dp

• 看一遍就理解：動態(tài)規(guī)劃詳解：https://juejin.cn/post/6951922898638471181

復雜度被分為兩種級別：一種是O(1),O(log(n)),O(n^a)等，我們把它叫做多項式級的復雜度，因為它的規(guī)模 n 出現(xiàn)在底數(shù)的位置；另一種是O(a^n)和O(n!)型復雜度，它是非多項式級的，其復雜度計算機往往不能承受

P 問題：如果一個問題可以找到一個能在多項式的時間里解決它的算法，那么這個問題就屬于 P 問題?NP 問題：NP 問題不是非 P 類問題。NP 問題是指可以在多項式的時間里驗證一個解的問題。NP 問題的另一個定義是，可以在多項式的時間里猜出一個解的問題?NPC 問題：同時滿足下面兩個條件的問題就是 NPC 問題。首先，它得是一個 NP 問題；然后，所有的 NP 問題都可以約化到它。NPC 問題目前沒有多項式的有效算法，只能用指數(shù)級甚至階乘級復雜度的搜索。NP-Hard 問題：它滿足 NPC 問題定義的第二條但不一定要滿足第一條。NP-Hard 問題同樣難以找到多項式的算法，但它不列入我們的研究范圍，因為它不一定是 NP 問題。即使 NPC 問題發(fā)現(xiàn)了多項式級的算法，NP-Hard 問題有可能仍然無法得到多項式級的算法

約化：(Reducibility，有的資料上叫“歸約”)。簡單地說，一個問題 A 可以約化為問題 B 的含義即是，可以用問題 B 的解法解決問題 A，或者說，問題 A 可以“變成”問題 B。通過對某些問題的不斷約化，我們能夠不斷尋找復雜度更高，但應用范圍更廣的算法來代替復雜度雖然低，但只能用于很小的一類問題的算法。

??next：拼圖

接下來我們還會上線更靈活的拼圖能力。拼圖算法可以實現(xiàn)任何尺寸的圖片，保持原比例不裁剪，用戶任意擺放位置，最終繪制成整齊的矩形，這個算法實現(xiàn)也遠比瀑布流復雜。

譬如你可以這樣：

也可以拖成這樣：

還可以拖成這樣：

甚至拖成這樣：

等等等等...... 隨意組合排序，最終都能整齊。?

等上線后我再寫寫拼圖的故事～