Задача: имея на входе отсортированный массив чисел, добавить одно число, не ломая сортировки. Использовать браузерный JavaScript.
Предположение: внутренний sort массива может выигрывать интерпретируемый код сортировщика до какого-то размера массива.
Что я сделал. Реализовал три алгоритма решения этой задачи и запилил пост с результатами проверки производительности и самим тестом, так что вы сами можете его запустить.
Тесты запускаются в async режиме чтобы позволить Google Charts отрендерить результаты и предотвратить подвисание браузера. Синхронный режим дал бы более точные результаты, впрочем и в асинхронном они достаточно показательны.
Каждый метод запускается несколько раз на одинаковых стартовых массивах. На следующем цикле проверки производительности размер стартового массива удваивается, пока не дойдёт до лимита размера массива.
Библиотека проверки производительности учитывает только время по часам. И хотя линейный способ выигрывает на небольших массивах (до 64 элементов у меня), он более затратен в смысле процессорного времени.
Попробуйте сами запустить [cci lang=”javascript”]runTest(size)[/cci] в консоли. Имейте в виду, что график может поломаться, если запустите с числом меньшим, чем максимальное на графике.
Можете установить лимит размера массива самостоятельно – это [cci]maxSize[/cci] параметр в url. Например, для 65536 используйте эту ссылку.
Результаты: Внутренний [cci]Array.sort[/cci] хуже логарифмической и даже линейной вставки во всех случаях. Логарифмический поиск меньше нагружает процессор, что неудивительно. Используйте логарифмический!
Код методов
[cc lang=”javascript”]
/*
* A simplest method that comes at the first sight.
* O(1) JavaScript interpreted insert and then the sort
* that is probably implemented as a precompiled method
* (or not?), but should take at least O(n*ln(n))
*/
Array.prototype.addSorted1 = function(element){
this.push(element);
this.sort();
return this;
}
[/cc]
vs
[cc lang=”javascript”]
/*
* An O(n) JavaScript interpreted new element inserter
*/
Array.prototype.addSorted2 = function(element){
for(var i=0;i<;this.length && this[i] < element;i++){
}
this.splice(i,0,element);
return this;
}
[/cc]
vs
[cc lang=”javascript”] После запуска теста подождите минуту, две… или посмотрите ошибки в консоли 🙂 Журнал:
/*
* An O(ln(n)) JavaScript interpreted new element inserter
*/
Array.prototype.addSorted3 = function(element){
var i=0;
var j=this.length;
var h;
var c=false;
if (element>this[j]){
this.push(element);
return this;
}
if (element
i=h;
} else {
j=h;
}
if (j-i<=1){
this.splice(j,0,element);
c=true;
}
}
return this;
};
[/cc]
Тест производительности