C'è un buon radix sort-implementazione per i galleggianti in C #
-
30-09-2019 - |
Domanda
Ho un datastructure con un campo del galleggiante tipo. Una raccolta di queste strutture deve essere risolto in base al valore del flottante. C'è un'implementazione Radix-ordinamento per questo.
Se non c'è, c'è un modo veloce per accedere al esponente, il segno e la mantissa. Perché se si ordina I galleggianti prima a mantissa, esponente, e l'esponente l'ultima volta. Si ordina galleggia in O (n).
Soluzione
Aggiornamento:
Sono stato molto interessato a questo argomento, così mi sono seduto e implementato (usando questo molto veloce e la memoria conservatore implementazione ). Ho letto anche questo (grazie Celion ) e scoperto che avete anche Dont di dividere i carri in mantissa ed esponente di risolvere. Devi solo prendere i bit one-to-one e di eseguire un int sorta. Non vi resta che preoccupano i valori negativi, che devono essere inversamente messo di fronte a quelli positivi alla fine dell'algoritmo (ho fatto che in un solo passo con l'ultima iterazione dell'algoritmo per risparmiare un po 'di tempo CPU).
Così heres il mio float radix sort:
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;
}
E 'leggermente più lento di un int ordinamento digitale, a causa della matrice copiare all'inizio e alla fine della funzione, dove i galleggianti sono bitwise copiati int e indietro. L'intera funzione tuttavia è ancora O (n). In ogni caso, molto più veloce di smistamento 3 volte di seguito come avete proposto. Non vedo molto spazio per le ottimizzazioni più, ma se qualcuno lo fa:. Sentitevi liberi di dire
Per ordine decrescente cambiare questa riga alla fine:
ret[i] = BitConverter.ToSingle(BitConverter.GetBytes(a[i]), 0);
a questo:
ret[a.Length - i - 1] = BitConverter.ToSingle(BitConverter.GetBytes(a[i]), 0);
di misura:
Ho messo su qualche breve test, che contiene tutti i casi particolari di carri (NaN, Inf +/-, il valore Min / Max, 0) e numeri casuali. Si ordina esattamente nello stesso ordine come Linq o Array.Sort
ordinamenti galleggianti:
NaN -> -Inf -> Min -> Negative Nums -> 0 -> Positive Nums -> Max -> +Inf
Così ho eseguito un test con una vasta gamma di numeri 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; }
}
}
E fermato il tempo dei vari algoritmi di ordinamento:
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));
E l'uscita è stata ( Aggiornamento: ora correva con build di rilascio, non debug ):
RadixSort: 00:00:03.9902332
Linq OrderBy: 00:00:17.4983272
Array.Sort: 00:00:03.1536785
all'incirca più di quattro volte più veloce di LINQ. Che non è male. Ma ancora non è ancora così veloce come Array.Sort
, ma anche non molto peggio. Ma ero davvero sorpreso da questo: mi aspettavo che fosse un po 'più lento di Linq su molto piccoli array. Ma poi ho eseguito un test con soli 20 elementi:
RadixSort: 00:00:00.0012944
Linq OrderBy: 00:00:00.0072271
Array.Sort: 00:00:00.0002979
e anche questa volta il mio radix sort è più veloce di Linq, ma via più lento rispetto sorta di matrice. :)
Aggiornamento 2:
Ho fatto alcuni più misure e ha scoperto alcune cose interessanti: più costanti di lunghezza gruppo significano meno iterazioni e più l'uso della memoria. Se si utilizza una lunghezza gruppo di 16 bit (solo 2 iterazioni), si ha un enorme overhead di memoria durante l'ordinamento piccoli array, ma si può battere Array.Sort
se si tratta di matrici superiori a circa 100k elementi, anche se non molto. Gli assi grafici sono entrambi logarithmized:
(fonte: daubmeier.de )
Altri suggerimenti
C'è una bella spiegazione di come eseguire radix sort su galleggianti qui: http://www.codercorner.com/RadixSortRevisited.htm
Se tutti i valori sono positivi, si può farla franca usando la rappresentazione binaria; il link spiega come gestire i valori negativi.
È possibile utilizzare un blocco unsafe
a memcpy o alias un float *
ad un uint *
per estrarre i bit.
Per fare un po 'di fantasia casting e scambiando array invece di copiare questa versione è 2 volte più veloce per i numeri 10 milioni come Philip Daubmeiers originale con il set grouplength a 8. Si tratta di 3 volte più veloce come Array.Sort per quella arraysize.
static public void RadixSortFloat(this float[] array, int arrayLen = -1)
{
// Some use cases have an array that is longer as the filled part which we want to sort
if (arrayLen < 0) arrayLen = array.Length;
// Cast our original array as long
Span<float> asFloat = array;
Span<int> a = MemoryMarshal.Cast<float, int>(asFloat);
// Create a temp array
Span<int> t = new Span<int>(new int[arrayLen]);
// set the group length to 1, 2, 4, 8 or 16 and see which one is quicker
int groupLength = 8;
int bitLength = 32;
// counting and prefix arrays
// (dimension is 2^r, the number of possible values of a r-bit number)
var dim = 1 << groupLength;
int groups = bitLength / groupLength;
if (groups % 2 != 0) throw new Exception("groups must be even so data is in original array at end");
var count = new int[dim];
var pref = new int[dim];
int mask = (dim) - 1;
int negatives = 0, positives = 0;
// counting elements of the 1st group incuding negative/positive
for (int i = 0; i < arrayLen; i++)
{
if (a[i] < 0) negatives++;
count[(a[i] >> 0) & mask]++;
}
positives = arrayLen - negatives;
int c;
int shift;
for (c = 0, shift = 0; c < groups - 1; c++, shift += groupLength)
{
CalcPrefixes();
var nextShift = shift + groupLength;
//
for (var i = 0; i < arrayLen; i++)
{
var ai = a[i];
// Get the right index to sort the number in
int index = pref[( ai >> shift) & mask]++;
count[( ai>> nextShift) & mask]++;
t[index] = ai;
}
// swap the arrays and start again until the last group
var temp = a;
a = t;
t = temp;
}
// Last round
CalcPrefixes();
for (var i = 0; i < arrayLen; i++)
{
var ai = a[i];
// Get the right index to sort the number in
int index = pref[( ai >> shift) & mask]++;
// 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 ( ai < 0) index = positives - (index - negatives) - 1; else index += negatives;
//
t[index] = ai;
}
void CalcPrefixes()
{
pref[0] = 0;
for (int i = 1; i < dim; i++)
{
pref[i] = pref[i - 1] + count[i - 1];
count[i - 1] = 0;
}
}
}
Credo che la soluzione migliore se i valori non sono troppo vicini e c'è un requisito ragionevole precisione, si può semplicemente utilizzare le cifre effettive galleggiante, prima e dopo la virgola per fare l'ordinamento.
Per esempio, si può semplicemente utilizzare i primi 4 decimali (siano essi 0 o meno) di fare l'ordinamento.