Collections.shuffleのRandomについて

• 
• Tweet

Javaのjava.util.Collectionsにはshuffleという便利なメソッドがありますが、shuffle(List<?> list)はマルチスレッドで遅くなります。JDK8u121の実装では次のようになっています。

public static void shuffle(List<?> list) {
    Random rnd = r;
    if (rnd == null)
        r = rnd = new Random(); // harmless race.
    shuffle(list, rnd);
}
private static Random r;

java.util.Randomを共有して処理する事になるので、複数のスレッドでCollections.shuffleを呼び出すと処理が詰まるわけです。Collectionsにはshuffle(List<?> list, Random rnd)というメソッドがあるので、次のように使うのが良いと思います。

Collections.shuffle(list, ThreadLocalRandom.current())

別件ですが、複数のスレッドで同じListに対してCollections.shuffleを呼び出すと壊れます。(そんな事をする人は少ないと思いますが)

どれくらい遅いのか？

JMHで簡単に計ってみました。

Benchmark                               Mode  Cnt        Score   Error  Units
Shuffle.random_list100                 thrpt    2   122031.999          ops/s
Shuffle.random_list1000                thrpt    2    11964.147          ops/s
Shuffle.random_list10000               thrpt    2     1306.136          ops/s
Shuffle.thread_local_random_list100    thrpt    2  2370353.238          ops/s
Shuffle.thread_local_random_list1000   thrpt    2   200793.729          ops/s
Shuffle.thread_local_random_list10000  thrpt    2    21029.163          ops/s

@Fork(1)
@Warmup(iterations=3)
@BenchmarkMode(Mode.Throughput)
@OutputTimeUnit(TimeUnit.SECONDS)
@Measurement(iterations=2, time=10, timeUnit=TimeUnit.SECONDS)
@Threads(4)
@State(Scope.Thread)
public class Shuffle {

  private List<Integer> list100 = new ArrayList<Integer>(100);
  private List<Integer> list1000 = new ArrayList<Integer>(1000);
  private List<Integer> list10000 = new ArrayList<Integer>(10000);
  @Setup
  public void setup() {
    for (int i = 0; i < 100; i++) {
      list100.add(ThreadLocalRandom.current().nextInt());
    }
    for (int i = 0; i < 1000; i++) {
      list1000.add(ThreadLocalRandom.current().nextInt());
    }
    for (int i = 0; i < 10000; i++) {
      list10000.add(ThreadLocalRandom.current().nextInt());
    }
  }

  @Benchmark
  public void random_list100() {
    Collections.shuffle(list100);
  }

  @Benchmark
  public void random_list1000() {
    Collections.shuffle(list1000);
  }

  @Benchmark
  public void random_list10000() {
    Collections.shuffle(list10000);
  }

  @Benchmark
  public void thread_local_random_list100() {
    Collections.shuffle(list100, ThreadLocalRandom.current());
  }

  @Benchmark
  public void thread_local_random_list1000() {
    Collections.shuffle(list1000, ThreadLocalRandom.current());
  }

  @Benchmark
  public void thread_local_random_list10000() {
    Collections.shuffle(list10000, ThreadLocalRandom.current());
  }

}