背景

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

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

問題定義

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

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

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

解決方案

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

按列打散法

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

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

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

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

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

缺點為：

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

同時也可以看出，這個算法對類目數(shù)量有著相當(dāng)?shù)囊蕾嚕绻惸孔銐蚣?xì)致，這個算法的缺點就可以被部分掩蓋，性能上，時間和空間消耗都是O(n)的

權(quán)重分配法

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

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

這樣，只需要采用一個排序操作，即可根據(jù)權(quán)重進(jìn)行打散處理。

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

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

缺點為：

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

窗口滑動法

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

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

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

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

綜合考量

根據(jù)前文的討論，我們對這幾種方法有如下的結(jié)論：

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

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

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

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

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

選用實例

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

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

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

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

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

總結(jié)

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