Можно ли сортировать числа с плавающей запятой IEEE754 по старшинству?
Я проделал некоторые низкоуровневые манипуляции с битами и в итоге создал алгоритм, который сортирует 64-битные числа с плавающей запятой по октетам убывания значимости (LE = 7 -> 0; BE = 0 -> 7) в качестве побочного продукта. При регистрации вывода я ожидал произвольного порядка. Однако, к моему некоторому удивлению, они были отсортированы (с оговоркой, что отрицательные числа располагаются после положительных)! Вот пример неявной сортировки случайных чисел с плавающей запятой (-50, 50):
[
4.2217695176666155,
4.6478025698022165,
25.500103628472857,
26.819343028582594,
43.402122471148246,
44.150586938484324,
-12.313937254813531,
-21.429343402208257,
-27.2049115791126,
-38.48913575841195
]
Мне было интересно, в какой степени эти результаты являются совпадением или вычислительной истиной, потому что было бы удобно полагаться на сортировку этих данных. Я также понимаю, что это очень похоже на поразрядную сортировку, но, как упоминалось ранее, я понимаю, что мантисса произвольна по отношению к порядку чисел.
Вот класс TS, который демонстрирует такое поведение, и ниже показано, как я его тестирую.
const ns = new NumberSet();
for (let i=0; i < 10; i++) {
ns.add(100 * Math.random() - 50);
}
for (let n of ns) console.info(n);
Вам также следует протестировать его с числами меньше единицы. Нули со знаком =0 и -0, очевидно, будут находиться далеко друг от друга, но остальные должны быть в монотонном порядке (сначала наименьшая величина). Вы можете поиграть с этим на конвертере IEEE754, чтобы понять, почему это работает.
Ваш код выглядит довольно чистым. Я бы на вашем месте тоже разместил вопрос здесь.
@MartinBrown Я могу подтвердить, что шаблон нарушается для чисел меньше 0. Одного этого достаточно, чтобы отговорить меня полагаться на такое поведение, но все равно было бы интересно услышать идеи о том, что является причиной этого.
@MartinBrown Неважно, я как-то неправильно прочитал вывод. При более чем 5 запусках Math.random() * (Math.random() < 0.5 ? 1 : -1) сортируется таким же образом.
@user24714692 Кросс-постинг завершен, спасибо за рекомендацию: codereview.stackexchange.com/questions/292921/…
Ответы 2
Вы можете «сравнивать» числа с плавающей запятой, используя лексикографический порядок, т. е. рассматривать сохраненные биты как строку или целое число без знака, если вы сделаете следующее:
- Проверьте наличие NaN. Если да, то процедура неприменима. Прервать. (NaN не сравниваются с другими, включая самих себя, результат сравнения всегда ложный, независимо от того, равен ли он или больше/меньше и т. д.)
- Если отрицательный ноль, то воспринимайте его как положительный 0 (т. е. меняйте знаковый бит).
- Если отрицательно, переверните все биты (включая знаковый бит).
- В противном случае переверните только знаковый бит (остальные биты оставьте прежними).
Вышеупомянутое предполагает, что у вас нет значений NaN, следовательно, шаг 1 выше. При условии, что это так, и вы примените вышеуказанное преобразование, вы сможете сравнить два числа с плавающей запятой как целочисленные значения без знака (или лексикографически, если хотите), и результатом будет правильный порядок исходных чисел с плавающей запятой. Это верно даже при наличии бесконечностей, как положительных, так и отрицательных, что приводит к правильной семантике сравнения, соответствующей стандарту IEEE754.
В частности, причина, по которой экспоненты с плавающей запятой хранятся со смещением, заключается именно в том, что вы можете проделать этот трюк, то есть сравнения становятся проще. То, что вы делаете, по сути, использует эту структуру, и поэтому результат, который получается в вашем случае, неудивителен.
Большое спасибо! Мне нужно будет посмотреть, будет ли отслеживание NaN и переключение -0 (есть ли у кого-нибудь способ обнаружить это? JS говорит 0 === -0) быстрее, чем встроенная сортировка. Хорошо, что есть подтверждение :)
Мы игнорируем знак 0 на шаге 2 именно потому, что 0 == -0. Однако я не ожидал, что этот трюк будет быстрее, чем нативная сортировка; потому что, скорее всего, само сравнение компилируется в HW-инструкцию, которая будет выполняться довольно быстро. (См. felixcloutier.com/x86/fcom:fcomp:fcompp)
Предполагая, что у ОП все в порядке с сортировкой "-NaN" < -inf < negative number < -0 < +0 < positive number < +inf < "+NaN", они могут пропустить шаги 1 и 2.
@chtz Действительно. Но это также будет отличать NaN: разные полезные нагрузки приведут к их разному упорядочению. Вероятно, это не проблема, но о чем следует помнить.
Если используемый язык позволяет манипулировать битами и не предполагает NAN, то вы можете обрабатывать числа с плавающей точкой аналогично числам знак + величина и использовать эти битовые операции без каких-либо условных операторов для преобразования знака + величины в целое число без знака и обратно. Обратите внимание, что при этом -0,0 считается меньшим, чем +0,0. Использование синтаксиса C:
a[i] ^= ((uint32_t)((int32_t)( a[i])>>31)>>1)|0x80000000ul; /* convert to unsigned */
Выполните сортировку целых чисел без знака (например, поразрядную сортировку).
a[i] ^= ((uint32_t)((int32_t)(~a[i])>>31)>>1)|0x80000000ul; /* convert back */
@user24714692 user24714692 Я добавил это в исходное сообщение.