@Sirion21 июн 2016 в 08:51

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

4 мин

20K

JavaScript *

+47

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

@Amareis 21 июн 2016 в 09:51

Удивительно, но Сириона я узнаю просто по тексту. Привет от клуба любителей рогаликов )

@Sirion 21 июн 2016 в 09:56

Давненько я у вас не был. Зашёл бы прямо сейчас, но мой рабочий айпишник до сих пор в бане, ещё со времён великих флеймовых войн) Так что вечерком-с.

@Viacheslav01 21 июн 2016 в 09:59

https://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 июн 2016 в 10:08

Чёрт, это же неспортивно) Однако спасибо. Действительно, я и забыл, что исходники Chakrum недавно открыли. Надо натравить свою страничку на несвежий IE.

@Viacheslav01 21 июн 2016 в 10:16

Неспортивно, но почти не реально подобрать спортивно. Если честно я удивлен, что они вообще используют QS, какое то время назад они у себя в .Net сделали гибрид QS с HS, при подозрении на плохие данные QS переходят на HS. А здесь IS + QS, не ожидал.

@Sirion 21 июн 2016 в 10:24

какое то время назад они у себя в .Net сделали гибрид QS с HS, при подозрении на плохие данные QS переходят на HS

Не вот этот ли?
А подбирал бы я его долго, да.

@Viacheslav01 21 июн 2016 в 10:27

Он самый, до этого они использовали QS, причем в 3.5 кривой.
Я если чесно его же и ожидал увидеть в чакре, но нашел другой гибрид :)

@Viacheslav01 21 июн 2016 в 15:14

Добавил реализацию Insertion Sort, с бинарным поиском места вставки. После size=10 сигнатура как и ожидалось однозначно QS.

@Sirion 21 июн 2016 в 15:24

Принял, спасибо.

@tyomitch 21 июн 2016 в 23:12

В консоли теперь печатается:

incorrect sort: Insertion sort (Binary search) main.js:64:4
Array [ 1, 0, 2, 4, 3, 5, 9, 6, 11, 7, 118 more… ] main.js:65:1

@Viacheslav01 22 июн 2016 в 02:15

Спасибо исправил.

@tyomitch 21 июн 2016 в 13:09

Надо натравить свою страничку на несвежий IE.

Я бы и рад вам помочь, но…

На который из скриптов он жалуется, я так и не понял.

@Sirion 21 июн 2016 в 13:26

Ох… в том, какая версия ослика что поддерживает, я разбираюсь плохо. Но есть у меня одно предположение. Перезалил, попробуйте ещё раз, пожалуйста.

@tyomitch 21 июн 2016 в 14:12

Оказывается, моя версия (IE7) вовсе не поддерживает canvas.
Хотите специально для неё сделать визуализацию при помощи таблицы с однопиксельными ячейками? :-)

@Sirion 21 июн 2016 в 15:27

Звучит жестоко, но я подумаю об этом)

@tyomitch 21 июн 2016 в 23:18

Как-то так.

Очевидно, там heapsort.

@Sirion 22 июн 2016 в 05:23

Пресвятой Ктулху, вы это сделали =) Не поделитесь кодом?

@kirilloid 22 июн 2016 в 08:55

Есть бибилиотека excanvas, работает в IE6+, для простых виуализаций хватит.
Главное начинать с ней работу только после body.onload.

@Sirion 22 июн 2016 в 09:09

К сожалению, оно не умеет в context.setImageData() и тому подобное.

@tyomitch 22 июн 2016 в 10:01

http://rgho.st/6xKbbn76v

(Оформлять пулл-реквест было лень, извините!)

Заодно проверил на древнючем Firefox 3 — там такая же сортировка слиянием, как и в современном.
Можете в сводном списке из пункта «Свежий Firefox» удалить слово «свежий» :-)

@dom1n1k 22 июн 2016 в 08:55

Канвас поддерживается начиная с девятки

@Azoh 21 июн 2016 в 10:09

