Когда вы находите минимум/сортируете/делаете кучу из элементов, нужно чтобы ваши элементы удовлетворяли свойству строгого слабого порядка (по-английски strict weak ordering).
Этот порядок для компаратора comp и множества S означает несколько свойств:
1. Антирефлексивность: comp(x, x) всегда false, 1 < 1 очевидно неправда
2. Ассиметричность: comp(x, y) и comp(y, x) не могут быть оба true
3. Транзитивность: если comp(x, y) и comp(y, z), то comp(x, z)
4. Транзитивность эквивалентности. Мы назовём 2 элемента эквивалентными, если comp(x, y) и comp(y, x) оба false. Тогда если x, y эквивалентны, а также y, z эквивалентны, то x и z тоже эквивалентны.
Если все эти свойства удовлетворяются, то все алгоритмы нахождения минимумов/максимумов/сортировок просто работают. Из-за этого всякие проблемы с тем, что сортировка floats с NaN не работают (так как comp(NaN, x) и comp(NaN, x) всегда false и свойство 4 ломается).
Тем не менее, дальше возникает инженерный вопрос, а если мне передают элементы в поиск минимума/любой другой алгоритм, как можно сообщить пользователю, что элементы не удовлетворяют порядку?
Можно все свойства проверить. Как вы можете видеть, надо проверять все тройки, это |S|^3 сравнений.
Если у вас линейный алгоритм поиска минимума или сортировка за |S| log |S|, то это ни в какие ворота не лезет.
Можно взять sample из 5-10 элементов и проверить в дебаг моде. Тоже вариант, и он даёт плоды найти сломанные компараторы.
Удивительный факт заключается в том, что существует алгоритм, который отвечает "да" или "нет" на вопрос, а удовлетворяет ли множество строгому слабому порядку за O(|S|^2) сравнений.
Это уже намного лучше. На тысячу элементов вы можете проверить 30-40 и замедлив вызовы всего в 2 раза.
Для этого надо
1. Посортировать множество каким-нибудь алгоритмом. Если строгое слабое свойство не выполняется, то этот алгоритм не должен падать. Учтите, что всякие std::sort могут упасть, а вот heap sort/bubble sort можно написать, чтобы даже если всё сломано, они выдадут какой-то результат.
2. Найти первый P, что comp(S[0], S[P]) is true. Если такого P нет, то P равно |S|.
3. Проверить все пары A, B до индекса P, что comp(S[A], S[B]) и comp(S[B], S[A]) false. Это означает, что все элементы до P должны быть эквивалентными
4. Проверить декартово произведение индексов A < P и B >= P, что comp(S[A], S[B]) is true и comp(S[B], S[A]) is false. Это означает, что P является разделительной точкой, чтобы элементы уже можно было сравнивать.
5. Если все проверки прошли, убрать первые P элементов и повторить. Если что-то не прошло, вернуть FALSE
Такой алгоритм работает за |S|^2 сравнений, так как если мы убираем P_1, ..., P_k элементов на каждой итерации, то мы делаем
P_1^2 + P_1(|S| - P_1) + P_2^2 + P_2(|S| - P_1 - P_2) + ... <= P_1|S| + P_2|S| + ... = |S|^2 сравнений.
Доказательство почему оно возвращает правду я написал в своём репозитории с удобным шаблонным вызовом
https://github.com/danlark1/quadratic_strict_weak_ordering
Надо тащить в LLVM/GCC/Rust/D, whatever, потому что у всех проверки не сильно мощные, а эта может найти больше, так как позволяет больше элементов забрать в sample и соответственно показать больше проблем.
Этот порядок для компаратора comp и множества S означает несколько свойств:
1. Антирефлексивность: comp(x, x) всегда false, 1 < 1 очевидно неправда
2. Ассиметричность: comp(x, y) и comp(y, x) не могут быть оба true
3. Транзитивность: если comp(x, y) и comp(y, z), то comp(x, z)
4. Транзитивность эквивалентности. Мы назовём 2 элемента эквивалентными, если comp(x, y) и comp(y, x) оба false. Тогда если x, y эквивалентны, а также y, z эквивалентны, то x и z тоже эквивалентны.
Если все эти свойства удовлетворяются, то все алгоритмы нахождения минимумов/максимумов/сортировок просто работают. Из-за этого всякие проблемы с тем, что сортировка floats с NaN не работают (так как comp(NaN, x) и comp(NaN, x) всегда false и свойство 4 ломается).
Тем не менее, дальше возникает инженерный вопрос, а если мне передают элементы в поиск минимума/любой другой алгоритм, как можно сообщить пользователю, что элементы не удовлетворяют порядку?
Можно все свойства проверить. Как вы можете видеть, надо проверять все тройки, это |S|^3 сравнений.
Если у вас линейный алгоритм поиска минимума или сортировка за |S| log |S|, то это ни в какие ворота не лезет.
Можно взять sample из 5-10 элементов и проверить в дебаг моде. Тоже вариант, и он даёт плоды найти сломанные компараторы.
Удивительный факт заключается в том, что существует алгоритм, который отвечает "да" или "нет" на вопрос, а удовлетворяет ли множество строгому слабому порядку за O(|S|^2) сравнений.
Это уже намного лучше. На тысячу элементов вы можете проверить 30-40 и замедлив вызовы всего в 2 раза.
Для этого надо
1. Посортировать множество каким-нибудь алгоритмом. Если строгое слабое свойство не выполняется, то этот алгоритм не должен падать. Учтите, что всякие std::sort могут упасть, а вот heap sort/bubble sort можно написать, чтобы даже если всё сломано, они выдадут какой-то результат.
2. Найти первый P, что comp(S[0], S[P]) is true. Если такого P нет, то P равно |S|.
3. Проверить все пары A, B до индекса P, что comp(S[A], S[B]) и comp(S[B], S[A]) false. Это означает, что все элементы до P должны быть эквивалентными
4. Проверить декартово произведение индексов A < P и B >= P, что comp(S[A], S[B]) is true и comp(S[B], S[A]) is false. Это означает, что P является разделительной точкой, чтобы элементы уже можно было сравнивать.
5. Если все проверки прошли, убрать первые P элементов и повторить. Если что-то не прошло, вернуть FALSE
Такой алгоритм работает за |S|^2 сравнений, так как если мы убираем P_1, ..., P_k элементов на каждой итерации, то мы делаем
P_1^2 + P_1(|S| - P_1) + P_2^2 + P_2(|S| - P_1 - P_2) + ... <= P_1|S| + P_2|S| + ... = |S|^2 сравнений.
Доказательство почему оно возвращает правду я написал в своём репозитории с удобным шаблонным вызовом
https://github.com/danlark1/quadratic_strict_weak_ordering
Надо тащить в LLVM/GCC/Rust/D, whatever, потому что у всех проверки не сильно мощные, а эта может найти больше, так как позволяет больше элементов забрать в sample и соответственно показать больше проблем.