How to sort a dynamic array of heterogeneous numbers?

Question

I want to sort an array that can contain different numeric types (double, float, etc.). This code throws a System.ArgumentException ("Value is not System.Single") error:

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

I know I can use LINQ to do this:

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

But is there a faster way that does not include performing any operations associated with each element?

Addendum: I would also like to be able to process zeros in a list, so even listing a LINQ query will not help.

Answer 1

First remove ToList (). This operation is not required, so just delete it. This will speed things up a bit.

Otherwise: there is no faster way. If at first a response was sent with code showing an increase in performance with a coefficient of 2. But, when I ran than the code with larger arrays, it became relatively slower and at a point even slower than the source code.

Why? The entire OrderBy is divided into 2 parts: generating keys and sorting values ​​by comparing these keys. If the number of elements in the array grows, key generation grows linearly, but the number of comparison operations grows exponentially.

My code did not require converting all values ​​to decimal numbers (speed increase during key generation), but during fase sorting, the values ​​needed for deletion, which is a performance decomposition. With larger arrays, the number of comparison operations increased exponentially, so the number of unpackers increased, which ultimately was sand in the layers.

I tried another solution, preferring to create delegates that accept two types of numbers, and in this deletion the dynamic part of the compiled code with the optimal solution for comparison for both types, which is always due to the fact that sometimes you need to convert the number. And during the sort-phase this becomes a kill.

It’s so simple to put: No, your routine cannot be done faster. It does not matter how long the key generation phase is, if you compare the phase as quickly as possible.

For people who are interested, the source code from my previous answer (which is NOT faster with large arrays):

  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)); } } } 

Numbers (on my machine):
Test1: 550 ms
Test2: 263ms
So ... factor 2 !!!