<float_sort>- это быстрый шаблонный алгоритм гибридного радикса / сравнения, очень похожий на<integer_sort>, но сортирует числа с плавающей точкой IEEE (положительные, нулевые, NaN и отрицательные) в восходящий порядок, отбрасывая их в целые числа. Это работает потому, что положительные числа с плавающей точкой IEEE сортируются как целые числа с одинаковыми битами, а отрицательные числа с плавающей точкой IEEE сортируются в обратном порядке целых чисел с одинаковыми битами. float_sort примерно в 2 раза быстрее, чем std::sort.

-0,0 vs. 0.0 и NaN получают определенные упорядоченные позиции на основе радикса, где сортировка на основе сравнения не гарантирует их относительное положение. Включенные тесты избегают создания NaN и -0.0, чтобы результаты соответствовали std::sort, что не согласуется с тем, как он обрабатывает эти числа, поскольку они сравниваются как равные числам с различными значениями.

float_sort проверяет размер типа данных и является ли он литейным, выбирая целочисленный тип для литья, если пользователь не предоставляет функтор литья.

float_mem_cast отбрасывает числа IEEE с плавающей точкой (положительные, нулевые, NaN и отрицательные) в целые числа. Это важная утилита для создания пользовательского функтора правого смещения для float_sort, когда он нужен. Только числа с плавающей запятой IEEE того же размера, что и отлитый целочисленный тип, должны использоваться в этом специализированном вызове метода. Наихудшая производительность& #119926; (N * (log2 (диапазон) / с + с)), так что<float_sort>асимптотически быстрее, чем чистые алгоритмы на основе сравнения.smax_splits, который по умолчанию 11, поэтому его худший случай с настройками по умолчанию для 32-битных целых чисел& #119926; (N * ((32/11))медленные итерации на основе радикса + 11 быстрых итераций на основе сравнения.

Некоторые графики производительности runtime vs. n и log2(range) приведены ниже:

Windows Float Sort

OSX Float Sort

#define CAST_TYPE int
#define KEY_TYPE float

struct DATA_TYPE {
    KEY_TYPE key;
    std::string data;
};

// Casting to an integer before bitshifting
struct rightshift {
  int operator()(const DATA_TYPE &x, const unsigned offset) const {
    return float_mem_cast<KEY_TYPE, CAST_TYPE>(x.key) >> offset;
  }
};

struct lessthan {
  bool operator()(const DATA_TYPE &x, const DATA_TYPE &y) const {
    return x.key < y.key;
  }
};