Рассмотрим, в качестве примера, формулу для вычисления среднего значения. На ней я постараюсь рассказать и показать какие подходы к реализации можно применять и чем они эффективны или не эффективны.

Это сумма всех значений за выбранный период, делённая на период. Иными словами -среднее значение за последние 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' ]
//=>   ¦       ¦       ¦       ¦       ¦       L-(6+7+8+9)/4
//=>   ¦       ¦       ¦       ¦       L-(5+6+7+8)/4
//=>   ¦       ¦       ¦       L-(4+5+6+7)/4
//=>   ¦       ¦       L-(3+4+5+6)/4
//=>   ¦       L-(2+3+4+5)/4
//=>   L-(1+2+3+4)/4

Безусловно, это решение работает, но оно очень плохое. Здесь происходит огромное количество повторных вычислений и лишних операций. Разберем весь код по порядку и посмотрим, строка за строкой, что происходит "под капотом".

const result = []

Создание массива в JavaScript, выделяет определенную область памяти для хранения данных. Размер массива не определенный и он наполняется по мере работы цикла, в какой-то момент может наступить заполнение выделенной области памяти и модуль управления памятью будет вынужден выделить новоую, более широкую область, затем осуществить перенос в нее диапазона всех значений памяти из предыдущей области, в разных движках это может работать по разному, но в любом случае необходимо, как минимум, выделение новой области памяти. И вот, как выглядит график замера времени на операцию push, в зависимости от длинны массива.

На картинке видны космические, по местным масштабам выбросы. Это происходит по причине тех самых накладных работ в памяти движка на перенос всей области, либо на выделение новой области и связывание со старой.

Из этого можно сделать два вывода:

1. Для работы с большими массивами лучше использовать создание массива через конструктор как: new Array(size). Это позволит вам задать размер массива и движок выделит столько памяти, сколько нужно.

2. А зачем тут этот массив вообще. (Позже мы к этому вернемся)

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.

Выводы:

1. Сравнение с нулем или нет - разница есть!

2. Не верьте бенчмаркам, если они написаны не правильно

3. Все эти вычисления можно сделать без цикла, об этом позже.

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 и многие другие аналитические функции (технические индикаторы) можно найти в моем репозитории.

Домашнее задание

В статье решается только одна из двух проблем потоковой реализации. Можно ли избавиться от проблемы номер два? Пишите ваши предложения в комментариях.