Кажется, что всегда было недоразумение в фронт-конце: передний конец не может использовать знание алгоритма. В течение долгого времени это могло повлиять на это утверждение. Пока я не столкнулся с требованием продукта некоторое время назад, я оглянулся назад и обнаружил, что это не так.
Сортировка фронта
Сценарий сортировки фронта
Фронт-энд передает условие сортировки на задний план в качестве параметра запроса, а задний конец возвращает результат сортировки в качестве ответа на запрос на передний конец, что является общим дизайном. Но это не подходит для некоторых продуктов.
Представьте себе сценарий: когда вы используете приложение для питания, вы часто меняете метод сортировки, сортируйте его по цене, а затем сортируйте по рейтингу.
В фактическом производстве, из-за таких факторов, как стоимость сервера, когда один запрос данных становится общим узким местом производительности, он также считается оптимизировать производительность, сортируя его на переднем крае.
Алгоритм сортировки
Я чувствую, что нет необходимости представлять это. В качестве основного алгоритма в информатике описание будет скопировано непосредственно из Wikipedia .
Этот абзац существует здесь исключительно с целью наследства первого (человека) и второго (SHU).
JavaScript Sorting
Поскольку мы говорим о сортировке фронта, мы, естественно, будем думать о нативном интерфейсном Array.prototype.sort JavaScript.prototype.sort.
Этот интерфейс существовал со времен ECMAScript 1st Edition . Давайте посмотрим, как это выглядит описание в последней спецификации.
Array.prototype.sort спецификация
Array.prototype.sort(compareFn)
Кода -копия выглядит следующим образом:
Элементы этого массива отсортированы. Сорт не требуется стабильным (то есть элементы, которые сравнивают равные, не обязательно остаются в их первоначальном порядке). При сравнении не является неопределенным, это должна быть функция, которая принимает два аргумента x и y и возвращает отрицательное значение, если x <y, ноль, если x = y или положительное значение, если x> y.
Очевидно, что спецификация не ограничивает то, что алгоритм sort , реализованный внутри,. Даже реализация интерфейса не должна быть устойчивой сортировкой . Это очень важно и будет участвовать много раз в следующий раз.
В этом контексте сортировка фронта на самом деле зависит от конкретной реализации каждого браузера. Итак, как основные браузеры реализуют сортировку? Затем мы кратко сравниваем Chrome , Firefox и Microsoft Edge соответственно.
Реализация в Chrome
Двигатель Javascript Chrome - V8. Поскольку это открытый исходный код, вы можете напрямую посмотреть на исходный код.
Весь Array.js реализован на языке JavaScript. Часть метода сортировки, очевидно, гораздо сложнее, чем быстрое сортирование, которое я видел, но, очевидно, основной алгоритм все еще быстро сортируется. Причиной сложного алгоритма является то, что V8 сделал много оптимизации для соображений производительности. (Я расскажу об этом дальше)
Реализация в Firefox
Невозможно определить, какой алгоритм сортировки массива будет использовать JavaScript Engine Firefox. [3]
В соответствии с существующей информацией, Spidermoney реализует слияние слияния внутри.
Реализация в Microsoft Edge
Основная часть кода для JavaScript Engine Chakra Microsoft Edge была открыта на Github в начале 2016 года.
Глядя на исходный код, мы можем обнаружить, что алгоритм сортировки массива чакры также реализует быструю сортировку. И по сравнению с V8, он только реализует исключительно быструю сортировку, без следов оптимизации производительности в V8 вообще.
Проблемы с сортировкой массива JavaScript
Как мы все знаем, быстрая сортировка - это нестабильный алгоритм сортировки, в то время как сортировка слияния - это стабильный алгоритм сортировки. Из-за различий в выборе алгоритма различных двигателей, фронт-конечный полагается на код JavaScript, реализованный интерфейсом array.prototype.sort, а фактический эффект сортировки, выполняемый в браузере, является несовместимым.
Различия в стабильности сортировки должны быть вызваны конкретными сценариями до возникновения проблемы; Во многих случаях нестабильная сортировка не окажет никакого влияния.
Если нет необходимости в стабильности в сортировке массивов в реальной разработке проекта, то вы действительно можете увидеть это, и различия в реализации между браузерами не так важны.
Но если проект требует, чтобы вид был стабильным, то существование этих различий не удовлетворит спрос. Нам нужно сделать дополнительную работу для этого.
Например:
Окончательные правила выигрыша для системы аукциона по лицензии на автотранспортные средства в определенном городе:
1. Сортировать по цене в обратном порядке;
2. Та же цена будет положительно отсортирована в соответствии с заказом в торгах (то есть время подчинения цен).
Если сортировка выполняется на передней части, победитель, отображаемый в браузере, с использованием быстрой сортировки, вероятно, будет противоречивым с ожиданиями.
Изучите различия
Прежде чем найти решение, необходимо изучить причины проблемы.
Почему Chrome использует быструю сортировку
На самом деле эта ситуация существовала с самого начала.
Chrome Beta была выпущена 2 сентября 2008 года. Однако, вскоре после его выпуска, некоторые разработчики представили обратную связь с ошибками № 90 в группу разработки Chromium. Реализация сортировки массива V8 не является стабильной.
Это обсуждение проблемы с ошибкой сильно охватывает. До 10 ноября 2015 года разработчики все еще прокомментировали реализацию сортировки массива в V8.
В то же время мы также заметили, что проблема была закрыта. Тем не менее, он был вновь открыт членами команды разработчиков в июне 2013 года в качестве ссылки для обсуждения следующей спецификации Ecmascript.
И окончательный вывод ES-Discuss
Кода -копия выглядит следующим образом:
Это не меняется. Стабильная подмножество нестабильных. И наоборот, каждый нестабильный алгоритм возвращает стабильный результат для некоторых входов. Смысл Марка заключается в том, что требование «всегда нестабильного» не имеет значения, независимо от того, какой язык вы выберете.
/Андреас
Как описано в завершенной спецификации Ecmascript 2015, упомянутой ранее в этой статье.
Характеристики времени
ИМХО, эта проблема была зарегистрирована в начале выпуска Chrome, который может иметь свои особые характеристики Times.
Как упомянуто выше, первая версия Chrome была выпущена в сентябре 2008 года. Согласно статистике Statcounter, двумя браузерами с самой высокой долей рынка в течение этого периода были IE (только IE6 и IE7 в то время) и Firefox, причем доля рынка достигла 67,16% и 25,77% соответственно. Другими словами, комбинированная доля рынка двух браузеров превышает 90%.
Согласно другой статистике алгоритма сортировки браузера, эти два браузера с более чем 90% доли рынка принимают стабильную сортировку массива. Следовательно, разумно быть подвергнуто сомнению разработчикам в начале выпуска Chrome.
Соблюдать спецификации
Из обсуждения вопроса об ошибке мы можем примерно понять некоторые соображения членов команды разработчиков в использовании быстрой сортировки реализации двигателя.
Одним из них является то, что они считают, что двигатель должен соблюдать спецификацию ECMASCRIPT. Поскольку спецификация не требует описания стабильной сортировки, они считают, что реализация V8 полностью соответствует спецификации.
Соображения производительности
Кроме того, они считают, что важным рассмотрением в дизайне V8 является производительность двигателя.
Быстрая сортировка работает лучше, чем общая производительность, чем сортировка слияния:
Более высокая эффективность вычислений. Быстрая сортировка быстрее в реальной среде выполнения компьютера, чем другие алгоритмы сортировки с той же сложностью времени (в случае, если не попасть в худшую комбинацию)
Более низкие затраты на пространство. Первый имеет только сложность пространства O (n) по сравнению с последней сложностью пространства O (n), потребление памяти меньше во время выполнения.
Оптимизация производительности V8 в алгоритме сортировки массива
Поскольку V8 очень заинтересован в производительности двигателя, что он делает в сортировке массива?
Читая исходный код, я все еще узнал некоторые базовые знания.
Смешанная вставка сорта
Быстрая сортировка - это идея разделения и завоевания, разложения больших массивов и повторения их слоя за слоем. Однако, если глубина рекурсии слишком велика, потребление ресурсов памяти рекурсивного стека вызовов также будет очень большим. Плохая оптимизация может даже вызвать переполнение стека.
Текущая реализация V8 заключается в том, чтобы установить порог и использовать сортировку вставки для небольших массивов по 10 или менее длины в самом низком уровне.
В соответствии с комментариями кода и описаниями в Википедии, хотя средняя временная сложность вставки составляет O (N²) хуже, чем у быстрого сортировки O (NN). Тем не менее, в бегущей среде эффективность использования сортировки вставки небольших массивов более эффективна, чем быстрая сортировка, поэтому она не будет расширена здесь.
пример кода V8
var QuickSort = function QuickSort (a, от, до) {...... while (true) {// insertion sort более быстрее для коротких массивов. if (to - from <= 10) {insertionsort (a, от, до); возвращаться; } ......} ......};Три числа в
Как известно, быстрая сортировка пята Ахиллеса заключается в том, что алгоритм дегенератизируется в худшей комбинации массива.
Ядро алгоритма быстрой сортировки состоит в том, чтобы выбрать поворот и разложить массив, который сравнивался и обменивался в две области в соответствии со ссылкой на последующую рекурсию. Представьте себе, что если для уже упорядоченного массива, первый или последний элемент всегда выбирается каждый раз, когда выбирается эталонный элемент, то будет будет пустая численная область, которая будет пустой каждый раз, и рекурсивное количество слоев будет достигнуто N, что в конечном итоге приведет к деградации сложности алгоритма до O (N²). Следовательно, выбор олова очень важен.
V8 использует оптимизацию median-of-three : в дополнение к двум элементам в начале и конец, выбирается еще один элемент для участия в конкуренции контрольного элемента.
Стратегия отбора для третьего элемента примерно:
Когда длина массива меньше или равна 1000, выберите элемент в половине позиции в качестве целевого элемента.
Когда длина массива превышает 1000, выберите один элемент на расстоянии 200-215 (не фиксированное, изменяется с длиной массива), чтобы сначала определить партию элементов кандидатов. Затем сортируйте элементы кандидата в этой партии и используйте полученное среднее значение в качестве целевого элемента.
Наконец, воспринимайте среднюю ценность трех элементов в качестве поворота.
пример кода V8
var getThirdIndex = function (a, от, to) {var t_array = new InternalArray (); // Используйте как «от», так и «для», чтобы определить кандидатов в стержне. var Increment = 200 + ((to - от) и 15); var j = 0; от += 1; к -= 1; for (var i = from; i <to; i += Increment) {t_array [j] = [i, a [i]]; J ++; } t_array.sort (function (a, b) {return comparefn (a [1], b [1]);}); var third_index = t_array [t_array.length >> 1] [0]; return Third_Index;}; var QuickSort = function QuickSort (a, от, to) {...... while (true) {...... if (to - from> 1000) {third_index = getThirdIndex (a, от, до); } else {third_index = from + ((to - from) >> 1); }} ......};Сортируйте на месте
Рассматривая алгоритм быстрой сортировки, я видел много примеров реализации с использованием JavaScript в Интернете.
Но я обнаружил, что большая часть реализации кода выглядит следующим образом
var QuickSort = function (arr) {if (arr.length <= 1) {return arr; } var pivotindex = math.floor (arr.length / 2); var pivot = arr.splice (pivotindex, 1) [0]; var Left = []; var right = []; for (var i = 0; i <arr.length; i ++) {if (arr [i] <pivot) {left.push (arr [i]); } else {right.push (arr [i]); }} вернуть QuickSort (слева) .concat ([pivot], QuickSort (справа));};Основная проблема с приведенным выше кодом: использование двух чисел областей слева и вправо для хранения рекурсивных субррей, поэтому для этого требуется дополнительное пространство для хранения O (n). Это большая разница по сравнению с теоретической средней пространственной сложностью o (n).
Дополнительные накладные расходы также повлияют на общую скорость фактического времени выполнения. Это также одна из причин, по которой быстрая сортировка может выполняться в реальном времени забега за пределами того же уровня сложности времени. Следовательно, вообще говоря, быстрая сортировка с лучшей производительностью примет сортировку на месте.
Реализация в исходном коде V8 заключается в обмене элементами на исходном массиве.
Почему Firefox использует сортировку слияния
За этим также стоит история.
Фактически, когда Firefox был выпущен в начале, он не использовал стабильный алгоритм сортировки для реализации сортировки массива, что хорошо задокументировано.
Алгоритм сортировки массива, реализованный оригинальной версией Firefox (Firebird), была сортировкой кучи, которая также является нестабильным алгоритмом сортировки. Поэтому кто -то позже отправил ошибку.
Команда разработчиков Mozilla провела серию дискуссий по этому вопросу.
Из процесса обсуждения мы можем нарисовать некоторые моменты
1. конкурент Mozilla за тот же период был IE6. Из приведенной выше статистики мы видим, что IE6 стабилен в сортировке.
2. Брендан Эйх, отец JavaScript, считает, что стабильность хороша
3. Firefox использует быструю сортировку перед сортировкой кучи
Основываясь на основной предпосылке, что члены группы разработки, как правило, внедряют стабильные алгоритмы сортировки, Firefox3 принимает сортировку слияния в качестве новой реализации сортировки массива.
Решить различия в стабильности сортировки
Я сказал так много выше, в основном, чтобы сказать различия в реализации сортировки каждого браузера и объяснить некоторые из более поверхностных причин, почему эти различия существуют.
Но после прочтения этого у читателей все еще могут быть вопросы: что мне делать, если моему проекту просто нужно полагаться на стабильную сортировку?
Решение
На самом деле, идея решения этой проблемы относительно проста.
Браузер выбирает разные алгоритмы сортировки для разных соображений. Некоторые могут стремиться к чрезвычайным показателям, в то время как другие, как правило, обеспечивают хороший опыт разработки, но есть правила, которым следует следовать.
Судя по нынешней известной ситуации, все основные браузеры (включая IE6, 7, 8) могут в основном перечислять внедрение алгоритмов сортировки массива:
1. Слияние сортировки/Тимскорт
2. Быстрый сортировка
Итак, мы можем просто превратить быструю сортировку в стабильную сортировку?
Вообще говоря, использование нестабильной сортировки для массивов объектов повлияет на результаты. В то время как другие типы массивов сами используют стабильные или нестабильные результаты сортировки равны. Следовательно, план примерно следующим образом:
Предварительно обрабатывать массив, который будет отсортирован, и добавьте атрибуты естественного порядка в каждый объект, который будет отсортирован, чтобы не противоречить другим атрибутам объекта.
Метод сравнения пользовательской сортировки Comparefn всегда использует естественный порядок в качестве измерения второго суждения, когда предварительное выступление равна.
При столкновении с такими реализациями, как сортировка слияния, поскольку сам алгоритм стабилен, дополнительное сравнение естественного порядка не изменит результат сортировки, поэтому совместимость схемы лучше.
Тем не менее, он включает в себя изменение массива, которое будет отсортировано, и для хранения свойств естественного порядка необходимо дополнительное пространство. Возможно, что такие двигатели, как V8, не должны использовать аналогичные методы. Тем не менее, это осуществимо как план сортировки, настроенный разработчиками.
Пример кода схемы
'Использовать strict'; const index = symbol ('index'); function getComparer (compare) {return function (слева, справа) {let result = compare (слева, справа); вернуть результат === 0? левый [index] - справа [индекс]: результат; };} function sort (array, compare) {array = array.map ((item, index) => {if (typeof item === 'object') {item [index] = index;} return item;}); return array.sort (getComparer (compare));}Выше приведено просто простой пример модификации алгоритма, который удовлетворяет стабильной сортировке.
Причина, по которой это просто, заключается в том, что структуры данных в качестве входов массива в фактической производственной среде являются сложными, и необходимо судить, требуются ли больше типов предварительного заказа на основе фактической ситуации.
Ярлык
1. Фронт-энд теперь является относительно широкой концепцией. Фронт в этой статье в основном относится к окружающей среде с использованием браузера в качестве носителя и JavaScript в качестве языка программирования.
2. Эта статья не намерена включать алгоритм в целом. Я хотел бы использовать общие алгоритмы сортировки в качестве точки входа.
3. При подтверждении алгоритма, реализованного сортировкой массива Firefox, в Spidermoney была обнаружена ошибка, связанная с видом. Вообще говоря, во время обсуждения кто -то предложил использовать алгоритм Timsort с лучшей производительностью в экстремальных случаях, чтобы заменить сортировку слияния, но инженеры Mozilla заявили, что из -за проблемы разрешения лицензии алгоритма Timsort невозможно напрямую использовать алгоритм в программном обеспечении Mozilla и ждать последующего ответа другой стороны.
Суммировать
Выше приведено краткое изложение и решение проблем, с которыми сталкиваются в передней части сортировки. В последние годы все больше и больше проектов изменяются в направлении богатых клиентских приложений, а доля фронта в проектах увеличилась. Благодаря дальнейшему улучшению вычислительной мощности браузера в будущем, это позволяет сделать более сложные расчеты. С изменением обязанностей, фронтальная форма может также претерпевать некоторые серьезные изменения. Когда вы гуляете по миру, вы всегда должны иметь навык.