打散算法的三种解决方案及其选型场景( 二 )


文章插图
这样,只需要采用一个排序操作,即可根据权重进行打散处理 。

打散算法的三种解决方案及其选型场景

文章插图
可以看出,通过设置更重的权重系数,我们实现了优先打乱了字体颜色,色块信息因为系数较低,可以容忍他们有限度的相邻 。这种算法的优点为:
  1. 实现同样简单直接
  2. 综合考虑了不同因素的打散,可以通过调整权重系数,轻易调整对打散的倾向程度
  3. 通过对权重计算函数的修改,可以很轻松的融入别的考量,如想更尊重原排序,也可以将原序加入权重计算
缺点为:
  1. 【打散算法的三种解决方案及其选型场景】因为权重计算的累积效应,本算法仍然容易末尾失效
  2. 最后对整体排序,性能为O(n logn),相对有优化空间
 
窗口滑动法以上两种,都是在我们彻底考虑全局后产生的算法,复杂度计算中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(都是素数,方便排序)分别用于用户、类目的权重函数计算,将窗口内的限制条件改为,与所有其他对象的权重差小于一定阈值 。最终就可以实现多因素统计和性能的统一 。


推荐阅读