Здравствуйте. Воткнулся в неприятную проблему и не знаю как ее решить хорошо.
Есть некое множество каких-то структур, которые нужно отсортировать по значению некоторой функции. Казалось бы все просто — std::sort с предикатом. Но проблема в том, что результат вызова этого предиката приближенный (в силу погрешностей fast floating point model), и иногда начинается дребезг, приводящий к тому, что алгоритм сходит с ума и ругается ассертами (я так понимаю, нарушается транзитивность). Как решить данную проблему, не "городя огород" и не получая лишних накладных расходов?
Какие варианты приходят на ум:
1. Предрассчитать значение функции. Это хорошо, но его нужно где-то хранить? Еще один контейнер? Огород. Внести в саму структуру? Нарушение абстракции.
2. Округлять результат. Не решение — аргумент округления может оказаться "на пике", и сваливаться то в одну, то в другую сторону, пускай и с меньшей вероятностью.
3. Включить precise floating point model конкретно в этом месте? А получится ли? Ведь оно может вызывать уже готовый код, который был скомпилирован в быстрой модели.
Что посоветуете?

Здравствуйте, Went, Вы писали:

W>Здравствуйте. Воткнулся в неприятную проблему и не знаю как ее решить хорошо.
W>Есть некое множество каких-то структур, которые нужно отсортировать по значению некоторой функции. Казалось бы все просто — std::sort с предикатом. Но проблема в том, что результат вызова этого предиката приближенный (в силу погрешностей fast floating point model), и иногда начинается дребезг, приводящий к тому, что алгоритм сходит с ума и ругается ассертами (я так понимаю, нарушается транзитивность). Как решить данную проблему, не "городя огород" и не получая лишних накладных расходов?
W>Какие варианты приходят на ум:
W>1. Предрассчитать значение функции. Это хорошо, но его нужно где-то хранить? Еще один контейнер? Огород. Внести в саму структуру? Нарушение абстракции.
W>2. Округлять результат. Не решение — аргумент округления может оказаться "на пике", и сваливаться то в одну, то в другую сторону, пускай и с меньшей вероятностью.
W>3. Включить precise floating point model конкретно в этом месте? А получится ли? Ведь оно может вызывать уже готовый код, который был скомпилирован в быстрой модели.
W>Что посоветуете?

Я за огород.

Здравствуйте, Went, Вы писали:

W>Здравствуйте. Воткнулся в неприятную проблему и не знаю как ее решить хорошо.
W>Есть некое множество каких-то структур, которые нужно отсортировать по значению некоторой функции. Казалось бы все просто — std::sort с предикатом. Но проблема в том, что результат вызова этого предиката приближенный (в силу погрешностей fast floating point model), и иногда начинается дребезг, приводящий к тому, что алгоритм сходит с ума и ругается ассертами (я так понимаю, нарушается транзитивность). Как решить данную проблему, не "городя огород" и не получая лишних накладных расходов?

Т.е. предикат у тебя не является "чистой" функцией и возвращаемое значение может меняться от вызова к вызову для одного и того же объекта?

Здравствуйте, Went, Вы писали:

W>Что посоветуете?

1. Топологическая сортировка вместо обычной.
2. Предвычислить значения функции один раз и запустить сортировку по уже готовым значениям (не знаю, какая именно там fast FP у вас применена, но вряд ли она будет одно и то же сравнение готовых значений делать с разными результатами).

А вообще я не понимаю, как fast FP влияет на это. По идее, одно и то же выражение с теми же аргументами на входе должно дать тот же результат. Fast FP должно влиять на то, что результат операций другой, чем при strict, но сам этот другой результат меняться не должен.

Здравствуйте, andyp, Вы писали:
A>Т.е. предикат у тебя не является "чистой" функцией и возвращаемое значение может меняться от вызова к вызову для одного и того же объекта?
Да, в микроскопических пределах нескольких младших бит float.

Здравствуйте, Went, Вы писали:

W>3. Включить precise floating point model конкретно в этом месте? А получится ли? Ведь оно может вызывать уже готовый код, который был скомпилирован в быстрой модели.
W>Что посоветуете?

ИМХО самый правильный вариант — не сравнивать floating point значения напрямую, а использовать epsilon.

