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

Aomine 發(fā)布于2019-08-15 14:48 / 1358人閱讀

摘要：的源碼如下一首先是判斷要打亂的的屬性的和是否實現(xiàn)接口如果的小于或者實現(xiàn)了接口，則直接交換內元素的位置。以上內容如有不正確的地方，歡迎支持。

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和是否實現(xiàn)RandomAccess接口
如果list的size小于SHUFFLE_THRESHOLD(5) 或者 list實現(xiàn)了RandomAccess接口，則直接交換list內元素的位置。具體的交換策略如下：
令list的size為n, 從n-1位開始，將該位的元素與其前面某一位(隨機得到)元素交換，直到第1位結束。
使用的函數(shù)：
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)某一實現(xiàn)
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沒有實現(xiàn)RandomAccess接口且長度大于SHUFFLE_THRESHOLD(5)
這時候首先要做的是將list轉化成數(shù)組，這個和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的實現(xiàn)類是否支持快速地隨機訪問(一般是O(1)的時間復雜度)，例如ArraryList實現(xiàn)了RandomAccess接口，隨機訪問一個元素(get(i))所花費的時間復雜度是O(1)，而LinkedList卻沒有實現(xiàn)這個接口，所以隨機一個元素的時間復雜度是O(n)(最壞情況)。所以在遍歷一個list時，可以先判斷它是否實現(xiàn)了RandomAccess接口，根據(jù)數(shù)據(jù)結構的不同先進行相應的處理，避免出現(xiàn)O(n²)的時間復雜度。
如在shuffle()的else代碼段中，就先將沒有實現(xiàn)RandomAccess接口的list轉換成數(shù)組，然后在執(zhí)行交換策略，這樣避免O(n²)的時間復雜度。

以上內容如有不正確的地方，歡迎支持。

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://systransis.cn/yun/68832.html

如何對兩個列表進行亂序處理，同時保持它們的一一對應的關系？

摘要：如何對兩個列表進行亂序處理，同時保持它們的一一對應的關系已知我們有兩個列表其中和中的元素是一一對應的。現(xiàn)在我們希望對兩個列表進行隨機排序，要求排序后它們依舊是一一對應的。如何對兩個列表進行亂序處理，同時保持它們的一一對應的關系？已知我們有兩個列表 public class RandomizeTwoList { public static String [] file = {...

ashe 2019-08-16 17:28 評論0 收藏0
Java? 教程（List接口）

List接口 List是一個有序的Collection（有時稱為序列），列表可能包含重復元素，除了從Collection繼承的操作之外，List接口還包括以下操作：位置訪問 — 根據(jù)列表中的數(shù)字位置操縱元素，這包括get、set、add、addAll和remove等方法。搜索 — 搜索列表中的指定對象并返回其數(shù)字位置，搜索方法包括indexOf和lastIndexOf。迭代 — 擴展Ite...

hedzr 2019-08-16 14:47 評論0 收藏0
Java 性能調優(yōu)指南之 Java 集合概覽

摘要：單線程集合本部分將重點介紹非線程安全集合。非線程安全集合框架的最新成員是自起推出的。這是標準的單線程陣營中唯一的有序集合。該功能能有效防止運行時造型。檢查個集合之間不存在共同的元素?；谧匀慌判蚧蛘页黾现械淖畲蠡蜃钚≡?。【編者按】本文作者為擁有十年金融軟件開發(fā)經驗的 Mikhail Vorontsov，文章主要概覽了所有標準 Java 集合類型。文章系國內 ITOM 管理平臺 O...

gnehc 2019-08-14 15:38 評論0 收藏0
pyecharts制作時長滾動圖片柱狀圖+餅狀圖+玫瑰圖+折線統(tǒng)計圖

　　本文主要是詳細介紹了pyecharts制作時長滾動圖片柱狀圖+餅狀圖+玫瑰圖+折線統(tǒng)計圖,文章內容把握重點把握重點詳盡的基本介紹，具有很強的實用價值，感興趣的朋友可以了解一下?！　?、pyecharts繪制時間輪播柱形圖　　fromrandomimportrandint 　　frompyechartsimportoptionsasopts 　　frompyecharts.chartsimpor...

89542767 2022-12-23 17:19 評論0 收藏0
1、Map接口 2、模擬斗地主洗牌發(fā)牌

摘要：中的集合稱為單列集合，中的集合稱為雙列集合。洗牌通過數(shù)字完成洗牌發(fā)牌發(fā)牌將每個人以及底牌設計為將最后張牌直接存放于底牌，剩余牌通過對取模依次發(fā)牌。存放的過程中要求數(shù)字大小與斗地主規(guī)則的大小對應。 01Map集合概述 A:Map集合概述: 我們通過查看Map接口描述,發(fā)現(xiàn)Map接口下的集合與Collection接口下的集合，它們存儲數(shù)據(jù)的形式不同 ? a:Collection中的集...

付倫 2019-08-14 18:41 評論0 收藏0