在开始前,我们要先明确一些小细节:
好的,先别着急,在正式开始讨论随机之前,我们先看几个生活中的实际情景(这样才能保证你能更好的理解为什么这么做)
你是一名程序员,需要做音乐播放器的随机播放功能,你三下五除二给歌曲标好号,根据随机函数结果播放对应的歌曲
这不就大功告成(了吗?)
不久,你就收到了用户的投诉“为什么我一首歌连续听了3次?”“为什么连着好几首都是一个歌手的?”……这些问题的最后一句不约而同的都跟着一句“你这真是随机吗???”
你看到这些用户反馈满脸问号,总不能是随机算法的问题吧?我这妥妥的真?随机啊?
让我们看看现在的主流音乐播放器是怎么做随机播放算法的(部分细节来自QQ音乐总监刘彦彬)经过对用户的调研,他们发现了几点:
解决2的方法很容易想到,我们只需要把歌单随机打乱排序就可以避免一首歌重复播放了
解决3也并不困难,只需要排序时把同一歌手的岔开放就行(编程中一般叫洗牌算法)
解决1也只需要根据歌曲标签,优先播放轻音乐即可,当然,如果高端一点,用大数据筛选晚上听的人更多的歌优先播放倒是省去了打标签的麻烦
当然,具体的细节肯定还有很多,但就从这几条我们就可以管中窥豹,得出音乐播放器的随机播放完全不随机的结论了,但用户反馈却恰恰相反,大家都觉得“这才叫随机嘛!”
诡异的事情出现了
明明挂羊头卖狗肉的洗牌算法一点也不随机,却被人认为非常随机,而良心的使用随机算法的却被大骂不够随机,这究竟是怎么回事??
接下来让我们用小学就学过的统计与概率来从数学角度分析一下这个问题
假设你现在需要做一个随机点名程序,全班有56名同学
先来回答第一个问题,根据简单的概率知识来看,显然是56选1,连续几次就是几次方
哈,看起来很小哈,两次的概率就已经是小概率事件了,但是我们是不考虑这个人是谁的,所以我们要乘56
这么看的话,2次连续约1.785%的概率其实并不算高,而3次及以上就已经是小概率事件了
再来看看第二个问题,假设我们考虑两个人的顺序,那么是选第一次连续的2个人一捆,剩下55全排即可,这时分母是56全排,同时,因为第一次连续的有55组,此时数字变的非常恐怖
只有约1.785%的概率第二次排序不出现和第一次一样的连续
哈,这下有趣起来了,让我们看看三个人的情况
概率急剧减少,只有1.785%了,不难看出,四次及以上已经是小概率事件了
最后,我们再看看第三个问题,显然,每个同学被点到的概率是0.5,n次就是0.5的n次,不难得出:n≥7时,才变成小概率事件,而如果题目改成不点到这个人,答案也完全相同
经过上面可能非常不严谨的数学论证,我们最起码得到了一些理论支持,但是概率确实并不算高,如果我们按照通用的另一种小概率标准(0.05)来看的话,甚至1和2都属于小概率事件!但是,请让我们看看文章开头:在生活中我们常常会干这些事,听音乐,老师上课点名……在长期的使用中,这些情况发生至少一次的概率会随着时间变的很大,而正如“既视感”一样,这些事情但凡经历一次,我们的印象会变的非常深刻,认为这种随机是有迹可寻的,会错误的怀疑这种随机的真实性
因为有相当一部分人对随机的理解是:他出现过了,下次应该不会有他了!殊不知,根据条件概率,无论同一个人连续被点到多少次,他下次循环中被点到的概率都是0.5
当然,避免出现这种感受的方法就是用很多规则做出实际上完全不随机,但感觉上非常符合直觉中随机的方法,开头的音乐播放器就是一个很好的例子。关于点名器的优化问题,也可以用加权的方式解决(多次点到调低概率,多次未点到调高概率)有关这个问题,笔者也有所感触,举个真实的例子:
高中时被班主任安排做一个随机排座位的软件,心想“这还不简单?”遂写了个生成随机数表后按字典对应人名的程序,但用了几次很快收到反馈“上次我就和他同桌/前后/左右”“上次我就坐这”“你这到底是不是随机啊?”其中班主任的反馈最为离谱:“你这随机应该是每个人的前后左右的人和之前不一样,上次坐后排的人应该坐前排,上次坐前排的人应该坐后排,上次左边的人应该坐右边,上次右边的应该坐左边啊?你现在根本不是随机啊”
一下子给我整蒙了,回家冥思苦想绝妙的洗牌算法好几天,最后选择了猴子排序(笑)
简单来说,就是一直把随机的结果和上次座位结果作比较,如果不符合甲方超长的要求就舍弃这次随机,直到符合要求再输出,这种传说中时空复杂度最高的算法确实不负众望,第一次写完试运行就跑了整整大半个小时,舍弃了一百多万种排座位方式还没得到符合要求的结果,遂改变主意,把甲方的要求简化了一番,在保证看起来还挺随机的同时,每次只需要遍历十万种以内就可以输出符合条件的结果
本文地址:http://www.ksxb.net/quote/7538.html 海之东岸资讯 http://www.ksxb.net/ , 查看更多