- PVSM.RU - https://www.pvsm.ru -
Как вам, возможно, известно, спецификация языка JavaScript не предписывает какой-то определённой реализации метода sort у массивов. Алгоритм, находящийся «под капотом», может отличаться (и отличается) в различных браузерах. Теоретически, можно представить себе ситуацию, когда от того, как именно реализована сортировка массивов в конкретном движке, зависит производительность вашего веб-приложения.
Если речь идёт о браузере с открытым исходным кодом, то можно просто открыть этот код и посмотреть, какой там использован алгоритм. Однако существуют браузеры с закрытым исходным кодом (не будем показывать пальцем). Что делать в таком случае?
Поскольку мы на Хабре, я готов предположить, что некоторые читатели уже потянулись к своим любимым дизассемблерам, в то время как некоторые другие готовятся звонить своим друзьям из одной небольшой и нетвёрдой компании. Однако сегодня мы не будем копаться в машинном коде или использовать инсайдерскую информацию. Мы будем смотреть весёлые картинки.
Существует возможность узнать кое-что о реализации метода sort прямо внутри скрипта. Она состоит в том, что этот метод принимает в качестве аргумента компаратор — функцию двух переменных, возвращающую числовое значение, на основании которого алгоритм сортировки делает вывод, какой из аргументов больше. Это позволяет сортировать массивы произвольных объектов, а не только чисел или строк. Также, что важно в нашем случае, это позволяет узнать, какие именно элементы массива и в каком порядке метод sort сравнивает между собой. Например, так:
function compare(a, b){
console.log(a, b);
return a - b;
}
Однако мало получить данные, нужно ещё придумать, как их интерпретировать. Когда я в последний раз заходил в книжный магазин, там не было книги под названием «Классификация алгоритмов сортировки на основании того, какие элементы они сравнивают между собой, для чайников». Возможно, с тех пор она там и появилась, но я решил обойтись без неё и положиться на способность человека распознавать визуальные паттерны.
Будем делать так: возьмём некий массив, затем отсортируем его с помощью специально обученного компаратора, который сохраняет данные о каждом сравнении. Затем возьмём эти данные и построим на их основании следующую диаграмму: для каждого сравнения, в котором участвовали элементы с индексами a и b (имеются в виду индексы этих элементов в уже отсортированном массиве), мы отметим точку с координатами (a, b). Заодно отметим точку с координатами (b, a), чтобы было красиво и чтобы вид диаграммы не зависел от мелких деталей реализации. Причём точка будет не простая, а цветная: её цвет будет символизировать то, когда произошло это сравнение. Сравнения, случившиеся в самом начале сортировки, отметим красным, те, что ближе к концу — синим, а между ними будут прочие цвета радуги.
Как ни странно, этот план оказался не таким уж дурацким. Я реализовал несколько наиболее распространённых алгоритмов, и они действительно давали чётко различимые паттерны. Вот, например, сортировка выбором (selection sort):
А так выглядит пузырьковая сортировка (bubble sort). Отличие хорошо различимо, и, в принципе, нетрудно понять, откуда оно берётся.
И тот, и другой — неэффективные алгоритмы сортировки (средняя временная сложность — О(n2)). Более продвинутые алгоритмы используют меньшее количество сравнений, потому диаграмма получается менее закрашенной. В начале статьи приведена диаграмма для пирамидальной сортировки (heap sort), на ней куда больше белых пикселей.
Каждая сортировка обладает своим узнаваемым паттерном. Плавный градиент у сортировки выбором, градиент с небольшими поперечными полосами у пузырьковой сортировки, полосы разного цвета у сортировки вставками (insertion sort). Быстрая сортировка (quicksort) всё расчерчивает крестиками, сортировка бинарным деревом (tree sort) — похожими крестиками, но не монотонными, а пёстрыми. У сортировки слиянием (merge sort) характерные короткие синие полосы ближе к диагонали. Диаграмма пирамидальной сортировки напоминает сортировку слиянием, но имеет выраженный цветовой градиент.
«Однако что там насчёт браузеров?» — спросит меня пытливый читатель, не забывший ещё, с чего начиналась статья. Специально для таких читателей я сделал страничку [1], где можно посмотреть диаграмму Array#sort в своём текущем браузере и сравнить её с диаграммами некоторых известных алгоритмов.
Если вкратце:
«Однако что там насчёт Internet Explorer?» — спросит меня пытливый читатель. Что ж, я знал, что до этого вопроса когда-нибудь дойдёт… С IE вышел конфуз. Полученные в IE11 и Edge диаграммы не совпадают ни с одним из реализованных алгоритмов. Выглядят они как-то так:
Есть что-то общее с сортировкой AVL-деревом, но чёткого совпадения нет. Однако я не теряю надежды и продолжаю впиливать в свою страничку новые алгоритмы. А если у вас чешутся руки мне помочь, я охотно приму [2] ваши пулл реквесты.
На текущий момент это всё, что я имею сказать. Надеюсь, вам было интересно.
Автор: Sirion
Источник [3]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/javascript/139558
Ссылки в тексте:
[1] страничку: https://siri0n.github.io/array_sort_fingerprint/
[2] приму: https://github.com/Siri0n/array_sort_fingerprint/tree/gh-pages
[3] Источник: https://habrahabr.ru/post/303748/?utm_source=habrahabr&utm_medium=rss&utm_campaign=best
Нажмите здесь для печати.