Лексикографическое упорядочение множественных двойников

Question

Рассмотрим класс типа double

class path_cost {
   double length;
   double time;
};

Если я хочу лексикографически упорядочить список path_costs, у меня проблема. Читайте дальше:)

Если я использую точное равенство для теста на равенство, вот так

bool operator<(const path_cost& rhs) const {
   if (length == rhs.length) return time < rhs.time;
   return length < rhs.length;
}

результирующий порядок, вероятно, будет неправильным, потому что небольшое отклонение (например, из-за неточностей в расчете длины) может привести к сбою теста длины, так что, например,

{ 231.00000000000001, 40 } < { 231.00000000000002, 10 }

ошибочно удерживается.

Если я альтернативно использую допуск, подобный этому

bool operator<(const path_cost& rhs) const {
   if (std::fabs(length-rhs.length)<1-e6)) return time < rhs.time;
   return length < rhs.length;
}

тогда алгоритм сортировки может ужасно потерпеть неудачу, так как оператор <больше не является транзитивным (то есть, если a <b и b <c, то a <c может не выполняться) </p>

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

(ОБНОВЛЕНИЕ Джеймса Керрана, надеюсь, объясняя проблему): Даны цифры:

• A = {231.0000001200, 10}
• B = {231.0000000500, 40}

• C = {231.0000000100, 60}

  • A. Длина и B. Длина отличаются на 7-e7, поэтому мы используем время, и A B. Длина и C. Длина отличаются на 4-е7, поэтому мы используем время, а B A.Length и C.Length отличаются на 1,1-e6, поэтому мы используем длину и A> C.

(Обновление Эсбен Мозе Хансен) Это не чисто теоретическое. Стандартные алгоритмы сортировки имеют тенденцию к сбою или, что хуже, при использовании нетранзитивного оператора сортировки. И это именно то, с чем я спорил (а мальчику было так весело отлаживать;))

Answer 1

Вы действительно хотите просто функцию сравнения?

Почему бы вам сначала не отсортировать по длине, а затем сгруппировать пары в то, что вы считаете одинаковой длины, а затем отсортировать по каждой группе по времени?1003 *

После сортировки по длине вы можете применить любую эвристику, необходимую для определения «равенства» длин, для группировки.

Answer 2

Я могу придумать два решения.

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

Или вы можете расширить ваш патч допуска, чтобы он стал отношением эквивалентности и вы восстановили транзитивность. Существуют стандартные объединяющие алгоритмы поиска для завершения любого отношения к отношению эквивалентности. После применения union-find вы можете заменить длину в каждом классе эквивалентности на согласованное значение (например, среднее значение, скажем), а затем выполнить то, что вы хотели сделать. Врачу кажется немного странным считать числа с плавающей запятой, чтобы предотвратить ложное переупорядочение, но это должно сработать.

---

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

Answer 3

Я не думаю, что вы сможете делать то, что вы хотите. По сути, вы, кажется, говорите, что в некоторых случаях вы хотите игнорировать тот факт, что a> b и притворяетесь a = b. Я вполне уверен, что вы можете построить доказательство, которое говорит, что если a и b эквивалентны, когда разница меньше определенного значения, то a и b эквивалентны для всех значений a и b. Что-то вроде:

Для допуска C и двух чисел A и B, где без потери общности A> B, существует D(n) = B+n*(C/10), где 0<=n<=(10*(A-B))/(C) такое, что тривиально D (n) находится в пределах допуска D (n-1) и D (n + 1) и, следовательно, эквивалентно им. Также D (0) - это B, а D ((10 * (A-B)) / (C)) = A, поэтому можно сказать, что A и B эквивалентны.

Я думаю, что единственный способ решить эту проблему - использовать метод разбиения. Что-то вроде умножения на 10 ^ 6 и последующего преобразования в раздел int shoudl довольно хорошо, но это будет означать, что если у вас есть 1.00001 * 10 ^ -6 и 0.999999 * 10 ^ -6, то они появятся в разных разделах, которые могут быть нежелательны .

Тогда возникает проблема с поиском ваших данных, чтобы определить, как лучше их разделить, с чем я не могу помочь, поскольку я ничего не знаю о ваших данных. :)

P.S. Алгоритмы действительно терпят крах, когда дан алгоритм или только когда они сталкиваются с определенными неразрешимыми случаями?

Answer 4

Вы никогда не получите 100% точности с обычными double с. Вы говорите, что боитесь, что использование допусков повлияет на правильность вашей программы. Вы действительно проверяли это? Какой уровень точности нужна вашей программе?

В большинстве распространенных приложений я нахожу допуск, например, 1e-9. Конечно все зависит от вашего приложения. Вы можете оценить требуемый уровень точности и просто установить допустимое значение допуска.

Если даже это не помогло, это означает, что double просто не подходит для ваших целей. Этот сценарий маловероятен, но может возникнуть, если вам нужны очень точные вычисления. В этом случае вы должны использовать пакет произвольной точности (например, BigDecimal в Java или что-то вроде GMP для C). Опять же, выбирайте эту опцию только тогда, когда другого пути нет.

Answer 5

Я не знаком с вашим приложением, но готов поспорить, что различия в расстоянии между точками на вашем графике на много порядков больше ошибок округления для чисел с плавающей запятой.Поэтому, если две записи отличаются только ошибкой округления, они по сути одинаковы, и не имеет значения, в каком порядке они появляются в вашем списке.С точки зрения здравого смысла я не вижу причин для беспокойства.