Здравствуйте. Воткнулся в неприятную проблему и не знаю как ее решить хорошо.
Есть некое множество каких-то структур, которые нужно отсортировать по значению некоторой функции. Казалось бы все просто — 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
Не знаю, правда, какой эффект это будет иметь

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

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

Это понятно, а что он примерно будет делать? Например если какой-нибудь двоичный поиск, то опять нужны старые значения ключей.

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

1. Создать ещё один массив и переместить в него элементы из первого, в соответствии с перестановкой.

2. Перетасовать элементы inplace следуя циклам перестановки.
Например: перемещаешь первый элемент исходного массива в temp, смотришь по индексу какой элемент должен быть первым, например k1, перемещаешь его на место первого, смотришь какой элемент должен быть на месте k1-го элемента — k2, и перемещаешь его на место k1, и т.д. этот цикл должен замкнутся на первом элементе, и тогда перемещаешь первоначальный temp в конец цепочки. После этого переходишь к следующему циклу, и так до конца. Следующий цикл например можно определить по не посещённым индексам.

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

Да, я в runtime устанавливал ASM'ом. Но как-то потом наткнулся на соответствующие интринсинки, то есть можно без ASM.

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

Хотя бы за-assert'ить тогда.

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

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

В случае со структурами — предрасчёт и внешний контейнер — это, возможно, лучшее решение.
Потому что радикально экономится время и на сравнения, и на обмены.

Тем более, если функция нахождения ключа дребезжит, значит, она не слишком простая. O(n) вызовов на мемоизацию против O(nlogn) на вычисления на ходу, с коэффицентом умножения "тормоза в функции".
Если данных много, то ещё и кешмиссы прибавятся за счёт хаотичного доступа.

std::vector< YourStruct > ds;
float key(YourStruct const&);

size_t const n = ds.size();

std::vector< std::pair<float,size_t> > ps(n);
for(size_t i = 0; i < n; ++i) ps[i] = std::make_pair(key(ds[i]),i);

std::sort(ps.begin(), ps.end()); // заодно нахаляву получили стабильную сортировку.

// перестановка копированием (перестановку по месту писать дольше)
std::vector< YourStruct > sds;
for(size_t i = 0; i < n; ++i) sds.push_back(ds[ps[i].second]);
sds.swap(ds);

W>2. Округлять результат. Не решение — аргумент округления может оказаться "на пике", и сваливаться то в одну, то в другую сторону, пускай и с меньшей вероятностью.

Округлять результат, обнуляя именно два-три последних дребезжащих разряда.
Ты же сам говоришь, что функция "дышит", что это ошибки вычислений. Ну так какая разница, функция свалится по собственной инициативе, или под твоим руководством?

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

Из пушки по воробьям, да ещё и платформо-зависимо. Поменяется платформа или компилятор, всё опять перекосится.

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

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

TB>Я за огород.

Не сработает. Транзитивности не будет.

Здравствуйте. Спасибо всем за помощь.
Короче, пока что решил проблему так: входные данные срезаю, прямо приводя к int (это действие не должно дребезжать, ИМХО), и все вычисления делаю в целых (тоже не дребезжит). Есть опасность вылететь за разрядность целого, но вроде не должен.

Здравствуйте, landerhigh, Вы писали:
L>Тогда можно перейти к фиксированной точке, не вариант?
Да, в общем, вариант. Мне даже фиксед не нужен, хватит точности целого с головой.

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

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

У вас скорее всего все трещит не из-за модели fp, а из-за приблизительности предиката. Модель fp влияет на вычисления, а не на результат сравнения даблов на больше\меньше\равно. Я так понял, что внутри предиката вы делаете вычисления, от них надо избавиться (это ваш вариант 1). Чтобы проблем не было, надо использовать точный предикат, а именно сравнивать уже вычисленные даблы точно (чтобы предикат удовлетворял всем правилам). При этом у вас с сортировкой проблем не должно быть.
Можно поразмыслить над сортировкой сразу двух векторов: в одном данные, а во втором значения, которые используются в предикате. Первое, что нагуглилось: http://stackoverflow.com/questions/9343846/boost-zip-iterator-and-stdsort

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

L>>ИМХО самый правильный вариант — не сравнивать floating point значения напрямую, а использовать epsilon.
К>Нельзя. Предикат приближённого сравнения не удовлетворяет аксиоматике строгого порядка. В частности, он нетранзитивен: x-e = x = x+e, x-e < x+e.

Хм... иными словами, в принципе сортировать контейнер, используя приближенное сравнение — плохая идея в общем случае?

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

