JavaScript
Comments 40
0

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

0
Давненько я у вас не был. Зашёл бы прямо сейчас, но мой рабочий айпишник до сих пор в бане, ещё со времён великих флеймовых войн) Так что вечерком-с.
+6
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

П.С. сортировка вставками использует бинарный поиск для определения места вставки, поэтому может иметь не характерную картину сравонения элементов.
+1
Чёрт, это же неспортивно) Однако спасибо. Действительно, я и забыл, что исходники Chakrum недавно открыли. Надо натравить свою страничку на несвежий IE.
0
Неспортивно, но почти не реально подобрать спортивно. Если честно я удивлен, что они вообще используют QS, какое то время назад они у себя в .Net сделали гибрид QS с HS, при подозрении на плохие данные QS переходят на HS. А здесь IS + QS, не ожидал.
+1
какое то время назад они у себя в .Net сделали гибрид QS с HS, при подозрении на плохие данные QS переходят на HS

Не вот этот ли?
А подбирал бы я его долго, да.
+1
Он самый, до этого они использовали QS, причем в 3.5 кривой.
Я если чесно его же и ожидал увидеть в чакре, но нашел другой гибрид :)
+1
Добавил реализацию Insertion Sort, с бинарным поиском места вставки. После size=10 сигнатура как и ожидалось однозначно QS.
0
В консоли теперь печатается:

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

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

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



На который из скриптов он жалуется, я так и не понял.
0
Ох… в том, какая версия ослика что поддерживает, я разбираюсь плохо. Но есть у меня одно предположение. Перезалил, попробуйте ещё раз, пожалуйста.
+4
Оказывается, моя версия (IE7) вовсе не поддерживает canvas.
Хотите специально для неё сделать визуализацию при помощи таблицы с однопиксельными ячейками? :-)
+5
Пресвятой Ктулху, вы это сделали =) Не поделитесь кодом?
0
Есть бибилиотека excanvas, работает в IE6+, для простых виуализаций хватит.
Главное начинать с ней работу только после body.onload.
0
К сожалению, оно не умеет в context.setImageData() и тому подобное.
0
http://rgho.st/6xKbbn76v

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

Заодно проверил на древнючем Firefox 3 — там такая же сортировка слиянием, как и в современном.
Можете в сводном списке из пункта «Свежий Firefox» удалить слово «свежий» :-)
0
В IE и Edge, возможно, quicksort со случайным выбором элемента. В Chrome на iOS используется тот же движок, что в Safari.
0
Вариации quicksort на тему выбора опорного элемента почти не отличаются по картинке. Выбор случайного выглядит примерно так же, как выбор последнего и выбор медианы, поэтому я не стал его вставлять в страничку.
0
А что насчёт варианта алгоритма с двумя опорными точками?
+2
Ну что, кто ещё поубивал себе все браузеры параметром типа "?size=100"?
0
Не, ну это понятно. FireFox предложил остановить скрипт. Vivaldi тоже поломал вкладку, показал мёртвую птичку…

Вообще, хотелось бы посмотреть, как какие браузеры реагируют на супертяжелые JS операции. FF, к примеру, порадовал тем, что предложил подождать ещё немного, пока запрос не выполнится…
0
Вообще да, надо будет сделать проверку параметра. Плюс ещё можно оптимизировать построение диаграмм для больших-но-не-настолько размеров, задав максимальный размер канваса (как сейчас задан минимальный) и записывая по несколько точек на пиксель. Большие канвасы не только неудобно смотреть, они ещё и память отжирают невероятное количество. Завтра займусь, спасибо, что подсказали.
+3
Лучше оставьте размер канваса настройкой. Мне, к примеру, больше нравится рассматривать графики размером size=9, чем стандартный.

А зачем проверка-то? Если кто-то вбивает "?size=100" — это же его желание. Может этот человек разрабатывает сверх производительный браузер, и решил его тестировать именно на вашем коде =) Не забирайте у него такой возможности.
+1
Сделал настройкой минимальный размер канваса. С масштабированием больших массивов на маленький канвас пока не разобрался (попробовал, но получилось страшненько, ушёл курить алгоритмы ресайза изображений).
0
Производительный? Сайз здесь степень двойки, боюсь, что как не разрабатывай, но памяти такого объема еще много лет не будет :)
+2

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

+2
В принципе, можно и так сделать. Я не стал этого делать изначально, потому что всё равно отличие в одной маленькой детали даст огромное расхождение картинки для двух принципиально одинаковых алгоритмов, а также потому что алгоритмы бывают рандомизированными, и попытка подобрать в точности такой же превратится в майндфак. С другой стороны, вы не первый об этом просите и, наверное, хуже от этого не будет. Сделаю.
0
А что за обозначение такое: Array#sort? Почему не Array.prototype.sort()?
Уже несколько раз видел такое обозначение за последнее время. Это какой-то стандарт обозначения методов?
+1
По идее, это пошло из JSDoc.
Basic Syntax Examples of Namepaths in JSDoc 3
myFunction
MyConstructor
MyConstructor#instanceMember
MyConstructor.staticMember
MyConstructor~innerMember
0
Реквестирую сортировку расчёской, интересно посмотреть на картинку.
Only logged in users are able to leave comments. , please.