c# - 比較で IComparable を使用すると文字列よりも遅いのはなぜですか?

Question

Mergesort を使用して 50.000.000 文字列を注文していますが、使用するパラメーター タイプに応じて 2 つの異なる結果が得られます。

インターフェイス IComparable の使用:

• 20226ミリ秒

文字列を直接使用する:

• 10912 ミリ秒

マージソート コード:

public class Mergesort2
{
    static private StringComparer comparer1 = StringComparer.Ordinal;
    public static void merge(IComparable[] a, IComparable[] aux, int lo, int mid, int hi)
    {

        for (int k = lo; k <= hi; k++)
        {
            aux[k] = a[k];
        }

        // merge back to a[]
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++)
        {
            if (i > mid)
            {
                a[k] = aux[j++];
            }
            else if (j > hi)
            {
                a[k] = aux[i++];
            }
            else if (less(aux[j], aux[i]))
            {
                a[k] = aux[j++];
            }
            else
            {
                a[k] = aux[i++];
            }
        }

    }

    private static void sort(IComparable[] a, IComparable[] aux, int lo, int hi)
    {
        if (hi <= lo)
        {
            return;
        }
        int mid = lo + (hi - lo) / 2;
        sort(a, aux, lo, mid);
        sort(a, aux, mid + 1, hi);
        merge(a, aux, lo, mid, hi);
    }

    public static void sort(IComparable[] a)
    {
        IComparable[] aux = new IComparable[a.Length];
        sort(a, aux, 0, a.Length - 1);
    }


    ///*********************************************************************
    ///  Helper sorting functions
    /// **********************************************************************

    // is v < w ?
    private static bool less(IComparable v, IComparable w)
    {
        return (comparer1.Compare(v, w) < 0);
    }

    // exchange a[i] and a[j]
    private static void exch(Object[] a, int i, int j)
    {
        Object swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }

    /// <summary>
    ///*********************************************************************
    ///  Index mergesort
    /// **********************************************************************
    /// </summary>
    // stably merge a[lo .. mid] with a[mid+1 .. hi] using aux[lo .. hi]
    private static void merge(IComparable[] a, int[] index, int[] aux, int lo, int mid, int hi)
    {

        // copy to aux[]
        for (int k = lo; k <= hi; k++)
        {
            aux[k] = index[k];
        }

        // merge back to a[]
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++)
        {
            if (i > mid)
            {
                index[k] = aux[j++];
            }
            else if (j > hi)
            {
                index[k] = aux[i++];
            }
            else if (less(a[aux[j]], a[aux[i]]))
            {
                index[k] = aux[j++];
            }
            else
            {
                index[k] = aux[i++];
            }
        }
    }

    // return a permutation that gives the elements in a[] in ascending order
    // do not change the original array a[]
    public static int[] indexSort(IComparable[] a)
    {
        int N = a.Length;
        int[] index = new int[N];
        for (int i = 0; i < N; i++)
        {
            index[i] = i;
        }

        int[] aux = new int[N];
        sort(a, index, aux, 0, N - 1);
        return index;
    }

    // mergesort a[lo..hi] using auxiliary array aux[lo..hi]
    private static void sort(IComparable[] a, int[] index, int[] aux, int lo, int hi)
    {
        if (hi <= lo)
        {
            return;
        }
        int mid = lo + (hi - lo) / 2;
        sort(a, index, aux, lo, mid);
        sort(a, index, aux, mid + 1, hi);
        merge(a, index, aux, lo, mid, hi);
    }
}

このコードにより、ランタイムが遅くなります。

すべてのIComparable型をStringに変更すると、パフォーマンスが向上します。異なるタイプを使用すると、なぜこれほど大きなパフォーマンスの違いがあるのでしょうか?

Answer 1

パフォーマンスに関する質問に答えるには、テストで、非ジェネリックIComparableインターフェイスを使用するために必要な追加の型チェックに加えて、virtual-dispatch（仮想の低レベルの詳細）の代わりにinterface-dispatchを使用するのに十分小さい文字列を使用しました。 .NETやJavaVMなどのマシンは、文字列の比較よりも高価でした。長い共通プレフィックスを持つ文字列を使用した場合、比較操作が主要なパフォーマンスコストになり、2つの形式間のギャップが縮まります。編集：コードのリリースビルドでテストを実行すると、ギャップも埋められる可能性があります（テストをローカルで実行しなかったため、テストに使用したOPのビルドがわかりません）。

