Если речь идёт о браузере с открытым исходным кодом, то можно просто открыть этот код и посмотреть, какой там использован алгоритм. Однако существуют браузеры с закрытым исходным кодом (не будем показывать пальцем). Что делать в таком случае?
Поскольку мы на Хабре, я готов предположить, что некоторые читатели уже потянулись к своим любимым дизассемблерам, в то время как некоторые другие готовятся звонить своим друзьям из одной небольшой и нетвёрдой компании. Однако сегодня мы не будем копаться в машинном коде или использовать инсайдерскую информацию. Мы будем смотреть весёлые картинки.
Существует возможность узнать кое-что о реализации метода 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 не поддерживает канвас, а фоллбэк я ещё не запилил.
Комментарии (40)
Viacheslav01
21.06.2016 12:59+6https://github.com/Microsoft/ChakraCore/blob/2ba5ccbb37c6f7e55fdf1870f80379857ae28b20/lib/Runtime/Library/JavascriptArray.cpp
У Чакры до 512 элементов в массиве используется сортировка вставками, если больше то qsort_s который
// qsort_s is a variant of qsort that takes in a context parameter
// It's similar to qsort_r that GCC provides, but with the difference
// that qsort_s takes in the context as the first param to the compare
// function, while qsort_r takes it as the last.
// So we have to do this wrapper dance to deal with the translation
// Lambda doesn't work here as qsort_r needs a function pointer
П.С. сортировка вставками использует бинарный поиск для определения места вставки, поэтому может иметь не характерную картину сравонения элементов.
Sirion
21.06.2016 13:08+1Чёрт, это же неспортивно) Однако спасибо. Действительно, я и забыл, что исходники Chakrum недавно открыли. Надо натравить свою страничку на несвежий IE.
Viacheslav01
21.06.2016 13:16Неспортивно, но почти не реально подобрать спортивно. Если честно я удивлен, что они вообще используют QS, какое то время назад они у себя в .Net сделали гибрид QS с HS, при подозрении на плохие данные QS переходят на HS. А здесь IS + QS, не ожидал.
Sirion
21.06.2016 13:24+1какое то время назад они у себя в .Net сделали гибрид QS с HS, при подозрении на плохие данные QS переходят на HS
Не вот этот ли?
А подбирал бы я его долго, да.Viacheslav01
21.06.2016 13:27+1Он самый, до этого они использовали QS, причем в 3.5 кривой.
Я если чесно его же и ожидал увидеть в чакре, но нашел другой гибрид :)
Viacheslav01
21.06.2016 18:14+1Добавил реализацию Insertion Sort, с бинарным поиском места вставки. После size=10 сигнатура как и ожидалось однозначно QS.
tyomitch
21.06.2016 16:09+1Надо натравить свою страничку на несвежий IE.
Я бы и рад вам помочь, но…
На который из скриптов он жалуется, я так и не понял.Sirion
21.06.2016 16:26Ох… в том, какая версия ослика что поддерживает, я разбираюсь плохо. Но есть у меня одно предположение. Перезалил, попробуйте ещё раз, пожалуйста.
tyomitch
21.06.2016 17:12+4Оказывается, моя версия (IE7) вовсе не поддерживает canvas.
Хотите специально для неё сделать визуализацию при помощи таблицы с однопиксельными ячейками? :-)tyomitch
22.06.2016 02:18+2Как-то так.
Sirion
22.06.2016 08:23+5Пресвятой Ктулху, вы это сделали =) Не поделитесь кодом?
tyomitch
22.06.2016 13:01http://rgho.st/6xKbbn76v
(Оформлять пулл-реквест было лень, извините!)
Заодно проверил на древнючем Firefox 3 — там такая же сортировка слиянием, как и в современном.
Можете в сводном списке из пункта «Свежий Firefox» удалить слово «свежий» :-)
Azoh
21.06.2016 13:09В IE и Edge, возможно, quicksort со случайным выбором элемента. В Chrome на iOS используется тот же движок, что в Safari.
Sirion
21.06.2016 13:10Вариации quicksort на тему выбора опорного элемента почти не отличаются по картинке. Выбор случайного выглядит примерно так же, как выбор последнего и выбор медианы, поэтому я не стал его вставлять в страничку.
Shultc
21.06.2016 16:49+2Ну что, кто ещё поубивал себе все браузеры параметром типа "?size=100"?
ad1Dima
21.06.2016 17:04в Edge только вкладка сломалась
Shultc
21.06.2016 17:09Не, ну это понятно. FireFox предложил остановить скрипт. Vivaldi тоже поломал вкладку, показал мёртвую птичку…
Вообще, хотелось бы посмотреть, как какие браузеры реагируют на супертяжелые JS операции. FF, к примеру, порадовал тем, что предложил подождать ещё немного, пока запрос не выполнится…
Sirion
21.06.2016 18:33Вообще да, надо будет сделать проверку параметра. Плюс ещё можно оптимизировать построение диаграмм для больших-но-не-настолько размеров, задав максимальный размер канваса (как сейчас задан минимальный) и записывая по несколько точек на пиксель. Большие канвасы не только неудобно смотреть, они ещё и память отжирают невероятное количество. Завтра займусь, спасибо, что подсказали.
Shultc
21.06.2016 19:10+3Лучше оставьте размер канваса настройкой. Мне, к примеру, больше нравится рассматривать графики размером size=9, чем стандартный.
А зачем проверка-то? Если кто-то вбивает "?size=100" — это же его желание. Может этот человек разрабатывает сверх производительный браузер, и решил его тестировать именно на вашем коде =) Не забирайте у него такой возможности.Sirion
22.06.2016 09:38+1Сделал настройкой минимальный размер канваса. С масштабированием больших массивов на маленький канвас пока не разобрался (попробовал, но получилось страшненько, ушёл курить алгоритмы ресайза изображений).
Viacheslav01
22.06.2016 17:48Производительный? Сайз здесь степень двойки, боюсь, что как не разрабатывай, но памяти такого объема еще много лет не будет :)
ZyXI
21.06.2016 19:33+2Я по коду посмотрел, похоже каждый раз (как для каждого обновления/другого пользователя, так и для различных алгоритмов в сравнении) сортируются разные массивы. Я бы предложил один раз в
main()сгенерировать случайный массив и сортировать его разными алгоритмами, так легче сравнивать.Sirion
21.06.2016 20:09+2В принципе, можно и так сделать. Я не стал этого делать изначально, потому что всё равно отличие в одной маленькой детали даст огромное расхождение картинки для двух принципиально одинаковых алгоритмов, а также потому что алгоритмы бывают рандомизированными, и попытка подобрать в точности такой же превратится в майндфак. С другой стороны, вы не первый об этом просите и, наверное, хуже от этого не будет. Сделаю.
Klestofer
22.06.2016 12:10А что за обозначение такое: Array#sort? Почему не Array.prototype.sort()?
Уже несколько раз видел такое обозначение за последнее время. Это какой-то стандарт обозначения методов?
Amareis
Удивительно, но Сириона я узнаю просто по тексту. Привет от клуба любителей рогаликов )
Sirion
Давненько я у вас не был. Зашёл бы прямо сейчас, но мой рабочий айпишник до сих пор в бане, ещё со времён великих флеймовых войн) Так что вечерком-с.