3

int配列のペアをソートしようとしています（int [] a; int [] b;）

Array.Sort（a、b）を使用すると、パフォーマンスが向上します。

ただし、List <>を使用して、構造体にintペアをロードすることをお勧めします。構造体の単純な比較子を提供するオーバーロードでArray.Sort（）を使用してこれを機能させることができますが、Array.Sort（a、b）よりも約4倍遅くなります。

それは正常ですか？

4

1 に答える 1

9

それは現実的に聞こえます。複雑さを増している (ルックアップなどの増加、仮想メソッドの増加、範囲チェックの増加) ため、遅くなるだけです (配列アクセスは非常に直接的で非常に高速です)。

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);
        }
    }
}
于 2009-05-30T22:35:40.577 に答える