背景

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

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

問(wèn)題定義

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

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

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

解決方案

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

按列打散法

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

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

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

為了保證對(duì)原算法結(jié)果的保留，我們?cè)谌∶恳涣袝r(shí)都有一次按原序排序的過(guò)程。這種算法的優(yōu)點(diǎn)為：

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

缺點(diǎn)為：

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

同時(shí)也可以看出，這個(gè)算法對(duì)類(lèi)目數(shù)量有著相當(dāng)?shù)囊蕾?lài)，如果類(lèi)目足夠細(xì)致，這個(gè)算法的缺點(diǎn)就可以被部分掩蓋，性能上，時(shí)間和空間消耗都是O(n)的

權(quán)重分配法

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

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

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

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

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

缺點(diǎn)為：

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

窗口滑動(dòng)法

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

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

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

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

綜合考量

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

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

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

綜合來(lái)說(shuō)，三種算法的適用場(chǎng)景如下：

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

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

選用實(shí)例

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

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

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

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

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

總結(jié)

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