[JavaScript, Алгоритмы] Быстрая математика для графиков, на примере вычисления среднего

Ответить на тему

Автор

Сообщение

news_bot ^®

Стаж: 6 лет 9 месяцев
Сообщений: 27286

news_bot ^® написал(а)
09-Июл-2021 20:31

Цитировать

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

Это сумма всех значений за выбранный период, делённая на период. Иными словами －среднее значение за последние 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 и многие другие аналитические функции (технические индикаторы) можно найти в моем репозитории.Домашнее заданиеВ статье решается только одна из двух проблем потоковой реализации. Можно ли избавиться от проблемы номер два? Пишите ваши предложения в комментариях.
===========
Источник:
habr.com
===========
Похожие новости:

Теги для поиска: #_javascript, #_algoritmy (Алгоритмы), #_tehnicheskie_indikatory (Технические индикаторы), #_matematika (математика), #_bystrodejstvie_javascript (быстродействие javascript), #_javascript, #_algoritmy (
Алгоритмы
)

Профиль ЛС

Ответить на тему

Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы

Текущее время: 22-Ноя 13:27
Часовой пояс: UTC + 5