В IE и Edge, возможно, quicksort со случайным выбором элемента. В Chrome на iOS используется тот же движок, что в Safari.

@Sirion 21 июн 2016 в 10:10

Вариации quicksort на тему выбора опорного элемента почти не отличаются по картинке. Выбор случайного выглядит примерно так же, как выбор последнего и выбор медианы, поэтому я не стал его вставлять в страничку.

@Maccimo 21 июн 2016 в 23:04

А что насчёт варианта алгоритма с двумя опорными точками?

@Sirion 22 июн 2016 в 05:21

Это должно выглядеть как-то интереснее, да.

@Shultc 21 июн 2016 в 13:49

Ну что, кто ещё поубивал себе все браузеры параметром типа "?size=100"?

@ad1Dima 21 июн 2016 в 14:04

в Edge только вкладка сломалась

@Shultc 21 июн 2016 в 14:09

Не, ну это понятно. FireFox предложил остановить скрипт. Vivaldi тоже поломал вкладку, показал мёртвую птичку…

Вообще, хотелось бы посмотреть, как какие браузеры реагируют на супертяжелые JS операции. FF, к примеру, порадовал тем, что предложил подождать ещё немного, пока запрос не выполнится…

@Sirion 21 июн 2016 в 15:33

Вообще да, надо будет сделать проверку параметра. Плюс ещё можно оптимизировать построение диаграмм для больших-но-не-настолько размеров, задав максимальный размер канваса (как сейчас задан минимальный) и записывая по несколько точек на пиксель. Большие канвасы не только неудобно смотреть, они ещё и память отжирают невероятное количество. Завтра займусь, спасибо, что подсказали.

@Shultc 21 июн 2016 в 16:10

Лучше оставьте размер канваса настройкой. Мне, к примеру, больше нравится рассматривать графики размером size=9, чем стандартный.

А зачем проверка-то? Если кто-то вбивает "?size=100" — это же его желание. Может этот человек разрабатывает сверх производительный браузер, и решил его тестировать именно на вашем коде =) Не забирайте у него такой возможности.

@Sirion 21 июн 2016 в 16:17

Можно и настройкой, в принципе.

@Sirion 22 июн 2016 в 06:38

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

@Viacheslav01 22 июн 2016 в 14:48

Производительный? Сайз здесь степень двойки, боюсь, что как не разрабатывай, но памяти такого объема еще много лет не будет :)

@ZyXI 21 июн 2016 в 16:33

Я по коду посмотрел, похоже каждый раз (как для каждого обновления/другого пользователя, так и для различных алгоритмов в сравнении) сортируются разные массивы. Я бы предложил один раз в main() сгенерировать случайный массив и сортировать его разными алгоритмами, так легче сравнивать.

@Sirion 21 июн 2016 в 17:09

В принципе, можно и так сделать. Я не стал этого делать изначально, потому что всё равно отличие в одной маленькой детали даст огромное расхождение картинки для двух принципиально одинаковых алгоритмов, а также потому что алгоритмы бывают рандомизированными, и попытка подобрать в точности такой же превратится в майндфак. С другой стороны, вы не первый об этом просите и, наверное, хуже от этого не будет. Сделаю.

@Klestofer 22 июн 2016 в 09:10

А что за обозначение такое: Array#sort? Почему не Array.prototype.sort()?
Уже несколько раз видел такое обозначение за последнее время. Это какой-то стандарт обозначения методов?

@Sirion 22 июн 2016 в 09:19

По идее, это пошло из JSDoc.

Basic Syntax Examples of Namepaths in JSDoc 3
myFunction
MyConstructor
MyConstructor#instanceMember
MyConstructor.staticMember
MyConstructor~innerMember

@elfwired 22 июн 2016 в 20:36

Реквестирую сортировку расчёской, интересно посмотреть на картинку.

@Sirion 23 июн 2016 в 11:37

Ваши молитвы услышаны.

@vittly 1 июл 2016 в 13:11

Прикольная идея! Получил вот картинку для v4.2.2

Зарегистрируйтесь на Хабре, чтобы оставить комментарий