.net - 如何加速基于 Array.Sort() 的二维对象值数组 (.NET) 的排序算法？

Question

我们有一个二维对象数组。通常每一项都是一个普通的值类型，比如 Int32 或 Decimal，数组的一列包含相同类型的值。我们的数组可以包含大约一百万行，我们需要对其进行排序。

为了加快速度，我们使用了一种基于所谓的行映射的特殊算法，当行映射数组的每一项都包含数组行的索引以显示在特定位置。我们在排序时不交换数组行 - 我们只是使用我们的自定义比较器对行映射数组进行排序。

排序算法的主要部分如下所示:

RowNavigatorMapComparer myRowNavigatorMapComparer = new RowNavigatorMapComparer(this, myGroupAndSortData, isGrouping);
RowNavigatorMapItem[] map = RowNavigatorMapItem.FromRowNavigatorArray(fRowsMap, rowIndex, rowCount);
Array.Sort(map, myRowNavigatorMapComparer);

RowNavigatorMapComparer工具 IComparer<RowNavigatorMapItem> , 并在其 int Compare(RowNavigatorMapItem x, RowNavigatorMapItem y) 内比较两个数组数组值像这样实现:

return ManagerCompare.CompareObjects(cellX.Value, cellY.Value);

，其中ManagerCompare是这样实现的:

public class ManagerCompare
{
    private ManagerCompare(){}

    public static int CompareObjects(object valueX, object valueY)
    {
        IComparable myValueX = valueX as IComparable;
        IComparable myValueY = valueY as IComparable;
        if(myValueX == null)
        {
            if(myValueY == null)
                return 0;
            return -1;
        }
        if(myValueY == null)
            return 1;

        Type myTypeX = myValueX.GetType();
        Type myTypeY = myValueY.GetType();
        if(myTypeX != myTypeY)
            return string.CompareOrdinal(myTypeX.Name, myTypeY.Name); 

        return  myValueX.CompareTo(myValueY);
    }
}

我们不喜欢上面描述的整个构造的性能，并希望大大加快它的速度。我们知道调用Array.Sort(map, myRowNavigatorMapComparer)测试数组的随机内容需要 98% 的时间。如果我们返回 -1 而不是 ManagerCompare.CompareObjects(cellX.Value, cellY.Value)如果所有项目都已经排序，只是估计速度，总时间最多减少十倍。因此，Array.Sort() 实现中的主要问题似乎是它如何移动数组中的数据。有什么办法可以用更有效的方法代替它吗？

另一点需要考虑的是，如果我们知道列中存储的值的类型，则可以对目标数组的每一列使用硬编码比较算法。例如，如果一列包含整数值，我们可以使用以下调用代替 ManagerCompare.CompareObjects :

myResult = ((int)cellX.Value).CompareTo((int)cellY.Value);

但这种情况下的最佳性能增益仅为 5%...

当然我知道我们的代码使用拆箱是因为将值类型存储为对象，但我们无法避免。我们需要为用户提供一组从不同来源动态填充的对象。

此代码的原始版本是在 .NET 1.x 时代编写的，但现在我们可以使用 .NET 2.0 或更高版本中更强大的工具重写它，因此欢迎任何建议。

Answer 1

The original version of this code was written in the era of .NET 1.x, but now we can rewrite it using >more powerful tools from .NET 2.0 or higher, so any advices are welcome.

这里要记住的一件事(虽然它可能不会影响您的特定场景)是在 .NET 4.5 中 Array.Sort 的实现已经改变。

现在回到您的问题。你说你不能避免将值存储为对象，但这不应该阻止你做一些或预处理。您可以尝试以下操作:

• 在对数组进行排序之前，循环一次并缓存您需要的所有信息。例如，您可以创建一个新类型来存储 IComparable 引用 + GetType 的结果。因为您使用的是基于比较的排序算法(最多 O(n logn) )，这意味着您只需支付一次这些费用(这至少会删除比较方法中的一些强制转换、方法调用和比较)。
• 以上应该会根据阵列的生命周期继续提高性能