2

我正在使用 Mergesort 订购 50.000.000 个字符串，根据我使用的参数类型，有两种不同的结果。

使用接口 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，性能将会提高。为什么使用不同类型会有如此巨大的性能差异？

4

2 回答 2

1

要回答有关性能的问题：您的测试使用的字符串足够小，以至于使用非泛型IComparable接口需要额外的类型检查，以及使用 interface-dispatch 而不是 virtual-dispatch（virtual .NET 和 Java VM 等机器）比字符串比较更昂贵。如果您使用具有长公共前缀的字符串，比较操作将成为主要的性能成本，并且两种形式之间的差距将缩小。编辑：在代码的发布版本上运行测试也可以缩小差距（没有在本地运行测试，我不确定用于测试的 OP 是什么版本）。

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

  1. 不要限制泛型类型T（可能是也可能不是string，如果事实上它可能实现也可能不实现IComparable）。
  2. 使用 anIComparer<T>来比较元素。如果用户将nullforcomparer参数传递给其中一个公共方法，则默认为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);
    }
}
于 2013-03-10T04:44:31.730 回答
-3

恕我直言，我不得不简单地说：对象本身的大小......所以每次你声明一个 ICompare，它包含一堆额外的属性、方法等，它需要更多的时间，而不是你声明较小的细绳...

于 2013-03-10T01:32:26.090 回答