[JavaScript, Алгоритмы, Программирование] Нестабильная сортировка в JavaScript
Автор
Сообщение
news_bot ®
Стаж: 6 лет 2 месяца
Сообщений: 27286
Когда я вижу пост на подобную тему в любой социальной сети, под ним почти всегда оказывается множество комментов вот такого типа:
- Зачем это нужно знать, если есть встроенные методы сортировки?
- Зачем изобретать велосипед заново?
- Это нужно, чтобы пройти собеседование, объективно больше незачем это знать
- В "любой движок 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.js11.0.02018-10-23V8 7.0.276.28+Node.js10.22.02020-07-21V8 6.8.275.32-Google Chrome70.0.35382018-10-16V8 7.0.276+Google Chrome69.0.34972018-09-04V8 6.9.427-Выводы
- Не верьте в «магию JavaScript», у всех странных кейсов в этом языке есть объяснение
- Изучайте технологии, которые вы используете
- Читайте официальную документацию
- Следите за тем, что появляется в новых версиях
- Не думайте, что уже все сделано и придумано, и вам нужно только использовать готовые решения
===========
Источник:
habr.com
===========
Похожие новости:
- [Программирование, Читальный зал, Научно-популярное, Здоровье] Заметки из больницы
- [Карьера в IT-индустрии, Программирование, Управление персоналом, Управление разработкой] Гугл-программисты. Как идиот набрал на работу идиотов
- [JavaScript] «Никогда не писали автотесты? Попробуйте Cypress»
- [Производство и разработка электроники, Химия] Исследователи наконец создали металлические провода из углерода (перевод)
- [Программирование, Прототипирование, Социальные сети и сообщества, Изучение языков] Ворк-шоп по чешскому языку и код-beer на уделёнке
- [Алгоритмы, Программирование] Удаление узлов из красно-чёрного дерева
- [.NET, C#, Программирование, Проектирование и рефакторинг] Архитектура интерпрайз-приложений может быть другой
- [Программирование, Системное программирование, Rust] Попробуем выдвинуть аргументы против Rust (перевод)
- [Гаджеты, Информационная безопасность, Программирование микроконтроллеров, Умный дом] Исследователь в рамках теста заразил умную кофеварку вымогателем и запустил на ней майнинг криптовалюты
- [Flutter, Конференции, Разработка мобильных приложений, Разработка под Android, Разработка под iOS] Нативная разработка vs кроссплатформенная – обсуждаем 30 сентября с владельцами приложений
Теги для поиска: #_javascript, #_algoritmy (Алгоритмы), #_programmirovanie (Программирование), #_javascript, #_sortirovka (сортировка), #_razrabotka (разработка), #_algoritmy (алгоритмы), #_algoritmy_sortirovki (алгоритмы сортировки), #_blog_kompanii_rostelekom (
Блог компании Ростелеком
), #_javascript, #_algoritmy (
Алгоритмы
), #_programmirovanie (
Программирование
)
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 02-Май 12:29
Часовой пояс: UTC + 5
| Автор | Сообщение |
|---|---|
|
news_bot ®
Стаж: 6 лет 2 месяца |
|
|
Когда я вижу пост на подобную тему в любой социальной сети, под ним почти всегда оказывается множество комментов вот такого типа:
 Кажется, что ничего странного, но есть нюансы.Случай номер разСделали задачу, техническое решение, код, unit-тесты. По бизнес-процессу тоже все хорошо. При поверхностном тестировании проблем не нашли. Но когда дело дошло до авто-тестов, начались странности. Конфигурация, которую просчитывал Node.js 10, в основном отдавала корректный результат, но иногда конфигурация отличалась. Что усложняло процесс поиска проблемы, учитывая, что в режиме отладки конфигурация отдавалась всегда корректной. А еще у одних членов команды некорректная конфигурация воспроизводилась, а у других — нет. И мы сделали вывод, что в старой версии, наверное, баг, и решили обновить версию на более новую.После длительного поиска проблемы в коде ошибка не была найдена. Тестирование проекта на разных Node показало, что при запуске проекта на Node, начиная с версии 11, ответ был всегда стабильным. Что и послужило решением этой проблемы. Версия Node была обновлена до 12, и проблема исчезла.  Случай номер дваНа этот раз конфигурации отличались уже в разных версиях браузера: в Google Chrome 80 был корректный результат, а в его 69 версии — нет. И тут нам стало интересно, почему же конфигурация отличается.
 Нюансы сортировкиСортировка в Node.js 10.22 (движок V8 v6.8) QuickSort.  Как видите, массив из первого скриншота изменил порядок, хотя функция сравнения всегда возвращала 0.Сортировка в Node.js 14.5 (движок V8 v7.0) TimSort.  На этот раз сортировка уже не изменила данные.Как дальше житьИ что же в итоге получается? То, что у клиентов могут быть разные результаты работы нашего кода в зависимости от типа сортировки используемого движка JavaScript. И если с Node.js переход на новую версию решит проблему, то заставить всех пользователей сделать то же самое со своими браузерами не получится. Есть несколько разных решений, которые подойдут для конкретных кейсов. В нашем случае мы решили использовать реализацию алгоритма BlockSort (wikisort). Да, реализация работает медленнее, чем нативная сортировка браузера, но зато теперь я уверен в стабильности результата сортировки там, где это необходимо.Сравнение разных вариантов решения с нативной реализациейМы решили сравнить:
 Из этого графика можно сделать вывод: после оптимизаций, которые провел движок V8, сортировка WikiSort не уступает нативной реализации TimSort, хотя при первых сортировках разница довольно заметная. А вот lodash я бы не стал советовать. Посмотреть результаты теста подробнее можно тут sort-test-js, а исходный код тут — Tihon-Ustinov/sort-test-jsГде стабильно?версиядата релизадвижок JavaScriptстабильностьNode.js11.0.02018-10-23V8 7.0.276.28+Node.js10.22.02020-07-21V8 6.8.275.32-Google Chrome70.0.35382018-10-16V8 7.0.276+Google Chrome69.0.34972018-09-04V8 6.9.427-Выводы
=========== Источник: habr.com =========== Похожие новости:
Блог компании Ростелеком ), #_javascript, #_algoritmy ( Алгоритмы ), #_programmirovanie ( Программирование ) |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 02-Май 12:29
Часовой пояс: UTC + 5