Solución:
Actualizar:
Estaba bastante interesado en este tema, así que me senté y lo implementé (usando esta implementación muy rápida y conservadora de memoria). También leí este (gracias celion) y descubrí que ni siquiera tienes que dividir los flotadores en mantisa y exponente para ordenarlos. Solo tiene que tomar los bits uno a uno y realizar una ordenación int. Solo tienes que preocuparte por los valores negativos, que deben colocarse inversamente frente a los positivos al final del algoritmo (lo hice en un paso con la última iteración del algoritmo para ahorrar algo de tiempo en la CPU).
Así que aquí está mi radixsort flotante:
public static float[] RadixSort(this float[] array)
{
// temporary array and the array of converted floats to ints
int[] t = new int[array.Length];
int[] a = new int[array.Length];
for (int i = 0; i < array.Length; i++)
a[i] = BitConverter.ToInt32(BitConverter.GetBytes(array[i]), 0);
// set the group length to 1, 2, 4, 8 or 16
// and see which one is quicker
int groupLength = 4;
int bitLength = 32;
// counting and prefix arrays
// (dimension is 2^r, the number of possible values of a r-bit number)
int[] count = new int[1 << groupLength];
int[] pref = new int[1 << groupLength];
int groups = bitLength / groupLength;
int mask = (1 << groupLength) - 1;
int negatives = 0, positives = 0;
for (int c = 0, shift = 0; c < groups; c++, shift += groupLength)
{
// reset count array
for (int j = 0; j < count.Length; j++)
count[j] = 0;
// counting elements of the c-th group
for (int i = 0; i < a.Length; i++)
{
count[(a[i] >> shift) & mask]++;
// additionally count all negative
// values in first round
if (c == 0 && a[i] < 0)
negatives++;
}
if (c == 0) positives = a.Length - negatives;
// calculating prefixes
pref[0] = 0;
for (int i = 1; i < count.Length; i++)
pref[i] = pref[i - 1] + count[i - 1];
// from a[] to t[] elements ordered by c-th group
for (int i = 0; i < a.Length; i++){
// Get the right index to sort the number in
int index = pref[(a[i] >> shift) & mask]++;
if (c == groups - 1)
{
// We're in the last (most significant) group, if the
// number is negative, order them inversely in front
// of the array, pushing positive ones back.
if (a[i] < 0)
index = positives - (index - negatives) - 1;
else
index += negatives;
}
t[index] = a[i];
}
// a[]=t[] and start again until the last group
t.CopyTo(a, 0);
}
// Convert back the ints to the float array
float[] ret = new float[a.Length];
for (int i = 0; i < a.Length; i++)
ret[i] = BitConverter.ToSingle(BitConverter.GetBytes(a[i]), 0);
return ret;
}
Es un poco más lento que una ordenación int radix, debido a que la matriz se copia al principio y al final de la función, donde los flotantes se copian bit a bit en ints y viceversa. No obstante, toda la función vuelve a ser O (n). En cualquier caso, mucho más rápido que ordenar 3 veces seguidas como propusiste. Ya no veo mucho espacio para las optimizaciones, pero si alguien lo ve, no dude en decírmelo.
Para ordenar descendente, cambie esta línea al final:
ret[i] = BitConverter.ToSingle(BitConverter.GetBytes(a[i]), 0);
a esto:
ret[a.Length - i - 1] = BitConverter.ToSingle(BitConverter.GetBytes(a[i]), 0);
Medición:
Configuré una prueba corta, que contiene todos los casos especiales de flotadores (NaN, +/- Inf, valor mínimo / máximo, 0) y números aleatorios. Ordena exactamente el mismo orden que Linq o Array.Sort ordena flotadores:
NaN -> -Inf -> Min -> Negative Nums -> 0 -> Positive Nums -> Max -> +Inf
Así que realicé una prueba con una gran variedad de números de 10 millones:
float[] test = new float[10000000];
Random rnd = new Random();
for (int i = 0; i < test.Length; i++)
{
byte[] buffer = new byte[4];
rnd.NextBytes(buffer);
float rndfloat = BitConverter.ToSingle(buffer, 0);
switch(i){
case 0: { test[i] = float.MaxValue; break; }
case 1: { test[i] = float.MinValue; break; }
case 2: { test[i] = float.NaN; break; }
case 3: { test[i] = float.NegativeInfinity; break; }
case 4: { test[i] = float.PositiveInfinity; break; }
case 5: { test[i] = 0f; break; }
default: { test[i] = test[i] = rndfloat; break; }
}
}
Y detuvo el tiempo de los diferentes algoritmos de clasificación:
Stopwatch sw = new Stopwatch();
sw.Start();
float[] sorted1 = test.RadixSort();
sw.Stop();
Console.WriteLine(string.Format("RadixSort: {0}", sw.Elapsed));
sw.Reset();
sw.Start();
float[] sorted2 = test.OrderBy(x => x).ToArray();
sw.Stop();
Console.WriteLine(string.Format("Linq OrderBy: {0}", sw.Elapsed));
sw.Reset();
sw.Start();
Array.Sort(test);
float[] sorted3 = test;
sw.Stop();
Console.WriteLine(string.Format("Array.Sort: {0}", sw.Elapsed));
Y la salida fue (actualización: ahora se ejecutó con la versión de compilación, no con la depuración):
RadixSort: 00:00:03.9902332
Linq OrderBy: 00:00:17.4983272
Array.Sort: 00:00:03.1536785
aproximadamente más de cuatro veces más rápido que Linq. Eso no es malo. Pero todavía no tan rápido como Array.Sort, pero tampoco mucho peor. Pero esto me sorprendió mucho: esperaba que fuera un poco más lento que Linq en arreglos muy pequeños. Pero luego realicé una prueba con solo 20 elementos:
RadixSort: 00:00:00.0012944
Linq OrderBy: 00:00:00.0072271
Array.Sort: 00:00:00.0002979
e incluso esta vez mi Radixsort es más rápido que Linq, pero camino más lento que la ordenación por matriz. 🙂
Actualización 2:
Hice algunas mediciones más y descubrí algunas cosas interesantes: las constantes de longitud de grupo más largas significan menos iteraciones y más uso de memoria. Si usa una longitud de grupo de 16 bits (solo 2 iteraciones), tiene una gran sobrecarga de memoria al ordenar arreglos pequeños, pero puede vencer Array.Sort si se trata de matrices de más de 100k elementos, aunque no muchos. Los ejes de los gráficos están logaritmizados:
(fuente: daubmeier.de)