Нестабильная сортировка в JavaScript

Когда я вижу пост на подобную тему в любой социальной сети, под ним почти всегда оказывается множество комментов вот такого типа:

  • Зачем это нужно знать, если есть встроенные методы сортировки?

  • Зачем изобретать велосипед заново?

  • Это нужно, чтобы пройти собеседование, объективно больше незачем это знать

  • В "любой движок javascript" работают не дураки, и уже сделали все как нужно

И сам я раньше считал так же, пока не пришел в одну из команд Ростелеком ИТ frontend-разработчиком. Вместе мы набрели на очень интересный кейс: нужно было создать виджет, который мог бы встраиваться в информационные системы всех наших макрорегиональных филиалов и упрощать работу операторов по подбору оптимального тарифа.

Сразу к делу

Как думаете, что произойдет после выполнения данного кода? ​

Кажется, что ничего странного, но есть нюансы.

Случай номер раз

Сделали задачу, техническое решение, код, unit-тесты. По бизнес-процессу тоже все хорошо. При поверхностном тестировании проблем не нашли. Но когда дело дошло до авто-тестов, начались странности. Конфигурация, которую просчитывал Node.js 10, в основном отдавала корректный результат, но иногда конфигурация отличалась. Что усложняло процесс поиска проблемы, учитывая, что в режиме отладки конфигурация отдавалась всегда корректной. А еще у одних членов команды некорректная конфигурация воспроизводилась, а у других — нет. И мы сделали вывод, что в старой версии, наверное, баг, и решили обновить версию на более новую.

После длительного поиска проблемы в коде ошибка не была найдена. Тестирование проекта на разных Node показало, что при запуске проекта на Node, начиная с версии 11, ответ был всегда стабильным. Что и послужило решением этой проблемы. Версия Node была обновлена до 12, и проблема исчезла.

Случай номер два

На этот раз конфигурации отличались уже в разных версиях браузера: в Google Chrome 80 был корректный результат, а в его 69 версии — нет. И тут нам стало интересно, почему же конфигурация отличается. 

  • Увидел, что версии отличаются

  • Открыл Release notes Google Chrome 

  • Обнаружил, что Google Chrome 69 —это последняя сборка, где используется 6-я версия V8

  • Открыл Release notes V8

  • И начал просматривать все статьи между 6 и 7 версией V8

Спустя некоторое время я наткнулся на статью Getting things sorted in V8, в которой говорится, что с 7-й версии V8 переходит на стабильный алгоритм сортировки TimSort, вместо предыдущего нестабильного QuickSort. И тут сразу стало понятно, что никакой магии нет, и все эти баги из-за нестабильной сортировки.

Нюансы сортировки

Сортировка в Node.js 10.22 (движок V8 v6.8) QuickSort.​

​Как видите, массив из первого скриншота изменил порядок, хотя функция сравнения всегда возвращала 0.

Сортировка в Node.js 14.5 (движок V8 v7.0) TimSort.​

​На этот раз сортировка уже не изменила данные.

Как дальше жить

И что же в итоге получается? То, что у клиентов могут быть разные результаты работы нашего кода в зависимости от типа сортировки используемого движка JavaScript. И если с Node.js переход на новую версию решит проблему, то заставить всех пользователей сделать то же самое со своими браузерами не получится. 

Есть несколько разных решений, которые подойдут для конкретных кейсов. В нашем случае мы решили использовать реализацию алгоритма BlockSort (wikisort). Да, реализация работает медленнее, чем нативная сортировка браузера, но зато теперь я уверен в стабильности результата сортировки там, где это необходимо.

Сравнение разных вариантов решения с нативной реализацией

Мы решили сравнить:

  • lodash.sortby

  • WikiSort javascript адаптация (WikiSort)

  • QuickSort нативная реализация V8 (node.js 10.22.0)

  • TimSort нативная реализация V8 (node.js 14.5.0)

В ходе теста было создано 10 массивов со случайным сортируемым значением, в каждом из которых было по 100 тысяч объектов. 

​Из этого графика можно сделать вывод: после оптимизаций, которые провел движок V8, сортировка WikiSort не уступает нативной реализации TimSort, хотя при первых сортировках разница довольно заметная. А вот lodash я бы не стал советовать. 

Посмотреть результаты теста подробнее можно тут sort-test-js, а исходный код тут — Tihon-Ustinov/sort-test-js

Где стабильно?

версия

дата релиза

движок JavaScript

стабильность

Node.js

11.0.0

2018-10-23

V8 7.0.276.28

+

Node.js

10.22.0

2020-07-21

V8 6.8.275.32

-

Google Chrome

70.0.3538

2018-10-16

V8 7.0.276

+

Google Chrome

69.0.3497

2018-09-04

V8 6.9.427

-

Выводы

  • Не верьте в «магию JavaScript», у всех странных кейсов в этом языке есть объяснение

  • Изучайте технологии, которые вы используете

  • Читайте официальную документацию

  • Следите за тем, что появляется в новых версиях

  • Не думайте, что уже все сделано и придумано, и вам нужно только использовать готовые решения

Ростелеком
Территория возможностей

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

    +16
    «Как я хочу получить от стандартной фичи языка не фиксируемое стандартом поведение, а потом удивляюсь, когда оно внезапно изменяется» (с)
      +1
      не фиксируемое стандартом поведение

      В спецификации чёрным по белому написано The sort must be stable. Начиная с ES2019.


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

        0
        В спецификации чёрным по белому написано The sort must be stable. Начиная с ES2019.

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

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

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

              Прямо в стандарте 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.

            +7
            Может было проще вместо return 0; использовать return a.localeCompare(b.name); и не полагаться на порядок?
              0

              Сравнивать строки вместо чисел? Гениально.

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

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

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

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

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

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

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

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

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

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

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

                      0

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

                        0

                        Если верить вики, 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.
                        0

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

                          0

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


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


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


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


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


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


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

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

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


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

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

                            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                            Самое читаемое