¿Hay una buena implementación de radixsort para flotadores en C #

Tengo una estructura de datos con un campo del tipo float. Una colección de estas estructuras debe ser ordenada por el valor del flotador. ¿Hay una implementación de tipo radix para esto?

Si no hay, hay una manera rápida de acceder al exponente, el signo y la mantisa. Porque si ordena los flotadores primero en mantisa, exponente y exponente la última vez. Tu ordenas flota en O (n).

Actualizar:

Estaba muy 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 clasificarlos. Solo tiene que tomar los bits uno a uno y realizar una ordenación int. Solo tiene que preocuparse por los valores negativos, que deben colocarse a la inversa de los positivos al final del algoritmo (lo hice en un solo paso con la última iteración del algoritmo para ahorrar tiempo de CPU).

Así que aquí está mi flotador radixsort:

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 un ordenamiento int radix, debido a que la matriz se copia al principio y al final de la función, donde los flotadores se copian a bit y se devuelven en bits. Sin embargo, toda la función es nuevamente O (n). En cualquier caso, mucho más rápido que clasificar 3 veces seguidas como propusiste. Ya no veo mucho espacio para las optimizaciones, pero si alguien lo hace, 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ín / Máx, 0) y números aleatorios. Array.Sort exactamente el mismo orden que Linq o Array.Sort flotadores:

 NaN -> -Inf -> Min -> Negative Nums -> 0 -> Positive Nums -> Max -> +Inf 

Así que hice una prueba con una gran variedad de números de 10M:

 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 el resultado fue ( actualización: ahora se ejecutó con la versión de lanzamiento, no con la depuración ):

 RadixSort: 00:00:03.9902332 Linq OrderBy: 00:00:17.4983272 Array.Sort: 00:00:03.1536785 

aproximadamente 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 me sorprendió mucho este: esperaba que fuera un poco más lento que Linq en arreglos muy pequeños. Pero luego hice 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 mucho más lento que el ordenamiento en 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 cuando Array.Sort arreglos pequeños, pero puede vencer a Array.Sort si se trata de arreglos de más de 100k elementos, aunque no mucho. Los ejes de los gráficos son logaritmizados:

tabla de comparación http://sofes.miximages.com/c%23/radixsort_vs_arraysort.png

Creo que es mejor apostar si los valores no están demasiado cerca y hay un requisito de precisión razonable, simplemente puede usar los dígitos de flotación reales antes y después del punto decimal para hacer la clasificación.

Por ejemplo, puedes usar los primeros 4 decimales (sean 0 o no) para hacer la clasificación.

Hay una buena explicación de cómo realizar la clasificación de radix en flotadores aquí: http://www.codercorner.com/RadixSortRevisited.htm

Si todos sus valores son positivos, puede salirse con la utilización de la representación binaria; El enlace explica cómo manejar los valores negativos.

Puede usar un bloque unsafe para memcpy o alias un float * para un uint * para extraer los bits.