Как найти среднее число по графику

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

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

Это сумма всех значений за выбранный период, делённая на период. Иными словами －среднее значение за последние 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, в зависимости от длинны массива.

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

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

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

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

for (let i = 0; i <= data.length - period; i++)

В теории самый самый быстрый способ итерации в 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. Это с ума сойти сколько операций на пустом месте. И тут все можно описать столь же подробно, но я не стану, потому что больше нет сил разбираться в рубрике “По колено в коде” (Олды тут?). Выше, я все обещал позже рассказать о том, как сделать эти вычисления эффективнее. Приступим!

Потоковая обработка

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 структуры браузера, которые применяются для оптимизации доступа к свойствам объекта в реальном режиме времени. Прочитать про это можно здесь. Однако это воздействие будет разовым и на дальнейших вычисления не скажется. Такой подход дает в итоге даст значительное ускорение.

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

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

Точечные графики: как найти среднее значение, медиану и моду

Среднее
значение периодической функции f(t)
за период Т
определяется по формуле

F_ср=
.
(2.4)

Отсюда
видно, что среднее значение за период
равно высоте прямоугольника с основанием
Т,
площадь которого равна площади,
ограниченной функцией f(t)
и осью абсцисс за один период.

В случае гармонического
колебания среднее значение за период
равно нулю, так как площадь положительной
полуволны компенсируется площадью
отрицательной полуволны гармонической
функции. Поэтому здесь пользуются
понятием среднего значения функции,
взятой по абсолютной величине, или, что
то же, среднего полупериодного значения,
соответствующего положительной полуволне
гармонической функции (рисунок 2.2).

В
соответствии с этим среднее значение
тока i
= I_mсosωt
с амплитудой А
= I_m
будет

. (2.5)

Аналогично среднее
значение гармонического напряжения

. (2.6)

Тепловое действие
тока, а также механическая сила
взаимодействия двух проводников, по
которым проходит один и тот же ток,
пропорциональны квадрату тока. Поэтому
о величине тока судят обычно по так
называемому действующему (среднеквадратичному)
значению за период. Этим термином заменен
применявшийся ранее в литературе и ныне
не рекомендуемый термин «эффективное»
значение.

Действующее
значение периодической функции f(t)
вычисляется по формуле

. (2.7)

Из
этой формулы следует, что величина F²
представляет собой среднее значение
функции [f(t}]²
за период
Т,
т.е. равна высоте прямоугольника с
основанием Т,
площадь которого равна площади,
ограниченной функцией [f(t)]²
и осью абсцисс за один период (рисунок
2.3).

В
соответствии с (2.7) действующее значение
периодического тока

. (2.8)

Возведя
(2.8) в квадрат и умножив обе части
полученного выражения на RT,
найдем

.

Это
равенство показывает, что действующее
значение периодического тока равно по
величине такому постоянному току,
который, проходя через неизменное
сопротивление R,
за период времени Т выделяет то же
количество тепла, что и данный ток i.

Аналогично
действующее значение периодического
напряжения

. (2.9)

При
токе i
= I_mcosωt

.

Следовательно,
согласно (2.8)

. (2.8а)

Аналогично
действующее значе­ние гармонического
напряжения

. (2.9а)

Номинальные токи
и напряжения электротехнических
устройств опре­деляются, как правило,
действующими значениями; поэтому
действующие значения представляют
наиболее распространенный электрический
параметр.

Для измерения
действующих значений применяются
системы приборов: тепловая, электромагнитная,
электродинамическая и др.

2.3
ПРЕДСТАВЛЕНИЕ ГАРМОНИЧЕСКИХ КОЛЕБАНИЙ
В ВИДЕ ПРОЕКЦИЙ ВРАЩАЮЩИХСЯ ВЕКТОРОВ

Мгновенные значения
функции u
= U_mcos(ωt+)
можно получить как проекцию на
горизонтальную ось отрезка длиной U_m,
вращающегося относительно начала
прямоугольной системы координат с
угловой скоростью ω = 2f
в положительном направлении (т.е. против
хода часовой стрелки). Вращающийся
отрезок условимся называть вектором.
Этот вектор, вращающийся в плоскости
прямоугольной системы координат, не
следует смешивать с вектором в трехмерном
пространстве из области механики или
теории электромагнитного поля.

В
момент t
= 0 вектор
образует с горизонтальной осью угол ψ
и его проекция
на горизонтальную ось равна U_mcos,
т.е. мгновенному значению заданной
функции при t
= 0 (рисунок
2.4, а).

За
время t
= t₁
вектор
повернется на угол ωt₁
и окажется повернутым относительно
горизонтальной оси на угол ωt₁+;
его проекция на эту ось будет равна
U_mcos(ωt₁
+ )
и т.д.

Таким
образом, рассмотрение гармонических
колебаний можно заменить рассмотрением
вращающихся векторов.

Для
получения мгновенных значений в
соответствии с вышесказанным условимся
проектировать векторы на горизонтальную
ось. Рассмотрим теперь функцию U_msin(ωt
+ )
= U_mcos(ωt
+ –).

Она
представится проекцией вращающегося
вектора, имеющего начальную фазу 
–

(рисунок 2.4, б).

Следовательно,
векторы, изображающие косинусоидальную
и синусоидальную функции, взаимно
перпендикулярны.

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

На
рисунке 2.5 показаны две гармонические
функции

u₁
= U_1mcos(ωt
+ ₁)

и

u₂
= U_2mcos(ωt
+ ₂),

имеющие
одинаковую угловую частоту ω и начальные
фазы ₁
и -₂.
Кривая u₁,
смещенная
влево относительно u₂,
возрастает от нуля до своего положительного
максимума раньше, чем кривая u₂.
Поэтому говорят, что u₁
опережает
по фазе u₂,
или, что то же, u₂
отстает по фазе от
u₁.
Разность
начальных фаз 
= ₁
– (-₂)
= ₁
+ ₂
называется фазовым сдвигом или углом
сдвига u₁
относительно u_2.
Этот угол
и образуют между собой векторы, показанные
на рисунке 2.5 (вверху).

При
равенстве начальных фаз, т.е. при фазовом
сдвиге, равном нулю,
векторы,
направлены, в одну и ту же сторону
(совпадают
по фазе).

При
фазовом сдвиге 180°
векторы направлены в диаметрально
противоположные стороны (находятся
в противофазе).

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

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

Например, пусть
требуется сложить функции

u₁
= U_1mcos(ωt
+ ₁) и
u₂
= U_2mcos(ωt
+ ₂).

Из
графического построения рисунок 2.6, а
следует:

; (2.11)

.
(2.12)

Здесь
угол 
находится с учетом знаков числителя и
знаменателя, определяющих знаки синуса
и косинуса.

В
случае, когда функция u₂
вычитается из u₁
(рисунок
2.6, б),
угол ₁
в (2.11) и (2.12) заменяется на _2
+ 
или, что то же, на ₂
().

Амплитуда
U_m
и угол 
могут быть также получены непосредственно
из векторной диаграммы.

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

Построение
векторных диаграмм обычно не связано
с определением мгновенных значений
гармонических функций; в таких случаях
векторные диаграммы строятся не для
амплитуд, а для действующих значений,
т.е. модули векторов уменьшаются по
сравнению с амплитудами в

раз. При этом векторная диаграмма
мыслится неподвижной.

В
отличие от векторных диаграмм кривые
мгновенных значений называются временными
диаграммами.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #