简介： 打散算法优缺点及选型场景
作者：闲鱼技术 - 华采
背景
打散是在举荐、广告、搜寻零碎的后果根底上，晋升用户视觉体验的一种解决。次要办法是对后果进行一个出现程序上的重排序，令类似品类的对象扩散开，防止用户疲劳。
算法端传出的举荐后果，往往具备以下几个痛点：
1、类似品类的商品易扎堆。显然的，如果商品的各特色类似，其取得的举荐分数也容易相近，而满目标同款必定不是用户冀望的后果。
2、对用户的偏好捕获太强。用户心理层面，对于隐衷或者偏好被完满捕获这件事是敏感的，过于精准的后果岂但容易导致用户的恶感，也容易限度用户后劲的转化。
3、产生的谬误容易被放大。对于简直没有什么应用痕迹的用户，很容易呈现对仅有特色的放大，从而就容易产生谬误举荐。
而打散算法，通过出现程序的扭转，将类似品类离开，缓冲了举荐零碎和用户的交互，晋升了用户体验，是算法赋能落地的最初一步。
问题定义
首先，咱们明确打散算法的定义。其输出是算法端依据用户偏好水平排列的有序列表，每个对象领有一个或多个须要加以辨别的属性，输入的要求是将类似属性扩散开后的一个列表。
其中会波及到这几个细节：
1、打散水平。到底是让雷同类目标尽可能分隔开，还是只有距离肯定间隔就能够满足要求？
2、打散根据的维度。是依照一种属性离开就能够，还是存在多种须要思考离开的因素？
3、打散的性能。作为常常调用的一种接口，性能的优化当然是越多越好
值得注意的是，咱们并不心愿失落算法端系统带来的用户共性因素，所以如何在打散的根底上，充分利用好原对象的程序，也是十分值得衡量的问题。
解决方案
从三个不同的维度，咱们将探讨三种比拟通用的打散方法。
三种办法中，打散水平最彻底的，是按列打散法；能综合多维度思考的，是权重调配法；只须要部分计算来进步性能的，是滑动窗口法。
1）按列打散法
既然要防止类似属性的内容在出现时相邻，很间接的思路是咱们将不同属性的装在不同的桶里，每次要拿的时候尽量抉择不同的桶。这样就能够实现将元素尽量打散。
如下图所示，在这个例子中，初始的列表是共有三类（蓝、黄、红）：
将他们按序装到桶里（通常是 HashMap）：
这个时候，咱们把每个桶按列取出元素，即能够保障元素被最大水平打散，最终后果为
为了保障对原算法后果的保留，咱们在取每一列时都有一次按原序排序的过程。
这种算法的长处为：
1、简略间接，容易实现
2、打散成果好 ，尽管排序可能导致元素在列的结尾和结尾偶尔相邻，然而在开端之前，最多相邻元素为 2，不影响体验
3、性能比较稳定，不易受输出构造影响
毛病为：
1、开端打散生效，容易呈现扎堆
2、对原序的尊重性不算强，即便有举荐系数非常低的对象也强制呈现在后面
3、只能思考一种维度的分类，无奈综合思考别的因素
同时也能够看出，这个算法对类目数量有着相当的依赖，如果类目足够粗疏，这个算法的毛病就能够被局部覆盖，性能上，工夫和空间耗费都是 O(n)的
2）权重调配法
当咱们想综合思考多个因素时，无奈很直观的将每个商品间接分类，这个时候能够采纳权重调配法。
首先，咱们对每个对象定义一个新的权重：
其中，W 为人为为每个属性调配的系数，代表着打散的优先度，而 Count 则代表着该对象在此属性的体现（雷同属性曾经呈现了多少次）。直观的来说，类似属性曾经呈现了越屡次，权重值就会越大，并且在函数计算过程中，人造思考了本来程序的因素，所以计算出权重后，毋庸其余解决，只须要按权重排序即可。
以下图为例，如果咱们规定字体色彩权重系数为 2，色块色彩权重系数为 1
那么，在 1、2 号，他们的字体色彩和色块都没呈现过，则权重为 0，到 3 号时，都呈现过 1 次，则权重为 2 1 + 1 1 = 3，以此类推，8 号时，其字体色彩呈现过 2 次，色块色彩呈现过 3 次，则权重为 2 2 + 1 3 = 7
这样，只须要采纳一个排序操作，即可依据权重进行打散解决。
能够看出，通过设置更重的权重系数，咱们实现了优先打乱了字体色彩，色块信息因为系数较低，能够容忍他们有限度的相邻。
这种算法的长处为：
1、实现同样简略间接
2、综合思考了不同因素的打散 ，能够通过调整权重系数，轻易调整对打散的偏向水平
3、通过对权重计算函数的批改，能够很轻松的融入别的考量，如想更尊重原排序，也能够将原序退出权重计算
毛病为：
1、因为权重计算的累积效应，本算法依然容易开端生效
2、最初对整体排序，性能为 O(n logn)，绝对有优化空间
3）窗口滑动法
以上两种，都是在咱们彻底思考全局后产生的算法，复杂度计算中 n 的变量也是整个原序列大小，然而，理论场景中，用户并不会一下看到整个序列，往往一次返回 topN 个，填满用户窗口就能够了。
这个时候，咱们该当挖掘一种只参考部分的办法，根本思维就是滑动窗口。
如下图所示，咱们开启一个 size 为 3 的窗口，以此来类比用户的接管窗口，规定窗口内不能有元素反复，即模仿用户看到的一个展现页面没有反复，如果窗口内发现反复元素，则往后探测一个适合的元素与以后元素替换。
在第一步时，咱们探测到 2、3 同类，于是将 3 拿进去，往后探测到 4 合乎 3 处的要求，于是替换 3、4，窗口往后滑动一格。
第二步时，发现还存在窗口中 2、3 同类，再将 3、5 替换，窗口往后滑动一格，发现窗口内无抵触，再滑动一格。
第三步时，发现 5、6 同类，将 6、7 替换，窗口滑动到最初，只管还发现了 7、8 同类，但彼时已无可替换元素，便不作解决。
这种算法的长处为 只须要部分计算，不须要齐全打散，适应了 topN 的需要；而毛病也同样显著，其健壮性不佳，受序列散布的影响很大，同样也防止不了开端沉积的缺点。
综合考量
依据前文的探讨，咱们对这几种办法有如下的论断：
打散水平
是否能联合多维度
性能体现
按列打散法
高
否
中
权重调配法
中
能
中
窗口滑动法
低
否
高
其中，为了便于直观的比拟三种办法的性能体现，咱们生成了齐全随机的十万条数据，在笔记本环境下测试了在不同规模下三种算法的体现。其中横坐标示意输入数据的规模，纵坐标示意运行的工夫（单位:ms）
能够看出，在肯定数据范畴内，滑动窗口法领有极大的劣势，然而性能与窗口大小也有极大关系，如果窗口范畴过大，抵触就多，替换速度会极大下滑。
综合来说，三种算法的实用场景如下：
- 如果平时应用的场景，繁多维度打散的话，采纳按列打散是齐全能够的
- 如果谋求性能且原排列散布曾经较为稠密了，抉择小单位的滑动窗口更佳
- 如果要引入多维度，则权重调配法就必不可少了
本文提出的所有算法性能都在 O(n)、O(nlogn)的级别上，而且因为理论场景往往规模极小，所以并不会成为利用中的性能瓶颈，也为批改和衡量留下了很大的空间。之后，能够在全局与部分的和谐、开端沉积等方面，对这个问题更进一步探讨。
选用实例
当咱们理论利用时，个别并不单纯应用其中任何一种，肯定要明确需要，而后联合需要来剖析，取三者的劣势。
本次，在解决闲鱼上马赫选品零碎打散的需要时，理解到以下几个特色：
1、商品列表长度约为 2000，用户获取一次音讯时的对象条数无限，个别只有一两位数
2、打散的要求：既要离开同一用户公布的，也要离开同一类目标商品，并且前者优先于后者，最好系数还能够调整
3、用户 id 极多（每个用户都可能公布商品），而商品类目极为无限
那么，咱们就能够有针对性的抉择本人的计划。
从特色 2 能够看出，须要综合多种因素，则须要抉择权重调配法；而为了解决性能问题，综合特色一和特色三，一次获取的音讯很少，商品的类目也极为无限，决定抉择滑动窗口法。
咱们联合权重调配法和滑动窗口法，采纳窗口大小为 4 的滑动窗口，而后采纳权重系数 13 和 7（都是素数，不便排序）别离用于用户、类目标权重函数计算，将窗口内的限度条件改为，与所有其余对象的权重差小于肯定阈值。最终就能够实现多因素统计和性能的对立。
略显有余的是，这次参数的抉择（窗口大小、权重系数）并未通过屡次重复的试验比拟，之后打算在理论场景中，采纳 ABtest 等办法，进行参数的优化调整，使算法的性能体现更优。
总结
本文探讨了打散算法的几种实现形式，从实现办法到优缺点具体进行了论述，通过本文的办法，能够将特定类别的后果程序进行扩散出现，从而晋升用户的视觉体验。
咱们能够看到，实际上打散的成果与尊重原算法的程序特色之间，存在着不可避免地一对矛盾。如何在理论简单需要的条件中，更好的把握两者的均衡，从而普适于更多的场景，是咱们须要在将来继续去摸索的；如何依附技术的晋升更好的晋升用户体验，更是技术人永恒的命题。