java – 以下用于改组数组的算法之间有什么区别吗?
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了java – 以下用于改组数组的算法之间有什么区别吗?,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1413字,纯文字阅读大概需要3分钟。
内容图文
![java – 以下用于改组数组的算法之间有什么区别吗?](/upload/InfoBanner/zyjiaocheng/750/5130b79f0d65449a9ce69f3fabcb2747.jpg)
参见英文答案 > why does this simple shuffle algorithm produce biased results? what is a simple reason? 12个
我的Java教科书说你可以使用以下代码随机洗牌任何给定的数组:
for(int i = myList.length-1; i >=0; i--)
{
int j = (int)( Math.random() * (i+1) );
double temp = myList[i];
myList[i] = myList[j];
myList[j] = temp;
}
我写的以下代码是否同样有效或有效?
for(int i = 0; i < myList.length; i++)
{
int j = (int)( Math.random() * (myList.length) );
double temp = myList[i];
myList[i] = myList[j];
myList[j] = temp;
}
我测试了我的代码,它确实正确地改变了元素.有没有理由在这一个上使用教科书的算法?
解决方法:
是的,它们实际上是不同的.
第一种算法是经典Knuth Shuffle的变体.
对于这个算法,我们可以证明(例如,通过归纳),如果我们的随机数生成器(Math.random())是理想的,它将生成n中的每一个! (n阶乘)可能的排列具有相同的概率.
第二种算法没有此属性.
例如,当n = 3时,有33 = 27个可能的结果,并且不会均匀地除以3! = 6,可能的排列数.
实际上,这里是结果的概率(生成统计数据的程序:1 2):
[0, 1, 2] 4/27
[0, 2, 1] 5/27
[1, 0, 2] 5/27
[1, 2, 0] 5/27
[2, 0, 1] 4/27
[2, 1, 0] 4/27
对于n = 4,结果更加不均匀,例如(生成统计的程序:3 4):
[1, 0, 3, 2] has probability 15/256
[3, 0, 1, 2] has probability 8/256
你可以想象,如果你的排列应该是随机的,那么这是一个不受欢迎的属性.
最后,我们通常使用伪随机数生成器而不是真正的随机源的事实不会使上述任何一个无效.
我们的随机数发生器的缺陷,如果有的话,显然无法在后一步修复损坏 – 如果我们选择非均匀算法,即.
内容总结
以上是互联网集市为您收集整理的java – 以下用于改组数组的算法之间有什么区别吗?全部内容,希望文章能够帮你解决java – 以下用于改组数组的算法之间有什么区别吗?所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。