文章插图
这样,只需要采用一个排序操作,即可根据权重进行打散处理 。
文章插图
可以看出,通过设置更重的权重系数,我们实现了优先打乱了字体颜色,色块信息因为系数较低,可以容忍他们有限度的相邻 。这种算法的优点为:
- 实现同样简单直接
- 综合考虑了不同因素的打散,可以通过调整权重系数,轻易调整对打散的倾向程度
- 通过对权重计算函数的修改,可以很轻松的融入别的考量,如想更尊重原排序,也可以将原序加入权重计算
- 【打散算法的三种解决方案及其选型场景】因为权重计算的累积效应,本算法仍然容易末尾失效
- 最后对整体排序,性能为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)
文章插图
可以看出,在一定数据范围内,滑动窗口法拥有极大的优势,但是性能与窗口大小也有极大关系,如果窗口范围过大,冲突就多,交换速度会极大下滑 。
综合来说,三种算法的适用场景如下:
- 如果平常使用的场景,单一维度打散的话,采用按列打散是完全可以的
- 如果追求性能且原排列分布已经较为稀疏了,选择小单位的滑动窗口更佳
- 如果要引入多维度,则权重分配法就必不可少了
选用实例当我们实际应用时,一般并不单纯使用其中任何一种,一定要明确需求,然后结合需求来分析,取三者的优势 。
本次,在解决闲鱼上马赫选品系统打散的需求时,了解到以下几个特征:
- 商品列表长度约为2000,用户获取一次消息时的对象条数有限,一般只有一两位数
- 打散的要求:既要分开同一用户发布的,也要分开同一类目的商品,并且前者优先于后者,最好系数还可以调整
- 用户id极多(每个用户都可能发布商品),而商品类目极为有限
推荐阅读
- 黑糖姜茶的四种做法,冰糖姜茶的做法
- PHP 2020经典面试题集
- 可乐茶叶蛋介绍,柠檬可乐生姜茶的做法
- HTTP长连接是啥?底层是如何工作的?Tomcat是如何实现长连接的?
- 何为茶事,香菜拌茶树菇的做法
- 如何科学地选择一台适合 Java 开发的电脑?
- Docker 的前世今生
- 如何选购iPad
- 隋炀帝杨广是不是昏君 隋炀帝杨广是怎么当上皇帝的
- 《酒狂》赏析 酒徒的小说