bool comparator(const myType& left, const myType& right)
{
    if (std::abs(left.fpValue - right.fpValue) < epsilon)  //*
    {
        return false;    // Values considered equal
    }
    else
    {
        return left.fpValue < right.fpValue;
    }
}

значение epsilon, естественно, зависит от того, что именно сравнивается.

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

Здравствуйте, T4r4sB, Вы писали:
TB>Я за огород.
Да, я тоже продумал этот вариант. Создаем параллельный массив из пар {результат функции, итератор в исходном массиве}, сортируем его, но потом нам все равно нужно отсортировать исходный массив. Как это сделать, при том, что контейнер — вектор? Точнее, как это сделать хорошо?

Здравствуйте, Went, Вы писали:

W>Есть некое множество каких-то структур, которые нужно отсортировать по значению некоторой функции.

Отсортировать с какой целью?

W>1. Предрассчитать значение функции. Это хорошо, но его нужно где-то хранить? Еще один контейнер? Огород.

Можно отсортировать прямо контейнер с закешированными значениями, в каждом элементе хранить само значение и указатель/индекс. Если потребуется, то можно будет применить эту перестановку к исходному контейнеру.

W>Внести в саму структуру? Нарушение абстракции.

Нормальное решение. Этот вариант может быть самым быстрым (зависит от тяжести операции перемещения), а скорость это очень веский объективный критерий.
Например некоторые алгоритмы работы графами могут требовать от узлов место для хранения дополнительной служебной информации.

W>3. Включить precise floating point model конкретно в этом месте? А получится ли?

Получится. При одинаковых настройках я получал идентичные FP результаты на трёх разных ОС и трёх разных компиляторах.

W>Ведь оно может вызывать уже готовый код, который был скомпилирован в быстрой модели.

Это уже тебе смотреть, какой код там вызывается и как он скомпилирован. На результат также может влиять fpu control word.

P.S. Учти что могут быть всякие NaN'ы и т.п.

Здравствуйте, netch80, Вы писали:
N>А вообще я не понимаю, как fast FP влияет на это. По идее, одно и то же выражение с теми же аргументами на входе должно дать тот же результат. Fast FP должно влиять на то, что результат операций другой, чем при strict, но сам этот другой результат меняться не должен.
Насколько я знаю, нет. Одна из фишек fast FP в том, что она не очищает младшие биты внутренних FP-регистров, загружая в них 32-битные флоаты из памяти. В результате, после проведения операций в этих регистрах, полученная погрешность выползает в значимые биты, и, копируя обратно в 32-битый флоат, мы получаем дребезг.

Здравствуйте, landerhigh, Вы писали:
L>ИМХО самый правильный вариант — не сравнивать floating point значения напрямую, а использовать epsilon.
А разве это не приведет к тем же биениям, только уже на других входных данных? То, что раньше дребезжало, станет однозначным, но то, что было однозначным, отличаясь на величину epsilon, начнет дребезжать?

Здравствуйте, Went, Вы писали:

W>Да, в микроскопических пределах нескольких младших бит float.

Я бы тогда все-таки загрубил бы предикат (или постарался бы сделать его чистым) и использовал какой-нибудь stable_sort, чтобы элементы не скакали по контейнеру при каждой сортировке. Обратная сторона этого — могут появиться равные для предиката элементы, которые логически не равны для других частей программы. Соответственно, что-то может поломаться в тех частях программы, которые ожидают определенного порядка элементов в контейнере.

Здравствуйте, Went, Вы писали:

W>Казалось бы все просто — std::sort с предикатом. Но проблема в том, что результат вызова этого предиката приближенный (в силу погрешностей fast floating point model), и иногда начинается дребезг, приводящий к тому, что алгоритм сходит с ума и ругается ассертами (я так понимаю, нарушается транзитивность).

Как вариант сделать свой алгоритм, который "приблизительно" сортирует. Насколько я вижу quicksort в качестве базы тут подойдёт (естественно без использования трюков типа guard element и т.п.).
Но, опять таки, важно для чего тебе изначально нужна сортировка.

Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>Отсортировать с какой целью?
Ну, передать в другой алгоритм, требующий подготовленных данных.

