Сортировка в JavaScript: должна ли каждая функция сравнения иметь инструкцию "return 0"?

Недавно я прочитал много ответов о сортировке в JavaScript, и я часто натыкаюсь на функцию сравнения, которая выглядит так:

array.sort(function(a,b){ a > b ? 1 : -1; });

Итак, это функция сравнения, которая возвращает 1, если a больше, чем b и -1, если a меньше OR EQUAL TO b. Как описано в MDN (ссылка), функция сравнения также может возвращать ноль, чтобы гарантировать, что относительное положение двух элементов остается неизменным:

Если compareFunction (a, b) возвращает 0, оставьте a и b без изменений с уважать друг друга, но отсортированы по всем элементы.

Итак, официальные примеры выглядят примерно так:

function compare(a, b) {
  if (a < b) return -1;
  if (a > b) return 1;
  return 0;
}

И действительно, добавив инструкцию return 0, алгоритм сортировки часто требует меньше итераций и работает быстрее всего (JSPerf).

Так что мне было интересно, есть ли какие-либо преимущества при отсутствии инструкции return 0.

Я понял, что на MDN он также говорит:

Примечание: стандарт ECMAscript не гарантирует такого поведения, и таким образом, не все браузеры (например, версии Mozilla, датированные, по меньшей мере, 2003) уважают это.

ссылаясь на поведение, что a и b должны оставаться неизменными, если возвращается 0. Может быть, вернув 0, мы получим немного другой отсортированный массив в разных браузерах? Это может быть причиной? И есть ли еще какие-то веские причины не возвращать нуль вообще?

Ответ 1

Поэтому мне было интересно, есть ли какое-либо преимущество при отсутствии инструкции return 0.

Меньше букв для ввода. И это может быть чуть-чуть быстрее из-за одного пропущенного сравнения. Все другие эффекты являются недостатками.

Я понял, что на MDN он также говорит:

Примечание. Стандарт ECMAscript не гарантирует такого поведения, и поэтому не все браузеры (например, версии Mozilla, датированные как минимум 2003 годом) уважают это.

ссылаясь на поведение, чтобы a и b остались неизменными, если возвращается 0.

То, что положение a и b может оставаться неизменным, является лишь требованием для стабильного сорта. Это не заданное поведение, и некоторые браузеры внедрили нестабильный алгоритм сортировки.

Однако фактическая цель возврата нуля состоит в том, что ни a них не сортируется до b (как если бы меньше 0), или что b сортируется до a (как если бы больше 0) - в основном, когда a равно b. Это необходимо для сравнения, и все алгоритмы сортировки подчиняются ему.

Чтобы создать корректный, выполнимый порядок (математически: разделите элементы на полностью упорядоченные классы эквивалентности), сравнение должно иметь определенные свойства. Они перечислены в спецификации для sort как требования для "согласованной функции сравнения".

Наиболее известным из них является рефлексивность, требуя, чтобы элемент равно (сам по себе). a a Другой способ сказать это:

compare(a, a) всегда должен возвращать 0

Что происходит, когда функция сравнения не удовлетворяет этому (например, тот, который вы наткнулись, очевидно, делает)?

Спектр говорит

Если comparefn [...] не является последовательной функцией сравнения для элементов этого массива, поведение sort определяется реализацией.

что в основном означает: если вы предоставите недопустимую функцию сравнения, массив, вероятно, не будет правильно отсортирован. Он может быть случайно изменен или вызов sort может даже не завершиться.

Может быть, вернув 0, мы получим немного другой отсортированный массив в разных браузерах? Это может быть причиной?

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

Итак, что может случиться, если вы не вернете 0 для эквивалентных предметов? В некоторых реализациях нет проблем с этим, поскольку они никогда не сравнивают элемент с самим собой (даже если это видно на нескольких позициях в массиве) - можно оптимизировать это и опустить дорогостоящий вызов функции сравнения, когда уже известно, что результат должен 0.

Другая крайность была бы бесконечной петлей. Предполагая, что у вас есть два эквивалентных предмета друг за другом, вы сравните последний с первым и поймете, что вам пришлось поменять их. Тестирование снова, последнее все равно будет меньше первого, и вам придется поменять их снова. И так далее…

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

И есть ли еще какие-то веские причины не возвращать нуль вообще?

Быть ленивым и надеяться, что массив не содержит дубликатов.

Ответ 1

Ответ 2