Collections.shuffleのRandomについて

  • このエントリーをはてなブックマークに追加

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());
}

}