L>Хм... иными словами, в принципе сортировать контейнер, используя приближенное сравнение — плохая идея в общем случае?

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

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

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

Ну да, всё верно, если в векторе жирные данные, то лучше сортировать указатели (или индексы), а не сами элементы.
А дальше надо выполнить перестановку. Это делается за ЭН свапов. У тебя в этом вопрос?

Ну надо подумать... Например найди обратную перестановку (тоже о от эн). Потом начни "править" обратную, ну типа если видишь на 1м месте число 5, то меняй 1й и 5й (обновременно меняя и те же элементы из вектора).

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

К>> Предикат приближённого сравнения не удовлетворяет аксиоматике строгого порядка.

L>сортировать контейнер, используя приближенное сравнение — плохая идея в общем случае?

С stl алгоритмами — да, плохая. В них существенно используется факт, что предикат задаёт strict weak ordering.
Если повезёт, то программа просто упадёт по segfault или сработает assert (как и было у автора в исходном сообщении).
Если не повезёт, то сортировка выдаст чушь, молча повредит данные (в том числе и за пределами сортируемого участка), или, потенциально, каким-то другим образом проявит своё неопределённое поведение.

В то же время, приближенное сравнение вполне можно использовать в других контекстах. Например, выше уже упомянули топологическую сортировку. С этим семейством алгоритмов приближенное сравнение будет работать, и даже будет выдавать некий осмысленный результат. Другое дело, что нужно понимать чем сортировка отличается от топологической сортировки — в некотором узком смысле это просто разные алгоритмы с похожим названием.

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

TB>>Я за огород.

К>Не сработает. Транзитивности не будет.

Сфигали? Предвычисленные значения можно загрубить, чтоб точно сравнивалось одинаково.

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

W>С stl алгоритмами — да, плохая. В них существенно используется факт, что предикат задаёт strict weak ordering.
W>Если повезёт, то программа просто упадёт по segfault или сработает assert (как и было у автора в исходном сообщении).
W>Если не повезёт, то сортировка выдаст чушь, молча повредит данные (в том числе и за пределами сортируемого участка), или, потенциально, каким-то другим образом проявит своё неопределённое поведение.

Я как-то видел такое, программа просто зацикливалась на сортировке. Но, конечно, гарантии этого нет.

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

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

Я тоже так думал)
Нет, не должно. Потому что в одной строчке оно может вычислить аргументы, которые сидели в 10-байтовых регистрах сопроцессора и только что прошли через некий алгоритм (не вылезая из регистров благодаря оптимизатору), потом положит их в память в 4х-байтовые ячейки, обрезав биты, а потом в другом месте он эти аргументы уже достанет из памяти и обрезанном виде и получит другой результат. Я помню, хорошую граблю словил, долго не мог понять, вдвоём неделю баг искали.

N>Fast FP должно влиять на то, что результат операций другой, чем при strict, но сам этот другой результат меняться не должен.

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

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

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

TB>Я тоже так думал)
TB>Нет, не должно. Потому что в одной строчке оно может вычислить аргументы, которые сидели в 10-байтовых регистрах сопроцессора и только что прошли через некий алгоритм (не вылезая из регистров благодаря оптимизатору), потом положит их в память в 4х-байтовые ячейки, обрезав биты, а потом в другом месте он эти аргументы уже достанет из памяти и обрезанном виде и получит другой результат. Я помню, хорошую граблю словил, долго не мог понять, вдвоём неделю баг искали.

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

Здравствуйте, uzhas, Вы писали:
U>У вас скорее всего все трещит не из-за модели fp, а из-за приблизительности предиката. Модель fp влияет на вычисления, а не на результат сравнения даблов на больше\меньше\равно. Я так понял, что внутри предиката вы делаете вычисления, от них надо избавиться (это ваш вариант 1). Чтобы проблем не было, надо использовать точный предикат, а именно сравнивать уже вычисленные даблы точно (чтобы предикат удовлетворял всем правилам). При этом у вас с сортировкой проблем не должно быть.
Сам по себе предикат формально однозначен — он сравнивает квадраты расстояний между точками и некой опорной точкой. Та, что ближе — та раньше. Просто квадраты разностей координат, все. Поэтому дело в fp. Симметричная сортировка звучит интересно.

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

К>>Не сработает. Транзитивности не будет.
TB>Сфигали? Предвычисленные значения можно загрубить, чтоб точно сравнивалось одинаково.

Упс. Неправильно понял условие. Спасибо.

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

