JavaのArrays#sortは、Collections#sortに比べてどのくらい速いのか？

Javaにはリストクラスがあるので、配列とリストクラスの使い分けをする必要があります。
リストクラスの方が多機能で便利なので、多くの場合はリストクラスを使います。しかし、パフォーマンスにシビアな場面だと、リストクラスのようなオーバーヘッドがありそうなものを避けたくなります。
というわけで、どのくらい速度差があるのか気になって試しました。ついでに、ArrayListとLinkedListも比較しました。

テストデータの作り方

要素数100万件のリストを作ります。中のオブジェクトは、longでランダムな数値とします。

ArrayList arrayListIds = new ArrayList();
for (int j = 0; j < 1000000; j++)
	arrayListIds.add((long) new Random().nextInt(50000000));

このArrayListを元に、LinkedListを作ります。

LinkedList linkedListIds = new LinkedList(arrayListIds);

long配列は、GuavaのLongsクラスで生成しました。

long[] arrayIds = Longs.toArray(arrayListIds);

これでテストデータが完成です。

ソートの仕方

ArrayListとLinkedListは、Collections#sortメソッドでソートします。

Collections.sort(arrayListIds);

Collections.sort(linkedListIds);

long配列は、Arrays#sortメソッドでソートします。

Arrays.sort(arrayIds);

あとはこれを測定するだけです。

結果は、Arrays#sortが5倍くらい速い

テストは100回繰り返して平均をとっています。

これを見ると、Arrays#sortの速度は、Collections#sortの5倍くらい速いようです。ArrayListとLinkedListはそれほど差がありませんでした。
ArrayList<Long>のソート時間と、long[]のソート時間をプロットしてみました。

テストデータによって何かしらの相関が見えたりするのかなと思っていましたが、特になくて面白くない図になりました。テストデータ自体がランダムだからかもしれません。

付録: 検証コード

検証コードの全体です。

for (int i = 0; i < 100; i++) {
	ArrayList arrayListIds = new ArrayList();
	for (int j = 0; j < 1000000; j++)
		arrayListIds.add((long) new Random().nextInt(50000000));
	LinkedList linkedListIds = new LinkedList(arrayListIds);
	long[] arrayIds = Longs.toArray(arrayListIds);
	{
		long start = new Date().getTime();
		Collections.sort(arrayListIds);
		System.out.print((new Date().getTime() - start) + ",");
	}
	{
		long start = new Date().getTime();
		Collections.sort(linkedListIds);
		System.out.print((new Date().getTime() - start) + ",");
	}
	{
		long start = new Date().getTime();
		Arrays.sort(arrayIds);
		System.out.print((new Date().getTime() - start) + "\n");
	}
}

終わりです。