That sounds realistic; you are introducing more complexity (more lookups etc, more virtual methods, more range checks), so it can only get slower (array access is very direct and very quick).
It looks like you can get it a bit quicker (but not as quick as the array) by implementing an IComparer<T>
instead of the delegate approach; (edit) and faster again using IComparable<T>
:
Array.Sort: 2241ms
List.Sort (delegate): 8714ms
List.Sort (interface): 6976ms
List.Sort (comparable): 5456ms
With code:
using System;
using System.Collections.Generic;
using System.Diagnostics;
struct MyStruct : IComparable<MyStruct>
{
private readonly int key, value;
public int Key { get { return key; } }
public int Value { get { return value; } }
public MyStruct(int key, int value)
{
this.key = key;
this.value = value;
}
public int CompareTo(MyStruct other)
{
return key.CompareTo(other.key);
}
}
static class Program
{
static void Main()
{
const int SIZE = 10000000;
int[] a = new int[SIZE], b = new int[SIZE];
Random rand = new Random();
for(int i = 0 ; i < SIZE ; i++) {
a[i] = rand.Next();
b[i] = i;
}
var list = new List<MyStruct>(SIZE);
for (int i = 0; i < SIZE; i++)
{
list.Add(new MyStruct(a[i], b[i]));
}
var list2 = new List<MyStruct>(list);
var list3 = new List<MyStruct>(list);
var watch = Stopwatch.StartNew();
Array.Sort(a, b);
watch.Stop();
Console.WriteLine("Array.Sort: " + watch.ElapsedMilliseconds + "ms");
watch = Stopwatch.StartNew();
list.Sort((x, y) => x.Key.CompareTo(y.Key));
watch.Stop();
Console.WriteLine("List.Sort (delegate): " + watch.ElapsedMilliseconds + "ms");
watch = Stopwatch.StartNew();
list2.Sort(MyComparer.Default);
watch.Stop();
Console.WriteLine("List.Sort (interface): " + watch.ElapsedMilliseconds + "ms");
watch = Stopwatch.StartNew();
list3.Sort();
watch.Stop();
Console.WriteLine("List.Sort (comparable): " + watch.ElapsedMilliseconds + "ms");
}
sealed class MyComparer : IComparer<MyStruct>
{
private MyComparer() { }
public static readonly MyComparer Default = new MyComparer();
public int Compare(MyStruct x, MyStruct y)
{
return x.Key.CompareTo(y.Key);
}
}
}