EP>Можно отсортировать прямо контейнер с закешированными значениями, в каждом элементе хранить само значение и указатель/индекс. Если потребуется, то можно будет применить эту перестановку к исходному контейнеру.
А как применить эту перестановку? Делать еще одну сортировку, предикат которой будет иметь линейную сложность (поиск индекса элемента в отсортированном множестве) как-то не улыбается. Хотя и возможно

EP>Получится. При одинаковых настройках я получал идентичные FP результаты на трёх разных ОС и трёх разных компиляторах.
EP>Это уже тебе смотреть, какой код там вызывается и как он скомпилирован. На результат также может влиять fpu control word.
Нужно будет асм посмотреть — взведется ли что-то или нет.

EP>P.S. Учти что могут быть всякие NaN'ы и т.п.
В моем случае — вряд ли

Здравствуйте, Went, Вы писали:

W>Что посоветуете?

1, а если таки можно оценить степень грубости, при которой шум из младших разрядов не прилезет уже, то можно гранулировать/округлить результат...

Здравствуйте, andyp, Вы писали:

A>Я бы тогда все-таки загрубил бы предикат (или постарался бы сделать его чистым) и использовал какой-нибудь stable_sort, чтобы элементы не скакали по контейнеру при каждой сортировке. Обратная сторона этого — могут появиться равные для предиката элементы, которые логически не равны для других частей программы. Соответственно, что-то может поломаться в тех частях программы, которые ожидают определенного порядка элементов в контейнере.

Там тоже можно этот предикат использовать...

Здравствуйте, Went, Вы писали:

W>Ну, передать в другой алгоритм, требующий подготовленных данных.
А предикат, исполнения которого требует тот, другой алгоритм недоступен?..

Здравствуйте, landerhigh, Вы писали:

L>ИМХО самый правильный вариант — не сравнивать floating point значения напрямую, а использовать epsilon.

Нельзя. Предикат приближённого сравнения не удовлетворяет аксиоматике строгого порядка. В частности, он нетранзитивен: x-e = x = x+e, x-e < x+e.

Здравствуйте, Went, Вы писали:

W>Здравствуйте, netch80, Вы писали:
N>>А вообще я не понимаю, как fast FP влияет на это. По идее, одно и то же выражение с теми же аргументами на входе должно дать тот же результат. Fast FP должно влиять на то, что результат операций другой, чем при strict, но сам этот другой результат меняться не должен.
W>Насколько я знаю, нет. Одна из фишек fast FP в том, что она не очищает младшие биты внутренних FP-регистров, загружая в них 32-битные флоаты из памяти.

Если речь именно про FPU, то загрузка fldl или flds вместо полной длины с fldt автоматически расширяет загруженное до полных 80 бит. Сам Intel явно пишет: "If the source operand is in single-precision or double-precision floating-point format, it is automatically converted to the double extended-precision floating-point format before being pushed on the stack." То есть если подмешивание мусора и происходит, то это не в процессоре.

Здравствуйте, Went, Вы писали:

W>Здравствуйте, landerhigh, Вы писали:
L>>ИМХО самый правильный вариант — не сравнивать floating point значения напрямую, а использовать epsilon.
W>А разве это не приведет к тем же биениям, только уже на других входных данных? То, что раньше дребезжало, станет однозначным, но то, что было однозначным, отличаясь на величину epsilon, начнет дребезжать?

Хмм.. есть такой риск, да.
У тебя несколько иная проблема, нежели та, о которой я подумал.
Тогда можно перейти к фиксированной точке, не вариант?
Или, если реально предрасчитать значения функции, то лучше так и сделать. Где хранить? Можно flyweight попробовать прямо из буста

Здравствуйте, Went, Вы писали:

W>Насколько я знаю, нет. Одна из фишек fast FP в том, что она не очищает младшие биты внутренних FP-регистров, загружая в них 32-битные флоаты из памяти. В результате, после проведения операций в этих регистрах, полученная погрешность выползает в значимые биты, и, копируя обратно в 32-битый флоат, мы получаем дребезг.

Кстати, ЕМНИП, есть еще прикол. По крайней мере, компилятор студии не сохраняет и не восстанавливае флаги сопроцессоа в прологе и эпилоге функции. Нашел это, когда искал баг в boost::context
Не знаю, правда, какой эффект это будет иметь