Рассмотрим, в качестве примера, формулу для вычисления среднего значения. На ней я постараюсь рассказать и показать какие подходы к реализации можно применять и чем они эффективны или не эффективны.
Это сумма всех значений за выбранный период, делённая на период. Иными словами －среднее значение за последние nзначений.
Классический подход
Как ни странно, большинство решений в сети выглядит, как последовательный перебор всех групп размером n (например 4) и вычисление среднего для каждой:
const data = [1, 2, 3, 4, 5, 6, 7, 8, 9];
function sma(data, period) {
const result = [];
for (let i = 0; i <= data.length - period; i++) {
const chunk = data.slice(i, i + period);
const sum = chunk.reduce((acc, num) => acc + num, 0);
result.push(sum / period);
}
return result;
}
console.log(sma(data, 4));
//=> [ '2.50', '3.50', '4.50', '5.50', '6.50', '7.50' ]
//=> │ │ │ │ │ └─(6+7+8+9)/4
//=> │ │ │ │ └─(5+6+7+8)/4
//=> │ │ │ └─(4+5+6+7)/4
//=> │ │ └─(3+4+5+6)/4
//=> │ └─(2+3+4+5)/4
//=> └─(1+2+3+4)/4
Безусловно, это решение работает, но оно очень плохое. Здесь происходит огромное количество повторных вычислений и лишних операций. Разберем весь код по порядку и посмотрим, строка за строкой, что происходит "под капотом".
const result = []Создание массива в JavaScript, выделяет определенную область памяти для хранения данных. Размер массива не определенный и он наполняется по мере работы цикла, в какой-то момент может наступить заполнение выделенной области памяти и модуль управления памятью будет вынужден выделить новоую, более широкую область, затем осуществить перенос в нее диапазона всех значений памяти из предыдущей области, в разных движках это может работать по разному, но в любом случае необходимо, как минимум, выделение новой области памяти. И вот, как выглядит график замера времени на операцию push, в зависимости от длинны массива.
На картинке видны космические, по местным масштабам выбросы. Это происходит по причине тех самых накладных работ в памяти движка на перенос всей области, либо на выделение новой области и связывание со старой.
Из этого можно сделать два вывода:
Для работы с большими массивами лучше использовать создание массива через конструктор как:
new Array(size). Это позволит вам задать размер массива и движок выделит столько памяти, сколько нужно.А зачем тут этот массив вообще. (Позже мы к этому вернемся)
for (let i = 0; i <= data.length - period; i++)Для начала, ремарка про цикл. Я бы не стал так подробно мусолить цикл и перешел бы к следующей части, тк в целом оптимизация цикла не дала бы нужный эффект производительности, но это просто крик души, ода к безграмотности современных разработчиков, щепетильно пишущих бенчмарки налево и направо.
Погуглив "Самый быстрый способ итерации в JavaScript" не трудно наткнуться на кучу разных бенчмарков, которые написаны не правильно. Почему не правильно? .
В теории самый самый быстрый способ итерации в JavaScript －while(i > 0) , но все тесты в лучшем случае предлагают такой вариант условия остановки: while(i++) , в котором добавляется дополнительная нагрузка в виде приведения типа числа из Number в Boolean. Даже такой вариант выхода из цикла не совсем правильный: while(i < length) потому, что сравнение с 0 является одной из самых быстрых операций и отличается от сравнения с любыми другими видами чисел.
Бытует мнение, что это миф, однако это не так. Доказательство очень простое, взглянем как процессор обрабатывает сравнение с 0 и с 1
// Сравнение с 0
Frame size 8
30 S> 0xc24390c03a6 @ 0 : 0c 01 LdaSmi [1]
0xc24390c03a8 @ 2 : 26 fb Star r0
38 S> 0xc24390c03aa @ 4 : 0b LdaZero
44 E> 0xc24390c03ab @ 5 : 6a fb 00 TestGreaterThan r0, [0]
0xc24390c03ae @ 8 : 9a 02 JumpIfFalse [2] (0xc24390c03b0 @ 10)
0xc24390c03b0 @ 10 : 0d LdaUndefined
52 S> 0xc24390c03b1 @ 11 : aa Return // Сравнение с 1
Frame size 8
30 S> 0x1ae5f0003a6 @ 0 : 0c 01 LdaSmi [1]
0x1ae5f0003a8 @ 2 : 26 fb Star r0
38 S> 0x1ae5f0003aa @ 4 : 0c 64 LdaSmi [100]
44 E> 0x1ae5f0003ac @ 6 : 6a fb 00 TestGreaterThan r0, [0]
0x1ae5f0003af @ 9 : 9a 02 JumpIfFalse [2] (0x1ae5f0003b1 @ 11)
0x1ae5f0003b1 @ 11 : 0d LdaUndefined
54 S> 0x1ae5f0003b2 @ 12 : aa Return Обратите внимание на 5ую строку. Там используется сравнение LdaZero. Которое вежливо отмечено вторым в порядке быстродействия самими разработчиками v8.
Выводы:
Сравнение с нулем или нет - разница есть!
Не верьте бенчмаркам, если они написаны не правильно
Все эти вычисления можно сделать без цикла, об этом позже.
const chunk = data.slice(i, i + period);Теперь очередь этой строки. Оператор sliceсоздает новый массив, для которого выделяется память, заполняет его данными из предыдущего массива (иммутабильно) и присваивается в переменную chunk. Это с ума сойти сколько операций на пустом месте. И тут все можно описать столь же подробно, но я не стану, потому что больше нет сил разбираться в рубрике "По колено в коде" (Олды тут?). Выше, я все обещал позже рассказать о том, как сделать эти вычисления эффективнее. Приступим!
Потоковая обработка
В основе идеи потоковой обработки, лежит архитектура последовательных вычислений, с последующим переиспользованием (по возможности) результатов предыдущих вычислений. Такой подход хорош всегда и везде (где он применим), он применяется в парсинге текста, вычислениях, поисках в математических абстракциях и прочее.
Реализация вычислений SMA в этом подходе выглядит так:
export class SMA {
constructor(period) {
this.period = period;
this.arr = [];
this.sum = 0;
this.filled = false;
}
nextValue(value) {
this.filled = this.filled || this.arr.length === this.period;
this.arr.push(value);
if (this.filled) {
this.sum -= this.arr.shift();
this.sum += value;
return this.sum / this.period;
}
this.sum += value;
}
}
const data = [1, 2, 3, 4, 5, 6, 7, 8, 9];
const sma = new SMA(4);
for(let i = 0; i < data.length; i++) {
console.log(sma.nextValue(data[i]));
}Преимущества подхода в сравнении с классической реализацией:
Массив фиксированной длинны, который заполняется значениями и очищается при переполнении, поддерживая константную размерность. Тем самым позволяет не хранить в памяти лишнюю информацию.
Повторное использование вычислений, позволяет вообще отказаться от итераций по какому-либо массиву, мы просто записываем сумму всех входящих значений, и вычитаем сумму уходящих значений (при переполнении массива)
Но проблемные места все же есть:
Проблема 1 － это постоянное условие проверки переполненности массива, даже оптимизированное в this.filled, все еще вызвыается в холостую на каждую итерацию.
Проблема 2 －Мы все еще вынуждены хранить массив длинной 4 и постоянно выполнять операции shift и push , и если push нам не так страшен, то shift, вызывает последовательное смещение индексов, что дорого.
В остальном, даже в таком виде это решение будет работать быстрее в разы, чем классический подход.
Решаем проблему под номером один. Для этого при заполнении массива переопределим метод
this.nextValue = (value: number) => {
this.sum += value;
this.arr.push(value);
this.sum -= this.arr.shift();
return this.sum / this.period;
};Это позволит избежать в дальнейших расчетах дополнительных проверок на заполненность массива. Такой "лайфхак" имеет мелкое негативное воздействие на так называемые Shape структуры браузера, которые применяются для оптимизации доступа к свойствам объекта в реальном режиме времени. Прочитать про это можно здесь. Однако это воздействие будет разовым и на дальнейших вычисления не скажется. Такой подход дает в итоге даст значительное ускорение.
Мы сегодня с вами разобрали два подхода к вычислениям среднего значения, но это все легко переносится и на любые другие вычисления, поддающиеся потоковому анализу. Я постарался сделать статью интересной затронув глубинный уровень языка и работу с памятью.
SMA и многие другие аналитические функции (технические индикаторы) можно найти в моем репозитории.
Домашнее задание
В статье решается только одна из двух проблем потоковой реализации. Можно ли избавиться от проблемы номер два? Пишите ваши предложения в комментариях.
