Если для сортировки массива чисел с плавающей точкой использовать компаратор наподобие следующего (здесь и далее все примеры на C++):
bool Compare(const double &a, const double &b)
{
return a - b > 0.0;
}
то проблемы возникнуть могут.
Во-первых, массив исходных данных может содержать "нечисла" (Not-a-Number, NaN
). NaN
является неупорядоченным (unordered) по отношению к любым другим числам с плавающей точкой, включая самого себя. Это означает, что если по крайней мере один операнд бинарных операторов <
, <=
, ==
, >=
, >
— NaN
, то результат сравнения false
; если по крайней мере один из операндов бинарного оператора !=
— NaN
, то результат сравнения true
(стоит заметить, что согласно стандарту вычислений с плавающей точкой IEEE 754-2008, операторы сравнения могут генерировать исключение в случае, если по крайней мере один из операндов — NaN
).
NaN
также характеризуется особой арифметикой. Например, если по крайней мере один из операндов бинарного -
— NaN
, то результат NaN
.
Такие свойства NaN
'ов в совокупности с представленным выше компаратором могут отрицательно сказаться на результатах сортировки. Для примера рассмотрим сортировку вставками (Пример):
void InsertionSort(vector<double> &vect)
{
for (size_t i = 1; i < vect.size(); ++i)
for (size_t j = i; j > 0 && Compare(vect[j], vect[j - 1]); --j)
swap(vect[j], vect[j - 1]);
}
Ни один элемент массива {1.0, NaN, 2.0, NaN, 1.0}
после такой сортировки не будет перемещён. На каждой итерации цикла i
при помощи функции Compare
будет сравниваться пара чисел с плавающей точкой. И каждый раз в этой паре будет присутствовать NaN
. И каждый раз результат сравнения будет false
, а значит не будет произведено ни одного обмена элементов вектора.
Второй пример связан с денормализованными (субнормальными) числами.
Если бы удалось подобрать два таких числа a
и b
, что a > b
, но a - b == 0
, то возникли бы проблемы с сортировкой. Ведь a
больше b
, но компаратор говорит, что a
не больше b
, а значит алгоритм сортировки не обязан менять числа a
и b
местами.
Википедия говорит, что в формате IEEE 754-2008 разность двух неравных, но близких друг к другу чисел, не бывает равна нулю. И обеспечивается это, отчасти, благодаря денормализованным числам.
Взглянем повнимательнее на числа с плавающей точкой двойной точности. А именно на минимальное положительное нормализованное число (min
), число следующее непосредственно за предыдущим (в сторону единицы, min_1
), разность двух предыдущих (diff = min_1 - min
) и минимальное положительное денормализованное число (denorm_min
):
min == 2.22507385850720138e-308
min_1 == 2.22507385850720188e-308
diff == 4.94065645841246544e-324
denorm_min == 4.94065645841246544e-324
Можно заметить, что разность двух нормализованных чисел представляет собой денормализованное значение.
Некоторые процессоры (в частности, с поддержкой SSE2), позволяют сбрасывать до нуля (flush to zero) результат арифметического выражения, если он денормализованный. Т.е. в данном конкретном случае, разность двух нормализованных, неравных чисел min
и min_1
вполне может получится равной нулю, а значит можно сконструировать пример некорректной сортировки.
Воспользуемся Visual Studio, функцией _controlfp_s и напишем небольшой пример:
#include <iostream>
#include <limits>
#include <cmath>
#include <float.h>
#include <vector>
#include <algorithm>
using namespace std;
#pragma fenv_access (on)
bool Compare(const double &a, const double &b)
{
return a - b > 0.0;
}
int main()
{
double min = numeric_limits<double>::min();
double min_1 = nextafter(min, 1.0);
vector<double> v = {min, min_1, min, 1.0, 2.0};
_controlfp_s(nullptr, _DN_FLUSH, _MCW_DN);
sort(v.begin(), v.end(), Compare);
for (auto val : v)
cout << val << " ";
cout << endl;
}
Вектор до сортировки:
2.22507385850720138e-308 2.22507385850720188e-308 2.22507385850720138e-308 1.0 2.0
Вектор после сортировки:
2.0 1.0 2.22507385850720138e-308 2.22507385850720188e-308 2.22507385850720138e-308
Хоть пример довольно таки надуманный, но не невозможный на практике (особенно с учетом того, что судя по документации, некоторые компиляторы по-умолчанию включают опцию flush to zero на всех уровнях оптимизации, больших чем -O0).