博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
JDK Collections.shuffle(List<?> list, Random rnd)源码分析
阅读量:5825 次
发布时间:2019-06-18

本文共 3217 字,大约阅读时间需要 10 分钟。

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(n2)的时间复杂度。

如在shuffle()的else代码段中,就先将没有实现RandomAccess接口的list转换成数组,然后在执行交换策略,这样避免O(n2)的时间复杂度。


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

转载地址:http://tosdx.baihongyu.com/

你可能感兴趣的文章
规划网络地址分配
查看>>
求助:路由交换-关于×××虚拟私有网二层隧道协议的问题
查看>>
我的友情链接
查看>>
LimeSDR Mini轻松上手系列3:Cubic SDR收听FM广播
查看>>
Android四大组件及意图和意图过滤器
查看>>
权限管理系统
查看>>
sed 问题
查看>>
lamp环境的搭建和应用
查看>>
我的友情链接
查看>>
LaTeX - 黎曼和
查看>>
过程化SQL、存储过程、自定义函数
查看>>
android出现的问题之 grandle一直在refreshing gradle project
查看>>
从实体搜索看搜索引擎发展趋势
查看>>
[转载] 百科全说——王晓斋:感冒时您找准医生了吗?(10-10-11)
查看>>
005,spring boot 配置文件-多环境配置
查看>>
我的友情链接
查看>>
[转载] 百科全说——潘怀宗:生活中的健康清洁法(11-01-25)
查看>>
[转载] 山楂树之恋——16-18
查看>>
Java NIO简单使用
查看>>
第七周作业
查看>>