排序算法太慢ArrayList

Question

我想在java上實現Fisher-Yates shuffle算法。它可以工作，但是當我的ArrayList的大小大於100000時，它會變得非常慢。我會告訴你我的代碼，並且你看到了優化代碼的方法嗎？我對ArrayList中的.get和.set的複雜性做了一些研究，它對我來說是O（1）。

更新1：我注意到我的實現是錯誤的。這是適當的Fisher-Yates算法。此外，我還包括我的next()功能，以便你們可以看到它。我使用java.Random進行了測試，看看我的next()函數是否是問題，但它給出了相同的結果。我相信問題出在我的數據結構的使用上。

更新2：我做了一個測試，ArrayList是RandomAccess的一個實例。所以問題不在那裏。

private long next(){ // MurmurHash3 

    seed ^= seed >> 33; 
    seed *= 0xff51afd7ed558ccdL; 
    seed ^= seed >> 33; 
    seed *= 0xc4ceb9fe1a85ec53L; 
    seed ^= seed >> 33; 

    return seed; 

} 


public int next(int range){ 

    return (int) Math.abs((next() % range)); 

} 

public ArrayList<Integer> shuffle(ArrayList<Integer> pList){ 

    Integer temp; 
    int index; 
    int size = pList.size(); 

    for (int i = size - 1; i > 0; i--){ 

     index = next(i + 1); 
     temp = pList.get(index); 
     pList.set(index, pList.get(i)); 
     pList.set(i, temp); 

    } 

    return pList; 

} 

Answer 1

合併已經散落在註釋和其他一些片段回答：

• 原始代碼不是Fisher-Yates-Shuffle的實施。它只是交換隨機元素。這意味着某些排列比其他排序更可能，並且結果不是真正隨機的
• 如果存在瓶頸，它可能（根據所提供的代碼）僅在next方法中，您沒有對此做任何說明。它應該由java.util.Random

這裏實例的nextInt方法來代替是什麼它可能看起來像一個例子。 （請注意，speedTest方法甚至不是作爲「基準」遠程設計的，但應該僅指示即使對於大型列表，執行時間也可以忽略不計）。

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.List; 
import java.util.Random; 

class FisherYatesShuffle { 
    public static void main(String[] args) { 
     basicTest(); 
     speedTest(); 
    } 

    private static void basicTest() { 
     List<Integer> list = new ArrayList<Integer>(Arrays.asList(1,2,3,4,5)); 
     shuffle(list, new Random(0));; 
     System.out.println(list); 
    } 

    private static void speedTest() { 
     List<Integer> list = new ArrayList<Integer>(); 
     int n = 1000000; 
     for (int i=0; i<n; i++) { 
      list.add(i); 
     } 
     long before = System.nanoTime(); 
     shuffle(list, new Random(0));; 
     long after = System.nanoTime(); 
     System.out.println("Duration "+(after-before)/1e6+"ms"); 
     System.out.println(list.get(0)); 
    } 

    public static <T> void shuffle(List<T> list, Random random) { 
     for (int i = list.size() - 1; i > 0; i--) { 
      int index = random.nextInt(i + 1); 
      T t = list.get(index); 
      list.set(index, list.get(i)); 
      list.set(i, t); 
     } 
    } 
} 

另一方面：你給出了一個列表作爲參數，並返回相同的列表。這個可能在某些情況下是合適的，但在這裏沒有任何意義。這種方法的簽名和行爲有幾種選擇。但最有可能的是，它應該收到List，並在原地洗牌。實際上，明確檢查該列表是否實現接口也是有意義的。對於沒有實現RandomAccess接口的List，該算法會退化爲二次性能。在這種情況下，將給定列表複製到實現RandomAccess的列表中，將該副本洗牌並將結果複製回原始列表會更好。

Answer 2

（更適合代碼審查論壇）

我改變了我所能做：

Random random = new Random(42); 
for (ListIterator<Integer>.iter = pList.listIterator(); iter.hasNext();) { 
    Integer value = iter.next(); 
    int index = random.nextInt(size); 
    iter.set(pList.get(index)); 
    pList.set(index, value); 
} 

作爲一個ArrayList是大陣列的列表，您可以設置參數：initialCapacity在ArrayList構造函數。 trimToSize()也可能做一些事情。使用ListIterator意味着已經存在於當前的部分數組中，這可能會有所幫助。

隨機構造函數的可選參數（這裏是42）允許選擇一個固定的隨機序列（=可重複），允許在開發時間和跟蹤相同的序列。

Answer 3

試試這段代碼，並將執行時間與您的fisher yates方法進行比較。 這可能是「下一個」的方法是緩慢

function fisherYates(array) { 
    for (var i = array.length - 1; i > 0; i--) { 
    var index = Math.floor(Math.random() * i); 
    //swap 
    var tmp = array[index]; 
    array[index] = array[i]; 
    array[i] = tmp; 
} 

Answer 4

編輯：增加了一些評論您實施後正確Fisher-Yates算法。 Fisher-Yates算法依賴均勻分佈的隨機整數來產生無偏置排列。使用散列函數（MurmurHash3）生成隨機數並引入abs和模操作來強制數字處於一個固定的範圍內會使實現的穩健性降低。

此實現使用java.util.Random PRNG，並應做工精細您的需求：

public <T> List<T> shuffle(List<T> list) { 

    // trust the default constructor which sets the seed to a value very likely 
    // to be distinct from any other invocation of this constructor 
    final Random random = new Random(); 

    final int size = list.size(); 

    for (int i = size - 1; i > 0; i--) { 
     // pick a random number between one and the number 
     // of unstruck numbers remaining (inclusive) 
     int index = random.nextInt(i + 1); 
     list.set(index, list.set(i, list.get(index))); 
    } 

    return list; 

} 

我看不到你的代碼中的任何主要性能瓶頸。然而，這裏是一個火&忘記對Collections#shuffle方法的上述實施比較：

public void testShuffle() { 
    List<Integer> list = new ArrayList<>(); 

    for (int i = 0; i < 1_000_000; i++) { 
     list.add(i); 
    } 

    System.out.println("size: " + list.size()); 

    System.out.println("Fisher-Yates shuffle"); 
    for (int i = 0; i < 10; i++) { 
     long start = System.currentTimeMillis(); 
     shuffle(list); 
     long stop = System.currentTimeMillis(); 
     System.out.println("#" + i + " " + (stop - start) + "ms"); 
    } 

    System.out.println("Java shuffle"); 
    for (int i = 0; i < 10; i++) { 
     long start = System.currentTimeMillis(); 
     Collections.shuffle(list); 
     long stop = System.currentTimeMillis(); 
     System.out.println("#" + i + " " + (stop - start) + "ms"); 
    } 
} 

這給了我下面的結果：

size: 1000000 
Fisher-Yates shuffle 
#0 84ms 
#1 60ms 
#2 42ms 
#3 45ms 
#4 47ms 
#5 46ms 
#6 52ms 
#7 49ms 
#8 47ms 
#9 53ms 
Java shuffle 
#0 60ms 
#1 46ms 
#2 44ms 
#3 48ms 
#4 50ms 
#5 46ms 
#6 46ms 
#7 49ms 
#8 50ms 
#9 47ms