java - 改组 ArrayList 的算法太慢

Question

我正在尝试在 Java 上实现 Fisher-Yates 洗牌算法。它可以工作，但是当我的 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 后添加了一些评论算法。

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