如何对异构数字的动态数组进行排序？

Question

我想排序一个可以包含不同数字类型(double,float等)的数组.这段代码引发System.ArgumentException("Value不是System.Single")错误:

new dynamic[] { 5L, 4D, 3F, 2U, 1M, 0UL }.ToList().Sort();

我知道我可以使用LINQ来做到这一点:

new dynamic[] { 5L, 4D, 3F, 2U, 1M, 0UL }.ToList().OrderBy(x => (decimal)x).ToArray();

但有没有更快的方法不涉及通过任何必须铸造每个元素？

附录:我还希望能够处理列表中的空值,因此即使是LINQ查询的强制转换也无济于事.

Answer 1

首先,删除ToList().此操作不是必需的,因此只需将其删除即可.这将加速一点点.

其余的:没有没有更快的方法.如果首先发布一个答案,其代码显示性能提高了2倍.但是,当我运行时比使用较大数组的代码时,它变得相对较慢,并且甚至比原始代码更慢.

为什么？整个OrderBy分为两部分:密钥的生成和通过比较这些密钥来对值进行排序.如果数组中的项目数量增加,则密钥的生成会线性增长,但比较操作的数量会呈指数级增长.

我的代码并不要求所有值都转换为小数(密钥生成期间的速度增加),但在排序期间fase unbox所需的值是性能判定.随着更大的阵列,比较操作的数量逐渐增加,因此拆箱的数量增加了,最终是钻井中的沙子.

我尝试过其他解决方案,比如创建委托接受两种类型的数字,并在其中委托一个动态的编译代码片段和两种类型的最佳比较解决方案,这总是涉及有时必须转换的数字.在分拣期间,这就变成了杀戮.

所以简单地说:不,你的日常工作不能更快.只要比较命令尽可能快,密钥生成的时间并不重要.

对于感兴趣的人,从我之前的答案中得到原始代码(对于较大的数组,这不是更快):

    static private dynamic[] testSet = new dynamic[] { 5L, 4D, 3F, null, 2U, 1M, null, 0UL };

    static void Main(string[] args)
    {
        Stopwatch st1 = new Stopwatch();
        st1.Start();
        for(int i = 0; i < 100000; i++)
            Test1();
        st1.Stop();

        Stopwatch st2 = new Stopwatch();
        st2.Start();
        for(int i = 0; i < 100000; i++)
            Test2();
        st2.Stop();
    }

    static public void Test1()
    {
        var result = testSet.OrderBy(x => x == null ? (decimal?)null : (decimal)x).ToArray();
    }

    static public void Test2()
    {
        var result = testSet.OrderBy(x => (object)x, new HeterogeneousNumbersComparer()).ToArray();
    }

    public class HeterogeneousNumbersComparer : IComparer<object>
    {
        public int Compare(object a, object b)
        {
            if (a == null)
                if (b == null)
                    return 0;
                else
                    return -1;
            else if (b == null)
                return +1;

            if (a.GetType() == b.GetType())
            {
                switch(Type.GetTypeCode(a.GetType()))
                {
                    case TypeCode.Byte:
                        return ((Byte)a).CompareTo((Byte)b);
                    case TypeCode.Decimal:
                        return ((Decimal)a).CompareTo((Decimal)b);
                    case TypeCode.Double:
                        return ((Double)a).CompareTo((Double)b);
                    case TypeCode.Int16:
                        return ((Int16)a).CompareTo((Int16)b);
                    case TypeCode.Int32:
                        return ((Int32)a).CompareTo((Int32)b);
                    case TypeCode.Int64:
                        return ((Int64)a).CompareTo((Int64)b);
                    case TypeCode.SByte:
                        return ((SByte)a).CompareTo((SByte)b);
                    case TypeCode.Single:
                        return ((Single)a).CompareTo((Single)b);
                    case TypeCode.UInt16:
                        return ((UInt16)a).CompareTo((UInt16)b);
                    case TypeCode.UInt32:
                        return ((UInt32)a).CompareTo((UInt32)b);
                    case TypeCode.UInt64:
                        return ((UInt64)a).CompareTo((UInt64)b);
                }
            }
            return Convert.ToDecimal(a).CompareTo(Convert.ToDecimal(b));
        }
    }
}

数字(在我的机器上):
测试1
:550毫秒测试
2 :263毫米所以...因素2 !!!