В JavaScript (несколько применимом в другом месте), где вы не знаете, в какую целевую реализацию работает ваш код, существует ли способ распознавания, если базовый алгоритм сортировки (Array.sort) стабилен или нет, зная только что следует спецификация?
Я мог бы найти 2 теста в webkit (1) ( 2), но насколько надежны эти тесты? (Может ли эта проверка быть выполнена с помощью PCP?) Я ищу решение, которое было бы математически звуковым.
Это сложная проблема, поскольку более продвинутый алгоритм сортировки может изменять субалгоритмы в зависимости от длины исходного массива (например, Timsort). Я был сбит с толку, так как каждый прогон, который я выполнил, показал, что сортировка Google Chrome стабильна, но вся документация, которую я видел, сказала, что она неустойчива (источник сообщит вам, почему).
(Как правило, я использую эту стратегию, чтобы сделать мой ролик стабильным, он имеет небольшое, но иногда заметное влияние на производительность)
Исходный код для сортировки в различных реализациях:Тестирование Black-box не может использоваться для определения того, что программа удовлетворяет любому критерию, если вы не можете проверить все возможные входные данные, относящиеся к критерию. Черному ящику можно просто иметь таблицу поиска, которая отображает входные данные для выходов (см. ошибка Pentium FDIV для ошибки в реальном мире таблицы поиска), поэтому вы не можете быть уверены, что ваши тесты исключают возможность того, что какой-либо другой вход вызывает нарушение.
Математически звучит, а? Это потребовало бы, чтобы каждый путь в алгоритме считался стабильным - и каждой их комбинацией. Для любых возможных данных.
Конечно, такие алгоритмы существуют, но они, скорее всего, были сделаны в соответствии с этим требованием. Так что, если это так, вероятно, он говорит, что это где-то.
Что касается теста, чтобы доказать что-то подобное, это, вероятно, относится к аналогичным проблемам, как проблема с остановкой.
Зачем рисковать? Для большинства разумных наборов данных реализация jayscript слияния должна быть достаточно быстрой. Возьмите пару и сравните их и используйте лучший.
Запустите небольшой внутренний тест, чтобы проверить? Вы можете использовать пример "игральные карты по рангу, затем по костюмам" из Википедии, чтобы проверить стабильность.
Смотрите: https://en.wikipedia.org/wiki/Sorting_algorithm#Stability
Я не знаю, сколько карточек вам нужно для проверки стабильности - возможно, 5 или около того?