JDK Collections.shuffle(List<?> list, Random

Aomine 发布于2019-08-15 14:48 / 1351人阅读

摘要：的源码如下一首先是判断要打乱的的属性的和是否实现接口如果的小于或者实现了接口，则直接交换内元素的位置。以上内容如有不正确的地方，欢迎支持。

jdk的源码如下

public static void shuffle(List list, Random rnd) {
        int size = list.size();
        if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
            for (int i=size; i>1; i--)
                swap(list, i-1, rnd.nextInt(i));
        } else {
            Object arr[] = list.toArray();

            // Shuffle array
            for (int i=size; i>1; i--)
                swap(arr, i-1, rnd.nextInt(i));

            // Dump array back into list
            // instead of using a raw type here, it"s possible to capture
            // the wildcard but it will require a call to a supplementary
            // private method
            ListIterator it = list.listIterator();
            for (int i=0; i
一、首先是判断要打乱的list的属性：list的size和是否实现RandomAccess接口
如果list的size小于SHUFFLE_THRESHOLD(5) 或者 list实现了RandomAccess接口，则直接交换list内元素的位置。具体的交换策略如下：
令list的size为n, 从n-1位开始，将该位的元素与其前面某一位(随机得到)元素交换，直到第1位结束。
使用的函数：
swap(List list, int i, int j)
public static void swap(List list, int i, int j) {
        // instead of using a raw type here, it"s possible to capture
        // the wildcard but it will require a call to a supplementary
        // private method
        final List l = list;
        l.set(i, l.set(j, l.get(i)));   //将j位置的值和i位置的值进行交换
}
E set(int index, E element)接口
    /**
     * Replaces the element at the specified position in this list with the
     * specified element (optional operation).
     * 
     * @param index index of the element to replace
     * @param element element to be stored at the specified position
     */
    E set(int index, E element)
E set(int index, E element)某一实现
public E set(int index, E element) {
      try {
            ListIterator e = listIterator(index);
            E oldVal = e.next();
            e.set(element);    
            return oldVal;      //将index的值设置为element，并返回原来的值
        } catch (NoSuchElementException exc) {
            throw new IndexOutOfBoundsException("Index: "+index);
        }
}
二、如果list没有实现RandomAccess接口且长度大于SHUFFLE_THRESHOLD(5)
这时候首先要做的是将list转化成数组，这个和RandomAccess有关
/**
 * Marker interface used by List implementations to indicate that
 * they support fast (generally constant time) random access.  The primary
 * purpose of this interface is to allow generic algorithms to alter their
 * behavior to provide good performance when applied to either random or
 * sequential access lists.
 *
 * The best algorithms for manipulating random access lists (such as
 * ArrayList) can produce quadratic behavior when applied to
 * sequential access lists (such as LinkedList).  Generic list
 * algorithms are encouraged to check whether the given list is an
 * instanceof this interface before applying an algorithm that would
 * provide poor performance if it were applied to a sequential access list,
 * and to alter their behavior if necessary to guarantee acceptable
 * performance.
 *
......
public interface RandomAccess {
}
RandomAccess用于标识ist的实现类是否支持快速地随机访问(一般是O(1)的时间复杂度)，例如ArraryList实现了RandomAccess接口，随机访问一个元素(get(i))所花费的时间复杂度是O(1)，而LinkedList却没有实现这个接口，所以随机一个元素的时间复杂度是O(n)(最坏情况)。所以在遍历一个list时，可以先判断它是否实现了RandomAccess接口，根据数据结构的不同先进行相应的处理，避免出现O(n²)的时间复杂度。
如在shuffle()的else代码段中，就先将没有实现RandomAccess接口的list转换成数组，然后在执行交换策略，这样避免O(n²)的时间复杂度。

以上内容如有不正确的地方，欢迎支持。

云服务器 GPU云服务器 list python &lt&gt java &lt=&gt java&lt &gt

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/68832.html

如何对两个列表进行乱序处理，同时保持它们的一一对应的关系？

摘要：如何对两个列表进行乱序处理，同时保持它们的一一对应的关系已知我们有两个列表其中和中的元素是一一对应的。现在我们希望对两个列表进行随机排序，要求排序后它们依旧是一一对应的。如何对两个列表进行乱序处理，同时保持它们的一一对应的关系？已知我们有两个列表 public class RandomizeTwoList { public static String [] file = {...

ashe 2019-08-16 17:28 评论0 收藏0
Java™ 教程（List接口）

List接口 List是一个有序的Collection（有时称为序列），列表可能包含重复元素，除了从Collection继承的操作之外，List接口还包括以下操作：位置访问 — 根据列表中的数字位置操纵元素，这包括get、set、add、addAll和remove等方法。搜索 — 搜索列表中的指定对象并返回其数字位置，搜索方法包括indexOf和lastIndexOf。迭代 — 扩展Ite...

hedzr 2019-08-16 14:47 评论0 收藏0
Java 性能调优指南之 Java 集合概览

摘要：单线程集合本部分将重点介绍非线程安全集合。非线程安全集合框架的最新成员是自起推出的。这是标准的单线程阵营中唯一的有序集合。该功能能有效防止运行时造型。检查个集合之间不存在共同的元素。基于自然排序或找出集合中的最大或最小元素。【编者按】本文作者为拥有十年金融软件开发经验的 Mikhail Vorontsov，文章主要概览了所有标准 Java 集合类型。文章系国内 ITOM 管理平台 O...

gnehc 2019-08-14 15:38 评论0 收藏0
pyecharts制作时长滚动图片柱状图+饼状图+玫瑰图+折线统计图

　　本文主要是详细介绍了pyecharts制作时长滚动图片柱状图+饼状图+玫瑰图+折线统计图,文章内容把握重点把握重点详尽的基本介绍，具有很强的实用价值，感兴趣的朋友可以了解一下。　　1、pyecharts绘制时间轮播柱形图　　fromrandomimportrandint 　　frompyechartsimportoptionsasopts 　　frompyecharts.chartsimpor...

89542767 2022-12-23 17:19 评论0 收藏0
1、Map接口 2、模拟斗地主洗牌发牌

摘要：中的集合称为单列集合，中的集合称为双列集合。洗牌通过数字完成洗牌发牌发牌将每个人以及底牌设计为将最后张牌直接存放于底牌，剩余牌通过对取模依次发牌。存放的过程中要求数字大小与斗地主规则的大小对应。 01Map集合概述 A:Map集合概述: 我们通过查看Map接口描述,发现Map接口下的集合与Collection接口下的集合，它们存储数据的形式不同  a:Collection中的集...

付伦 2019-08-14 18:41 评论0 收藏0