A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 聂益飞 高级黑马   /  2013-1-2 14:45  /  2019 人查看  /  3 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 niexiaolu 于 2013-1-2 17:23 编辑

最近突然想了解shuffle方法的底层实现方式!进而了解计算机对所谓的“随机”是怎么做的!意思就是计算机是怎么随机获取数,或是角标的!由于手边没有API文档,无法查看shuffle方法的源码!还望各位同学指教指教!!

3 个回复

倒序浏览
本帖最后由 刘文超 于 2013-1-2 15:39 编辑

一般计算机的随机数都是“伪随机数”,以一个随机种子作为初始条件,然后用一定的算法不停迭代产生随机数。 随机种子可以是当前的系统时间,又叫真随机数
而shuffle只是应用了random而已,比较简单,很好理解:
这个是shuffle的主要思想
  1. To shuffle an array a of n elements (indices 0..n-1):  
  2.   for i from n − 1 downto 1 do  
  3.        j ← random integer with 0 ≤ j ≤ i  
  4.        exchange a[j] and a[i]
复制代码
就是说逆序遍历一个数组(集合),每一个元素 i 都与 “它之前那些元素(0~ i)中随机的一个元素” 进行互换
这是JDK源代码
  1. /**
  2.      * Moves every element of the List to a random new position in the list.
  3.      *  
  4.      * @param list
  5.      *            the List to shuffle
  6.      *  
  7.      * @throws UnsupportedOperationException
  8.      *             when replacing an element in the List is not supported
  9.      */  
  10.     public static void shuffle(List<?> list) {  
  11.         shuffle(list, new Random());  
  12.     }  
  13.   
  14.     /**
  15.      * Moves every element of the List to a random new position in the list
  16.      * using the specified random number generator.
  17.      *  
  18.      * @param list
  19.      *            the List to shuffle
  20.      * @param random
  21.      *            the random number generator
  22.      *  
  23.      * @throws UnsupportedOperationException
  24.      *             when replacing an element in the List is not supported
  25.      */  
  26.     @SuppressWarnings("unchecked")  
  27.     public static void shuffle(List<?> list, Random random) {  
  28.         if (!(list instanceof RandomAccess)) {  
  29.             Object[] array = list.toArray();  
  30.             for (int i = array.length - 1; i > 0; i--) {  
  31.                 int index = random.nextInt(i + 1);  
  32.                 if (index < 0) {  
  33.                     index = -index;  
  34.                 }  
  35.                 Object temp = array[i];  
  36.                 array[i] = array[index];  
  37.                 array[index] = temp;  
  38.             }  
  39.   
  40.             int i = 0;  
  41.             ListIterator<Object> it = (ListIterator<Object>) list  
  42.                     .listIterator();  
  43.             while (it.hasNext()) {  
  44.                 it.next();  
  45.                 it.set(array[i++]);  
  46.             }  
  47.         } else {  
  48.             List<Object> rawList = (List<Object>) list;  
  49.             for (int i = rawList.size() - 1; i > 0; i--) {  
  50.                 int index = random.nextInt(i + 1);  
  51.                 if (index < 0) {  
  52.                     index = -index;  
  53.                 }  
  54.                 rawList.set(index, rawList.set(i, rawList.get(index)));  
  55.             }  
  56.         }  
  57.     }
复制代码

评分

参与人数 1技术分 +1 收起 理由
古银平 + 1 神马都是浮云

查看全部评分

回复 使用道具 举报
就是List的下标,以及Random类的nextInt()方法循环遍历,随机交换位置。
回复 使用道具 举报
本帖最后由 张会文 于 2013-1-2 16:07 编辑

计算机做不到真正的随机,所有的计算机随机都是“伪随机”,算法不同而已,绝大部分都是用时间作随机种子
什么是“伪随机数”呢?因为实际上要保证每次生成的随机数都不同,那是不太可能的,我们唯一能做到的只能是尽量使每次生成的数字与前面的不同,并且尽量使生成的数字均匀分布在指定的范围内。
API中的解释:
public static void shuffle(List<?>list)
使用默认随机源对指定列表进行置换。所有置换发生的可能性都是大致相等的。前面描述中使用了不确定的词“大致”,因为随机源只是大致上独立选择位的无偏源。如果它是一个随机选择位的最佳源,那么算法将完全一致的选择置换。此实现向后遍历列表,从最后一个元素一直到第二个元素,将随机选择的元素重复交换到“当前位置”。元素是从列表的一部分随机选择的,该部分列表从第一个元素一直到当前位置(包括)。此方法以线性时间运行。如果指定列表没有实现 RandomAccess 接口并且是一个大型列表,则此实现在改组列表前将指定列表转储到数组中,并将改组后的数组转储回列表中。这避免了二次行为,该行为是原地改组一个“有序访问”列表引起的。
JAVA的Collections类中shuffle的用法
  1. <h2 class="title content-title"> </h2>
  2. <div id="content" class="content mod-cs-content text-content clearfix">
  3. <p>// ShuffleTest.java

  4. import java.util.*;

  5. public class
  6. ShuffleTest {
  7.     public static void main(String[] args) {
  8.         
  9. List<Integer> list = new ArrayList<Integer>();
  10.         for (int i
  11. = 0; i < 10; i++)
  12.             list.add(new Integer(i));
  13.         
  14. System.out.println("打乱前:");
  15.         System.out.println(list);

  16.         
  17. for (int i = 0; i < 5; i++) {
  18.             System.out.println("第" + i +
  19. "次打乱:");
  20.             Collections.shuffle(list);
  21.             
  22. System.out.println(list);
  23.         }
  24.     }
  25. }
  26. </p>
  27. <p></p>
  28. <p></p>
  29. <p></p>
  30. <p></p>
  31. <p>//对,就是将集合中的元素,重新的随机的排序........
  32. import java.util.*;
  33. import
  34. sun.plugin.javascript.navig.Array;

  35. public class Demo {
  36. public Demo()
  37. {
  38. }
  39. public static void main(String[] args) {

  40. ArrayList c=new
  41. ArrayList();

  42. for(int i=0;i <4;i++)
  43. {
  44. c.add(new Integer(i));

  45. }
  46. c.add("西西");
  47. c.add("哈哈");
  48. c.add("呵呵");
  49. c.add("嘿嘿");

  50. Iterator it=c.iterator();
  51. System.out.println("排序前的输出:\n");
  52. for(int
  53. i=0;i <c.size();i++)
  54. {
  55. System.out.println(""+c.get(i));
  56. }


  57. Collections.shuffle(c,new Random());

  58. System.out.println("排序后的输出:\n");
  59. while(it.hasNext())
  60. {

  61. System.out.println(""+it.next());
  62. }

  63. }

  64. }


  65. </p></div><p></p>
复制代码

评分

参与人数 1技术分 +1 收起 理由
古银平 + 1 神马都是浮云

查看全部评分

回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马