速度比較

Listのソート速度を比較してみました。

using System;
using System.Collections.Generic;
using System.Collections;

namespace ListSortSpeedTest
{
	public class Program
	{
		private const int Max = 5000000;

		public static void Main( string[] args )
		{
			Random random = new Random();
			List<int> list = new List<int>();

			for ( int i = 0; i < Max; i++ )
			{
				list.Add( random.Next() );
			}

			Test( list );
			Test( list );
			Test( list );
			Test( list );
			Test( list );
			Console.ReadLine();
		}

		private static void Test( List<int> list )
		{
			int[] org = new int[ Max ];
			list.CopyTo( org );

			Console.WriteLine( "" );
			int t0, t1;

			t0 = Environment.TickCount;
			SortOriginal( list );
			t1 = Environment.TickCount;
			Console.WriteLine( "SortOriginal   : " + ( t1 - t0 ).ToString() );
			list.Clear();
			list.AddRange( org );

			t0 = Environment.TickCount;
			SortComparison( list );
			t1 = Environment.TickCount;
			Console.WriteLine( "SortComparison : " + ( t1 - t0 ).ToString() );
			list.Clear();
			list.AddRange( org );

			t0 = Environment.TickCount;
			SortComparison2( list );
			t1 = Environment.TickCount;
			Console.WriteLine( "SortComparison2: " + ( t1 - t0 ).ToString() );
			list.Clear();
			list.AddRange( org );

			t0 = Environment.TickCount;
			SortIComparer( list );
			t1 = Environment.TickCount;
			Console.WriteLine( "SortIComparer  : " + ( t1 - t0 ).ToString() );
			list.Clear();
			list.AddRange( org );

			ArrayList al = new ArrayList( org );
			t0 = Environment.TickCount;
			SortArrayList( al );
			t1 = Environment.TickCount;
			Console.WriteLine( "SortArrayList  : " + ( t1 - t0 ).ToString() );
		}

		private static void SortOriginal( List<int> list )
		{
			list.Sort();
		}

		private static void SortComparison( List<int> list )
		{
			list.Sort( delegate( int x, int y ) { return x - y; } );
		}

		private static void SortComparison2( List<int> list )
		{
			list.Sort( ComparisonMethod );
		}

		private static void SortIComparer( List<int> list )
		{
			list.Sort( new Comp() );
		}

		private static void SortArrayList( ArrayList al )
		{
			al.Sort();
		}

		public static int ComparisonMethod( int x, int y )
		{
			return x - y;
		}
	}

	public class Comp : IComparer<int>
	{
		public Comp() {}

		public int Compare( int x, int y )
		{
			return x - y;
		}
	}
}

タイムは書きませんが傾向は早いほうから順に、SortOriginal、SortIComparer、SortComparison、SortComparison2、SortArrayList でした。
SortComparison と SortComparison2 の差はほとんどなく、ときどき順位が入れ替わります。誤差の範囲内と見てよさそう。

SortOriginal と SortIComparer の差は 3.1〜3.3倍程度。
SortIComparer と SortComparison の差は 1.3倍程度。delegateが.NET2.0でも遅いのかってが知りたくてこれをやってみたんですが、もしかしてメソッドコールと大きな差はなくなったのかな？少なくともWriting Faster Managed Code: Know What Things Costで書かれているほどの大きな差はないようです。う〜ん、興味深い。

比較するのがかわいそうだけどArrayListも入れてあります。ListとArrayListは値型で最大の差が出ると思われるので、一度見てみたかったのです。案の定、すごいことになってます。

ところで、Listのコピーってもっとうまいやり方ないでしょうか？