ここで、実験全体にとってより重要なことですが、コードに関する他のすべての問題を無視して、.NETで一般的な方法で「比較可能な」アイテムをサポートするための一般的な方法を具体的に指摘します。

1. ジェネリック型を制限しないでくださいT（string実際には実装されている場合とされていない場合がありますIComparable）。
2. を使用しIComparer<T>て要素を比較します。ユーザーが引数のanullをcomparerパブリックメソッドの1つに渡す場合、デフォルトは。ですComparer<T>.Default。

更新されたコードは次のとおりです。

public class Mergesort2
{
    public static void merge<T>(T[] a, T[] aux, int lo, int mid, int hi, IComparer<T> comparer)
    {
        comparer = comparer ?? Comparer<T>.Default;

        for (int k = lo; k <= hi; k++)
        {
            aux[k] = a[k];
        }

        // merge back to a[]
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++)
        {
            if (i > mid)
            {
                a[k] = aux[j++];
            }
            else if (j > hi)
            {
                a[k] = aux[i++];
            }
            else if (less(aux[j], aux[i], comparer))
            {
                a[k] = aux[j++];
            }
            else
            {
                a[k] = aux[i++];
            }
        }

    }

    private static void sort<T>(T[] a, T[] aux, int lo, int hi, IComparer<T> comparer)
    {
        if (hi <= lo)
        {
            return;
        }
        int mid = lo + (hi - lo) / 2;
        sort(a, aux, lo, mid, comparer);
        sort(a, aux, mid + 1, hi, comparer);
        merge(a, aux, lo, mid, hi, comparer);
    }

    public static void sort<T>(T[] a, IComparer<T> comparer)
    {
        comparer = comparer ?? Comparer<T>.Default;
        T[] aux = new T[a.Length];
        sort(a, aux, 0, a.Length - 1, comparer);
    }


    ///*********************************************************************
    ///  Helper sorting functions
    /// **********************************************************************

    // is v < w ?
    private static bool less<T>(T v, T w, IComparer<T> comparer)
    {
        return (comparer.Compare(v, w) < 0);
    }

    // exchange a[i] and a[j]
    private static void exch<T>(T[] a, int i, int j)
    {
        T swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }

    /// <summary>
    ///*********************************************************************
    ///  Index mergesort
    /// **********************************************************************
    /// </summary>
    // stably merge a[lo .. mid] with a[mid+1 .. hi] using aux[lo .. hi]
    private static void merge<T>(T[] a, int[] index, int[] aux, int lo, int mid, int hi, IComparer<T> comparer)
    {

        // copy to aux[]
        for (int k = lo; k <= hi; k++)
        {
            aux[k] = index[k];
        }

        // merge back to a[]
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++)
        {
            if (i > mid)
            {
                index[k] = aux[j++];
            }
            else if (j > hi)
            {
                index[k] = aux[i++];
            }
            else if (less(a[aux[j]], a[aux[i]], comparer))
            {
                index[k] = aux[j++];
            }
            else
            {
                index[k] = aux[i++];
            }
        }
    }

    // return a permutation that gives the elements in a[] in ascending order
    // do not change the original array a[]
    public static int[] indexSort<T>(T[] a, IComparer<T> comparer)
    {
        comparer = comparer ?? Comparer<T>.Default;
        int N = a.Length;
        int[] index = new int[N];
        for (int i = 0; i < N; i++)
        {
            index[i] = i;
        }

        int[] aux = new int[N];
        sort(a, index, aux, 0, N - 1, comparer);
        return index;
    }

    // mergesort a[lo..hi] using auxiliary array aux[lo..hi]
    private static void sort<T>(T[] a, int[] index, int[] aux, int lo, int hi, IComparer<T> comparer)
    {
        if (hi <= lo)
        {
            return;
        }
        int mid = lo + (hi - lo) / 2;
        sort(a, index, aux, lo, mid, comparer);
        sort(a, index, aux, mid + 1, hi, comparer);
        merge(a, index, aux, lo, mid, hi, comparer);
    }
}

Answer 2

私見、私はこれを簡単に言わなければならないでしょう：オブジェクト自体のサイズ...したがって、追加のプロパティ、メソッドなどの束を含むICompareを宣言するたびに、より少ないものを宣言する場合よりも時間がかかります弦...