背景

打散是在推薦、廣告、搜索系統(tǒng)的結果基礎上，提升用戶視覺體驗的一種處理。主要方法是對結果進行一個呈現(xiàn)順序上的重排序，令相似品類的對象分散開，避免用戶疲勞。算法端傳出的推薦結果，往往具有以下幾個痛點：

• 相似品類的商品易扎堆。顯然的，如果商品的各特征相似，其獲得的推薦分數也容易相近，而滿目的同款肯定不是用戶期望的結果。
• 對用戶的偏好捕捉太強。用戶心理層面，對于隱私或者偏好被完美捕捉這件事是敏感的，過于精準的結果不但容易導致用戶的反感，也容易限制用戶潛力的轉化。
• 產生的錯誤容易被放大。對于幾乎沒有什么使用痕跡的用戶，很容易出現(xiàn)對僅有特征的放大，從而就容易產生錯誤推薦。
• 而打散算法，通過呈現(xiàn)順序的改變，將相似品類分開，緩沖了推薦系統(tǒng)和用戶的交互，提升了用戶體驗，是算法賦能落地的最后一步。

問題定義

首先，我們明確打散算法的定義。其輸入是算法端根據用戶偏好程度排列的有序列表，每個對象擁有一個或多個需要加以區(qū)分的屬性，輸出的要求是將相似屬性分散開后的一個列表。其中會涉及到這幾個細節(jié)：

• 打散程度。究竟是讓相同類目的盡可能分隔開，還是只要間隔一定距離就可以滿足要求?
• 打散依據的維度。是按照一種屬性分開就可以，還是存在多種需要考慮分開的因素?
• 打散的性能。作為經常調用的一種接口，性能的優(yōu)化當然是越多越好。

值得注意的是，我們并不希望丟失算法端系統(tǒng)帶來的用戶個性因素，所以如何在打散的基礎上，充分利用好原對象的順序，也是非常值得權衡的問題。

解決方案

從三個不同的維度，我們將討論三種比較通用的打散辦法。三種方法中，打散程度最徹底的，是按列打散法;能綜合多維度考慮的，是權重分配法;只需要局部計算來提高性能的，是滑動窗口法。

按列打散法

既然要避免相似屬性的內容在呈現(xiàn)時相鄰，很直接的思路是我們將不同屬性的裝在不同的桶里，每次要拿的時候盡量選擇不同的桶。這樣就可以實現(xiàn)將元素盡量打散。如下圖所示，在這個例子中，初始的列表是共有三類(藍、黃、紅)：

將他們按序裝到桶里(通常是HashMap)：

這個時候，我們把每個桶按列取出元素，即可以保證元素被最大程度打散，最終結果為

為了保證對原算法結果的保留，我們在取每一列時都有一次按原序排序的過程。這種算法的優(yōu)點為：

• 簡單直接，容易實現(xiàn)
• 打散效果好，雖然排序可能導致元素在列的開頭和結尾偶然相鄰，但是在末尾之前，最多相鄰元素為2，不影響體驗
• 性能比較穩(wěn)定，不易受輸入結構影響

缺點為：

• 末尾打散失效，容易出現(xiàn)扎堆
• 對原序的尊重性不算強，即使有推薦系數非常低的對象也強制出現(xiàn)在前面
• 只能考慮一種維度的分類，無法綜合考慮別的因素

同時也可以看出，這個算法對類目數量有著相當的依賴，如果類目足夠細致，這個算法的缺點就可以被部分掩蓋，性能上，時間和空間消耗都是O(n)的

權重分配法

當我們想綜合考慮多個因素時，無法很直觀的將每個商品直接分類，這個時候可以采用權重分配法。首先，我們對每個對象定義一個新的權重：

其中，W為人為為每個屬性分配的系數，代表著打散的優(yōu)先度，而Count則代表著該對象在此屬性的表現(xiàn)(相同屬性已經出現(xiàn)了多少次)。直觀的來說，相似屬性已經出現(xiàn)了越多次，權重值就會越大，并且在函數計算過程中，天然考慮了原本順序的因素，所以計算出權重后，無須其他處理，只需要按權重排序即可。以下圖為例，如果我們規(guī)定字體顏色權重系數為2，色塊顏色權重系數為1 那么，在1、2號，他們的字體顏色和色塊都沒出現(xiàn)過，則權重為0，到3號時，都出現(xiàn)過1次，則權重為 2 * 1 + 1 * 1 = 3，以此類推，8號時，其字體顏色出現(xiàn)過2次，色塊顏色出現(xiàn)過3次，則權重為 2 * 2 + 1 * 3 = 7

這樣，只需要采用一個排序操作，即可根據權重進行打散處理。

可以看出，通過設置更重的權重系數，我們實現(xiàn)了優(yōu)先打亂了字體顏色，色塊信息因為系數較低，可以容忍他們有限度的相鄰。這種算法的優(yōu)點為：

• 實現(xiàn)同樣簡單直接
• 綜合考慮了不同因素的打散，可以通過調整權重系數，輕易調整對打散的傾向程度
• 通過對權重計算函數的修改，可以很輕松的融入別的考量，如想更尊重原排序，也可以將原序加入權重計算

