Knuth高效洗牌算法的示例分析

Knuth高效洗牌算法的示例分析,相信很多没有经验的人对此束手无策,为此本文总结了问题出现的原因和解决方法,通过这篇文章希望你能解决这个问题。

成都创新互联专业成都网站建设、网站制作,集网站策划、网站设计、网站制作于一体,网站seo、网站优化、网站营销、软文营销等专业人才根据搜索规律编程设计,让网站在运行后,在搜索中有好的表现,专业设计制作为您带来效益的网站!让网站建设为您创造效益。

Knuth高效洗牌算法的示例分析

今天在做一个游戏需求的时候碰到一个问题,问题很简单,给定75个球,编号1-75,需要保证初始化的时候位置是随机的。

显然,我们可以初始化一个数组A,把75个数放进去,然后做一个shuffle函数随机交换其中的元素,这样就是随机的。

我准备这样做一个shuffle,但同时也想看看golang里面是否有这样的接口直接得到结果,看了下还真有,这个函数是rand.Perm(n),这个函数会返回一个数组,比如我传入75,会返回一个0-74的随机数组。

arr := rand.Perm(75)
 

好奇心驱使我一探究竟,golang会用什么样的方式实现Perm函数呢?

打开golang的源代码,在rand.go文件中找到这个函数:

Knuth高效洗牌算法的示例分析  

实现很简单,然而初一看有点懵,因为没有用到shuffle,而是一次遍历就把事情给解决了,到底是怎么回事?

仔细分析发现,这个算法非常精巧,每次遍历都是将当前的数i和已经在数组中的随机一个数m[j]进行交换,最终达到了公平随机整个数组的作用。虽然只有短短3行代码,却让人有种震撼的感觉。

顿时觉得golang很NB,确实很高效。

上面这段代码写了4行的注释,大概意思是说不能省去0那一次,看起来没啥用处,但是为了照顾r随机器中的随机序列,还是要加上,不然可能会造成负作用,这里面和随机种子以及此后随机的序列有关,为了对随机序列不产生影响保证公平性,不能省略0。

网上搜索了一下高效洗牌算法,又发现python里面也有这样的函数,这样写的:

for(int i = N - 1; i >= 0 ; i -- )
    swap(arr[i], arr[rand(0, i)])         // rand(0, i) 生成 [0, i] 之间的随机整数
 

而这个算法的出处竟然来自于TAOCP!算法就是大名鼎鼎的 Knuth-Shuffle,即 Knuth 洗牌算法。

看似简单的问题,竟然又扯出Knuth,大意了。

能把一件小事情做到极致的人,可以称之为艺术家。Knuth名副其实。

最后以 Knuth 的一句话共勉:

A programmer who subconsciously views himself as an artist will enjoy what he does and will do it better.

看完上述内容,你们掌握Knuth高效洗牌算法的示例分析的方法了吗?如果还想学到更多技能或想了解更多相关内容,欢迎关注创新互联行业资讯频道,感谢各位的阅读!


网页名称:Knuth高效洗牌算法的示例分析
文章转载:http://pwwzsj.com/article/ppoocc.html