Я пытаюсь отсортировать пару массивов int (int[] a; int[] b;)
Если я использую Array.Sort(a,b), то производительность отличная.
Однако я бы предпочел использовать List‹> и загружать пары int в структуру. Я могу заставить это работать, используя Array.Sort() с перегрузкой, которая обеспечивает простой компаратор для структуры, но примерно в 4 раза медленнее, чем Array.Sort(a,b)
Это нормально?
Звучит реалистично; вы вводите больше сложности (больше поиска и т. д., больше виртуальных методов, больше проверок диапазона), поэтому это может только замедлиться (доступ к массиву очень прямой и очень быстрый).
Похоже, вы можете получить это немного быстрее (но не так быстро, как массив), реализуя IComparer<T> вместо подхода делегата; (редактировать) и еще раз быстрее, используя IComparable<T>:
Array.Sort: 2241ms
List.Sort (delegate): 8714ms
List.Sort (interface): 6976ms
List.Sort (comparable): 5456ms
С кодом:
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);
}
}
}