缺點為：

• 因為權重計算的累積效應，本算法仍然容易末尾失效
• 最后對整體排序，性能為O(n logn)，相對有優(yōu)化空間

窗口滑動法

以上兩種，都是在我們徹底考慮全局后產生的算法，復雜度計算中n的變量也是整個原序列大小，但是，實際場景中，用戶并不會一下看到整個序列，往往一次返回topN個，填滿用戶窗口就可以了。這個時候，我們應當發(fā)掘一種只參考局部的方法，基本思想就是滑動窗口。

如下圖所示，我們開啟一個size為3的窗口，以此來類比用戶的接收窗口，規(guī)定窗口內不能有元素重復，即模擬用戶看到的一個展示頁面沒有重復，如果窗口內發(fā)現(xiàn)重復元素，則往后探測一個合適的元素與當前元素交換。在第一步時，我們探測到2、3同類，于是將3拿出來，往后探測到4符合3處的要求，于是交換3、4，窗口往后滑動一格。第二步時，發(fā)現(xiàn)還存在窗口中2、3同類，再將3、5交換，窗口往后滑動一格，發(fā)現(xiàn)窗口內無沖突，再滑動一格。第三步時，發(fā)現(xiàn)5、6同類，將6、7交換，窗口滑動到最后，盡管還發(fā)現(xiàn)了7、8同類，但彼時已無可交換元素，便不作處理。

這種算法的優(yōu)點為只需要局部計算，不需要完全打散，適應了topN的需求;

而缺點也同樣明顯，其健壯性不佳，受序列分布的影響很大，同樣也避免不了末尾堆積的缺陷。

綜合考量

根據前文的討論，我們對這幾種方法有如下的結論：

其中，為了便于直觀的比較三種方法的性能表現(xiàn)，我們生成了完全隨機的十萬條數據，在筆記本環(huán)境下測試了在不同規(guī)模下三種算法的表現(xiàn)。其中橫坐標表示輸出數據的規(guī)模，縱坐標表示運行的時間(單位:ms)

可以看出，在一定數據范圍內，滑動窗口法擁有極大的優(yōu)勢，但是性能與窗口大小也有極大關系，如果窗口范圍過大，沖突就多，交換速度會極大下滑。

綜合來說，三種算法的適用場景如下：

• 如果平常使用的場景，單一維度打散的話，采用按列打散是完全可以的
• 如果追求性能且原排列分布已經較為稀疏了，選擇小單位的滑動窗口更佳
• 如果要引入多維度，則權重分配法就必不可少了

本文提出的所有算法性能都在O(n)、O(nlogn)的級別上，而且因為實際場景往往規(guī)模極小，所以并不會成為應用中的性能瓶頸，也為修改和權衡留下了很大的空間。之后，可以在全局與局部的調和、末尾堆積等方面，對這個問題更進一步討論。

選用實例

當我們實際應用時，一般并不單純使用其中任何一種，一定要明確需求，然后結合需求來分析，取三者的優(yōu)勢。

本次，在解決閑魚上馬赫選品系統(tǒng)打散的需求時，了解到以下幾個特征：

• 商品列表長度約為2000，用戶獲取一次消息時的對象條數有限，一般只有一兩位數
• 打散的要求：既要分開同一用戶發(fā)布的，也要分開同一類目的商品，并且前者優(yōu)先于后者，最好系數還可以調整
• 用戶id極多(每個用戶都可能發(fā)布商品)，而商品類目極為有限

那么，我們就可以有針對性的選擇自己的方案。從特征2可以看出，需要綜合多種因素，則需要選擇權重分配法;而為了解決性能問題，綜合特征一和特征三，一次獲取的消息很少，商品的類目也極為有限，決定選擇滑動窗口法。我們結合權重分配法和滑動窗口法，采用窗口大小為4的滑動窗口，然后采用權重系數13和7(都是素數，方便排序)分別用于用戶、類目的權重函數計算，將窗口內的限制條件改為，與所有其他對象的權重差小于一定閾值。最終就可以實現(xiàn)多因素統(tǒng)計和性能的統(tǒng)一。

略顯不足的是，這次參數的選擇(窗口大小、權重系數)并未經過多次反復的實驗比較，之后計劃在實際場景中，采用ABtest等方法，進行參數的優(yōu)化調整，使算法的性能表現(xiàn)更優(yōu)。

總結

本文討論了打散算法的幾種實現(xiàn)方式，從實現(xiàn)方法到優(yōu)缺點詳細進行了闡述，通過本文的方法，可以將特定類別的結果順序進行分散呈現(xiàn)，從而提升用戶的視覺體驗。我們可以看到，實際上打散的效果與尊重原算法的順序特征之間，存在著不可避免的一對矛盾。如何在實際復雜需求的條件中，更好的把握兩者的平衡，從而普適于更多的場景，是我們需要在未來持續(xù)去探索的;如何依靠技術的提升更好的提升用戶體驗，更是技術人永恒的命題。