У меня есть datastructure с полем типа плавающего. Набор этих структур должен быть отсортирован по значению плавания. Есть ли реализация вида основания для этого.
Если нет, там быстрый способ получить доступ к экспоненте, знаку и мантиссе. Поскольку, если Вы сортируете плавания сначала на мантиссе, экспоненте, и на экспоненте в прошлый раз. Вы сортируете плавания в O (n).
Обновление:
Меня очень заинтересовала эта тема, поэтому я сел и реализовал ее (используя эту очень быструю и консервативную реализацию ). Я также прочитал этот (спасибо celion ) и обнаружил, что вам даже не нужно разбивать числа с плавающей запятой на мантиссу и экспоненту, чтобы отсортировать их. Вам просто нужно взять биты один к одному и выполнить сортировку int. Вам просто нужно позаботиться об отрицательных значениях, которые должны быть обратно поставлены перед положительными в конце алгоритма (я сделал это за один шаг с последней итерацией алгоритма, чтобы сэкономить некоторое время процессора).
Вот моя поразрядная сортировка с плавающей запятой:
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;
}
Она немного медленнее, чем сортировка по основанию int, из-за копирования массива в начале и в конце функции, где числа с плавающей запятой побитово копируются в целые числа и обратно. Тем не менее, вся функция снова O (n). В любом случае намного быстрее, чем сортировка 3 раза подряд, как вы предлагали. Я больше не вижу много возможностей для оптимизации, но если кто-то это сделает: не стесняйтесь сказать мне.
Чтобы отсортировать по убыванию, измените эту строку в самом конце:
ret[i] = BitConverter.ToSingle(BitConverter.GetBytes(a[i]), 0);
на это:
ret[a.Length - i - 1] = BitConverter.ToSingle(BitConverter.GetBytes(a[i]), 0);
Измерение:
Я создал небольшой тест, содержащий все специальные случаи с плавающей запятой (NaN, +/- Inf, Min / Максимальное значение, 0) и случайные числа. Он сортирует в точности тот же порядок, что и Linq или Array.Sort
сортирует числа с плавающей запятой:
NaN -> -Inf -> Min -> Negative Nums -> 0 -> Positive Nums -> Max -> +Inf
Итак, я провел тест с огромным массивом из 10 миллионов чисел:
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; }
}
}
И остановил время различных алгоритмов сортировки:
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));
Результат был ( обновление: теперь выполняется с выпуском сборки, а не с отладкой ):
RadixSort: 00:00:03.9902332
Linq OrderBy: 00:00:17.4983272
Array.Sort: 00:00:03.1536785
примерно в четыре раза быстрее, чем Linq. Это неплохо. Но все еще не так быстро, как Array.Sort
, но и не намного хуже. Но меня это очень удивило: я ожидал, что он будет немного медленнее, чем Linq на очень маленьких массивах. Но затем я провел тест всего с 20 элементами:
RadixSort: 00:00:00.0012944
Linq OrderBy: 00:00:00.0072271
Array.Sort: 00:00:00.0002979
и даже на этот раз мой Radixsort быстрее, чем Linq, но способом медленнее, чем сортировка по массиву. :)
Обновление 2:
Я провел еще несколько измерений и обнаружил кое-что интересное: более длинные константы длины группы означают меньше итераций и больше использования памяти.Если вы используете длину группы в 16 бит (всего 2 итерации), у вас будут огромные накладные расходы на память при сортировке небольших массивов, но вы можете превзойти Array.Sort
, если речь идет о массивах, размер которых превышает примерно 100 тыс. Элементов, даже если не очень. Обе оси диаграммы логарифмированы:
(источник: daubmeier.de )
Здесь есть хорошее объяснение того, как выполнять сортировку по основанию с плавающей запятой: http://www.codercorner.com/RadixSortRevisited.htm
Если все ваши значения положительны, вы можете уйти от использования двоичного представления; ссылка объясняет, как обрабатывать отрицательные значения.
Думаю, ваш Лучше всего, если значения не слишком близки и есть разумные требования к точности, вы можете просто использовать фактические цифры с плавающей запятой до и после десятичной точки для сортировки.
Например, вы можете просто использовать первые 4 десятичных знака (0 или нет) для сортировки.
Вы можете использовать блок unsafe
для memcpy или использовать псевдоним float *
для uint *
для извлечения битов.