W>Сам по себе предикат формально однозначен — он сравнивает квадраты расстояний между точками и некой опорной точкой. Та, что ближе — та раньше. Просто квадраты разностей координат, все. Поэтому дело в fp. Симметричная сортировка звучит интересно.

А сами точки даблы? Просто если целые, или как-то гранулированы хотя бы, не понятно, как тут может возникать дребезг?

И что с предикатом того алгоритма для которого готовишь данные?
Он-то чего на самом деле требует? Вдруг ты так отсортируешь, а у него там внутри дребезг приключится?..

Здравствуйте, Erop, Вы писали:
E>А сами точки даблы? Просто если целые, или как-то гранулированы хотя бы, не понятно, как тут может возникать дребезг?
Сами точки — флоаты, никак не гранулированы.

E>И что с предикатом того алгоритма для которого готовишь данные?
E>Он-то чего на самом деле требует? Вдруг ты так отсортируешь, а у него там внутри дребезг приключится?..
Не совсем понял, где тут предикат второго алгоритма. Второй алгоритм на входе получает отсортированную последовательность точек и считает вероятность коллизии некого объекта с этими точками. Следующий алгоритм это все рисует или использует для нужд ИИ.

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

W>Сами точки — флоаты, никак не гранулированы.
Ну, флоаты сами по себе гранулированы, относительно даблов. Просто неудобно.
Но можно же их гранулировать насильно, как часть твоей функции?

E>>Он-то чего на самом деле требует? Вдруг ты так отсортируешь, а у него там внутри дребезг приключится?..
W>Не совсем понял, где тут предикат второго алгоритма. Второй алгоритм на входе получает отсортированную последовательность точек и считает вероятность коллизии некого объекта с этими точками. Следующий алгоритм это все рисует или использует для нужд ИИ.

Вот смотри, у алгоритма, который вероятность коллизии считает, есть предусловие, что точки должны быть отсортированы.
Это предусловие как выражается? Например, есть две точки, на одинаковом расстоянии. У тебя из-за дребезга получилось, что они должны идти в порядке а, b, а в том алгоритме получится, что ожидаемый порядок b, a. Что тогда случится?
Или алгоритму достаточно приблизительной сортировки? Ну, типа, что бы если встретил точку на расстоянии r, это гарантировало, что дальше точки не ближе, чем r-e? Где е > 0 -- некоторая допустимая погрешность?

Или как оно устроено?
Собственно тебе сортировка же нужна для того, что бы в предусловие второго алгоритма попасть? А как оно формулируется с учётом дребезга?

Здравствуйте, Erop, Вы писали:
E>Ну, флоаты сами по себе гранулированы, относительно даблов. Просто неудобно.
E>Но можно же их гранулировать насильно, как часть твоей функции?
Может, мы друг друга не понимаем. Не важно, дабл или флоат — они оба меньше внутреннего представления FPU и в быстрой модели мусор будет оставаться наверняка. Мусор заползает в значимые биты. Чтобы с этим бороться, мы будем вынуждены срезать мусор самостоятельно, причем и до операции, и после оной. И количество срезаемых бит мантиссы должно учитывать сущность операции — одно дело сложение (там заползет меньше), другое дело — возведение в квадрат. Правка: тут даже не знаю у кого больше заполезт

E>Вот смотри, у алгоритма, который вероятность коллизии считает, есть предусловие, что точки должны быть отсортированы.
E>Это предусловие как выражается? Например, есть две точки, на одинаковом расстоянии. У тебя из-за дребезга получилось, что они должны идти в порядке а, b, а в том алгоритме получится, что ожидаемый порядок b, a. Что тогда случится?
E>Или алгоритму достаточно приблизительной сортировки? Ну, типа, что бы если встретил точку на расстоянии r, это гарантировало, что дальше точки не ближе, чем r-e? Где е > 0 -- некоторая допустимая погрешность?
Да. Тому алгоритму будет достаточно, чтобы точки были отсортированы более-менее приблизительно. То есть дребезг не создает алгоритмической проблемы, он создает исключительно техническую проблему падения алгоритма сортировки.

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

W>Да. Тому алгоритму будет достаточно, чтобы точки были отсортированы более-менее приблизительно. То есть дребезг не создает алгоритмической проблемы, он создает исключительно техническую проблему падения алгоритма сортировки.
Понял.

Я бы тупо взял что-то вроде SSE, что бы с шумами е бороться и считать быстро, и насчитал бы на все точки их расстояния, потом по ним бы и сортировал...
Но если это от чего-то не годится, то можно сделать свой алгоритм сортировки, который сортирует до состояния "примерно равно"...