c# - 为什么在比较中使用 IComparable 比使用字符串慢？

Question

我正在使用 Mergesort 对 50.000.000 个字符串进行排序，根据我使用的参数类型，有两种不同的结果。

使用接口(interface) 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 interface，以及使用 interface-dispatch 而不是 virtual-dispatch(.NET 和 Java VM 等虚拟机的低级细节)比字符串比较更昂贵。如果您使用带有长公共(public)前缀的字符串，比较操作将成为主要的性能成本，并且两种形式之间的差距将会缩小。 编辑:在代码的发布版本上运行测试也可能会缩小差距(没有在本地运行测试，我不确定 OP 用于测试的版本)。 p>

现在更重要的是整个实验，忽略代码的所有其他问题，我将特别指出支持“可比较”项目的常见做法在 .NET 中以通用方式。

1. 不限制通用类型T (可能是也可能不是 string ，如果事实上它可能会或可能不会实现 IComparable )。
2. 使用IComparer<T>比较元素。如果用户传递 null对于 comparer公共(public)方法之一的参数，默认为 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);
    }
}