Для моего приложения в node.js я должен сортировать элементы массива в порядке убывания на основе некоторого числового значения (т.е. числового ранга). Поскольку мое приложение критично критично, я решил создать свою структуру данных, чтобы оптимизировать сортировку. Я предположил, что чем меньше данных, содержащихся в каждом элементе в моем массиве, тем быстрее будут сортировки. Чтобы проверить мою гипотезу, я выполнил следующее на трех разных массивах длиной 10000:
РЕДАКТИРОВАТЬ. Ребята, похоже, что с моим оригинальным тестированием было что-то неподобающее. Первый тест занимает значительно больше времени, чем те, которые следуют. Таким образом, я изменил свой тестовый код, чтобы иметь сортировку "буфера" до фактических сортировок. Кроме того, я поменял порядок своих тестов на фиксированное количество испытаний, чтобы уменьшить любые смещения, которые могут возникнуть в результате заказа самих тестов. Я изменил результаты соответственно.
Полный источник здесь: https://raw.githubusercontent.com/youngrrrr/js-array-sort-bench-test/master/arraySortTest.js
var buffer = [781197, ... ];
var sparseArray = [781197, ... ];
var sparseArray2 = [{'a' : 781197}, ...];
var denseArray = [{'a' : 781197, 'b': ['r', 'a', 'n', 'd', 'o', 'm'] }, ...];
/* buffer : for some reason, the first test always takes significantly longer than the others. I've added this to try to remove whatever bias there was before... */
console.time('buffer');
random.sort(compareSparse);
console.timeEnd('buffer');
console.log(buffer[0]); // prints "58"
/* sparseArray : an array whose elements are numbers */
console.time('sparse');
sparseArray.sort(compareSparse);
console.timeEnd('sparse');
console.log(sparseArray[0]); // prints "58"
/* sparseArray2 (not an accurate name, just got lazy) :
an array whose elements are objects with a single key-value pair mapping
an arbitrary name 'a' to a number (which we sort on) */
console.time('sparse2');
sparseArray2.sort(compareDense);
console.timeEnd('sparse2');
console.log(sparseArray2[0]); // prints "{ a: 58 }"
/* denseArray : an array whose elements are objects with two key-value
pairs mapping an arbitrary key 'a' to a number (which we sort on) and
another arbitrary key 'b' to an array (which is just supposed to be
extra data for the purpose of my hypothesis) */
console.time('dense');
denseArray.sort(compareDense);
console.timeEnd('dense');
console.log(denseArray[0]); // prints "{ a: 58, b: [ 'r', 'a', 'n', 'd', 'o', 'm' ] }"
function compareSparse(a, b) {
if (a < b) {
return -1;
} else if (a > b) {
return 1; }
else {
return 0;
}
}
function compareDense(a, b) {
if (a.a < b.a) {
return -1;
} else if (a.a > b.a) {
return 1; }
else {
return 0;
}
}
}
Старый тест:
После 25 испытаний (я знаю, небольшой размер выборки, но я сделал это все вручную), я получил следующее время для среднего времени сортировки:
- sparseArray: (24 + 23 + 21 + 23 + 21 + 22 + 22 + 22 + 22 + 22 + 21 + 20 + 22 + 24 + 24 + 21 + 22 + 22 + 25 + 23 + 24 + 23 + 21 + 21 + 23)/25 = 22.32мс
- sparseArray2: (4 + 4 + 4 + 4 + 4 + 5 + 5 + 5 + 5 + 4 + 6 + 5 + 5 + 4 + 5 + 4 + 4 + 4 + 5 + 6 + 4 + 5 + 4 + 4 + 5)/25 = 4,56 мс
- denseArray: (5 + 5 + 4 + 5 + 5 + 5 + 5 + 5 + 5 + 6 + 5 + 5 + 4 + 4 + 5 + 5 + 5 + 4 + 5 + 5 + 6 + 5 + 5 + 5 + 4)/25 = 4.88 мс
Новый тест:
После 25 испытаний (я знаю, небольшой размер выборки, но я сделал это все вручную), я получил следующее время для среднего времени сортировки:
- sparseArray: (4 + 4 + 4 + 4 + 3 + 4 + 4 + 4 + 4 + 4 + 4 + 4 + 3 + 4 + 4)/15 = 3.867 мс
- sparseArray2: (4 + 4 + 4 + 6 + 5 + 4 + 4 + 4 + 4 + 5 + 5 + 4 + 5 + 5 + 5)/15 = 4.533 мс
- denseArray: (4 + 4 + 4 + 5 + 5 + 4 + 4 + 4 + 4 + 5 + 5 + 4 + 5 + 5 + 5)/15 = 4.466 мс
Итак, я пришел к следующим выводам:
- Массивы чисел сортируются быстрее, чем массивы объектов, значения которых являются числами. Это имеет смысл интуитивно.
- По какой-то причине и, как это ни парадоксально, больше данных в конкретном элементе приводит к более быстрой сортировке, чем к меньшим данным (о чем свидетельствуют sparseArray2 vs denseArray).
Что я хочу знать:
- Являются ли эти выводы подкрепленными какой-либо документацией/чем-то другим, кроме моего тестирования? То есть, я пришел к правильным выводам?
- И почему? Почему массивы чисел сортируются быстрее, чем массивы объектов (имеет смысл интуитивно, но каково объяснение этого, если таковое имеется)? Не только это, но почему массивы, содержащие БОЛЬШЕ данные, сортируются быстрее, чем те, которые содержат меньше данных?
И помните, я не женат на этих выводах или что-то еще. Размер выборки мал, и мое тестирование оказалось ошибочным раньше, поэтому мои результаты вполне могут быть результатом плохого тестирования. Кроме того, есть, по-видимому, различные факторы, о которых я не знаю, что может повлиять на результаты (как отметил Райан О'Хара в моем предыдущем посте). Целью этого сообщения является открытие любого основанного на фактах объяснения для сортировки поведения в Javascript.
Спасибо за чтение!
