JavaScript
June 21 2016

Что скрывает Array#sort: реверс-инжиниринг подручными средствами

Как вам, возможно, известно, спецификация языка 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) характерные короткие синие полосы ближе к диагонали. Диаграмма пирамидальной сортировки напоминает сортировку слиянием, но имеет выраженный цветовой градиент.

«Однако что там насчёт браузеров?» — спросит меня пытливый читатель, не забывший ещё, с чего начиналась статья. Специально для таких читателей я сделал страничку, где можно посмотреть диаграмму Array#sort в своём текущем браузере и сравнить её с диаграммами некоторых известных алгоритмов.

Если вкратце:

  • Свежий Firefox использует сортировку слиянием, но на достаточно малых массивах переключается на нечто, напоминающее сортировку вставками. Можете проверить это самостоятельно, добавив к URL странички "?size=4" (без кавычек, естественно).
  • Свежий десктопный Chrome использует быструю сортировку. Однако на iOS он же использует сортировку слиянием.
  • Safari на MacOS и iOS также использует сортировку слиянием.
  • Яндекс.Браузер использует сортировку слиянием.
  • И старая Opera использует сортировку слиянием.
  • Konqueror и rekonq используют сортировку бинарным деревом, красно-чёрным или похожим на него.


«Однако что там насчёт Internet Explorer?» — спросит меня пытливый читатель. Что ж, я знал, что до этого вопроса когда-нибудь дойдёт… С IE вышел конфуз. Полученные в IE11 и Edge диаграммы не совпадают ни с одним из реализованных алгоритмов. Выглядят они как-то так:



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

На текущий момент это всё, что я имею сказать. Надеюсь, вам было интересно.

Upd: как подсказал Viacheslav01, в IE11 и Edge для массивов небольшого размера используется модифицированная сортировка вставками; он же добавил реализацию этой сортировки на страницу, дабы каждый мог проверить и убедиться. Для массивов размером более 512 элементов используется быстрая сортировка, в чём опять же можно убедиться, добавив "?size=10" к урле.

Upd2: С помощью чёрной магии было установлено, что IE7 использует пирамидальную сортировку. Этот результат пока недоступен для проверки широкой общественностью ввиду того, что IE7 не поддерживает канвас, а фоллбэк я ещё не запилил.
+48
13.1k 82
Comments 40
Top of the day