Как стать автором
Обновить

Комментарии 29

«Как я хочу получить от стандартной фичи языка не фиксируемое стандартом поведение, а потом удивляюсь, когда оно внезапно изменяется» (с)
НЛО прилетело и опубликовало эту надпись здесь
В спецификации чёрным по белому написано The sort must be stable. Начиная с ES2019.

Угу, и именно из-за этого изменения спецификации и пошли все прикручивать TimSort.

Стандартизированный WTF не перестаёт быть WTF.

иногда в языках программирования есть реальные ошибки, о которых годами известно и годами ничего не исправляется, потому что это сломает годами наработанный код, который научен их обходить.
В данном случае это совершенно не ошибка. Вы нигде не найдете в стандартах требование к Array.sort() размещать равные с т.з. компаратора элементы в каком-то предсказуемом порядке относительно друг друга.
Я не про данный случай. Иногда бывает, что исправлять гораздо хуже, чем оставить как есть. Хотя на первый взгляд кажется, что это неправильно.

Прямо в стандарте ECMAScript


22.1.3.27 Array.prototype.sort ( comparefn )
The elements of this array are sorted. The sort must be stable (that is, elements that compare equal must remain in their original order).

А в стандартах других языков… ну, например, в C++ есть функция std::stable_sort.

НЛО прилетело и опубликовало эту надпись здесь
Нет, сравнивать строки при равенстве чисел.
let array = [
{name: "item 1", price: 100},
{name: "item 2", price: 100},
{name: "item 10", price: 100},
{name: "item 20", price: 100},
]

попробуйте посравнивать строки в такой ситуации, например

Что вам мешает применять при сравнении строк не кондовое «больше» и «меньше», а ваш собственный мегаалгоритм, который делает всё как надо?
А вы, возможно, хотите, чтобы стандартная сортировка включала в себя весь функционал MixedSort из R, включая детектирование и сортировку римских цифр, числа с указанием единиц измерения и т.д.?

Это конечно, можно, но зачем, когда достаточно сделать стабильную сортировку, которая без больших оверхедов сделает как надо.

По-моему, «сделать как надо» описывает вообще любую задачу программирования. А ваш массив сравнением строк тоже будет сортироваться вполне стабильно.
То чувство, когда в делаешь свою инфраструктуру так, чтобы всегда данные досортировывались по Id (на случай подобного), а потом видишь блог Ростелекома, в котором находят «проблему» и героически её решают.

Предлагаю следующую статью: почему перемешивание с помощью сортировки по Math.random — плохая идея.
Вы передаете компаратору некорректную функцию (с точки зрения желаемого результата) и удивляетесь совершенно предсказуемому результату, а потом героически с ним боритесь? об этом статья? я ничего не упустил?

Коварство в том, что обычно нативные реализации сортировки для маленьких массивов (в хроме — менее 10 элементов) используют не q-sort, а какую-то другую, стабильную сортировку. И если об этом не знать, то можно забыть проверить алгоритм на массиве покрупнее. Статья-предостережение, скажем так.

А вот оно как… вы знаете я про стабильные сортировки даже честно говоря не слышал. Если я сам не знаю какая будет сортировка по заданным критериям я либо добавляю еще критерии либо мирюсь с действительностью (select * order by самый частый кейс или даже без Order by).

Можно считать, что стабильная сортировка неявно добавляет в сравнение дополнительный критерий — позицию элемента на момент старта. Конечно, это не относится к случаям, где исходный порядок вообще не определен (например, выборка из БД), но в массиве он есть.

Ясно, спасибо, ужасть)

Интересно, почему в V8 запилили TimSort, а не BlockSort? У последнего space complexity O(1), в отличии от.

TimSort работает за линию по времени в случае уже отсортированного массива. Наверняка авторы V8 собирали статистику или свой код попрофилировали и выяснили, что избыточная пересортировка случается достаточно часто.

Если верить вики, TimSort чаще сортирует за время O(n), чем BlockSort.


https://en.wikipedia.org/wiki/Block_sort#Disadvantages :


Block sort does not exploit sorted ranges of data on as fine a level as some other algorithms, such as Timsort.

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

Нет, просто акцент у статьи немножко смещён.
Нестабильная сортировка — это разновидность случайной перестановки (не очень случайной, конечно же).
Тем более, что квиксорт специально рандомизируют, чтобы он не выродился в квадратичный пузырёк на упорядоченном наборе (а у нас набор упорядоченный, все элементы — "первые").


Как именно аукнется рандомизация в программе — возможны варианты.
Первое, что приходит в голову — это при сериализации получаются разные последовательности. То есть, умом-то мы понимаем, что в двух файлах одно и то же лежит, а побайтово — нет, кажется, разное.
(Этим грешило, в частности, MFC — контейнер CMap).


Или может вылезти какой-нибудь гейзенбаг, — который воспроизводится раз в 100500 запусков, при удачном стечении обстоятельств. (Баг всю жизнь есть, но рандомизация его прячет от нас).


Программисту может показаться, что порядок элементов в сортированном массиве или в ассоциативном контейнере ему не важен. А потом хоба — и оказалось, что важен.


Вот поэтому хэш-таблицы — страшная вещь.


И вот поэтому в третьем питоне, наконец-то, объявили, что хватит трепать людям нервы, пусть dict будет стабильным контейнером (OrderedDict из второго питона). Это по-прежнему хэш-таблица, но перечисление элементов — в исходном порядке, а не в том, как оно во внутренней табличке быстрого доступа сложилось.
И, думаю, поэтому же в стандарте экмаскрипта потребовали стабильность от сортировки.


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

Следующая статья в блоге будет про то, что до ES2015 порядок обхода свойств объекта не определён? Даже план статьи составлю:

  1. Написать код, придумав свои спецификации ECMAScript
  2. Поудивляться, что есть баги, вставить картинку «магия»
  3. Найти решение, перейдя на более новую версию nodejs
  4. Узнать про спецификацию и про реализации в разных рантаймах и разных их версий


А по теме статьи: вам не нужна была своя сортировка, вам лишь надо было сделать так, чтобы компаратор не возвращал 0. Например сравнивая исходные индексы в массиве.

Но да, в некоторых случаях своя сортировка на js может быть быстрее.
  • Подтяните фундаментальные знания об алгоритмах вообще и сортировках в частности, чтобы не заниматься археологией в поисках причины странного поведения.
Зарегистрируйтесь на Хабре , чтобы оставить комментарий