Эффективная сбойная сэмплинг (диаграмма) растущего массива

Question

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

Выражаясь с кодом:

const CHART_LENGTH = 2048 
createChart(CHART_LENGTH) 
onReceivePoint = function(p) { 
    // p can be considered a number 
    const chart = addPointToChart(p) 
    // chart is an array representing all the samples received, from 0 to now 
    console.assert(chart.length <= CHART_LENGTH) 
} 

У меня уже есть рабочая понижающей дискретизации функции с числом массивов:

function downsample (arr, density) { 
    let i, j, p, _i, _len 
    const downsampled = [] 
    for (i = _i = 0, _len = arr.length; _i < _len; i = ++_i) { 
    p = arr[i] 
    j = ~~(i/arr.length * density) 
    if (downsampled[j] == null) downsampled[j] = 0 
    downsampled[j] += Math.abs(arr[i] * density/arr.length) 
    } 
    return downsampled 
} 

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

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

Обратите внимание, что диаграмма должна содержать всю историю, начиная с точки отсчета № 0 в любой момент, поэтому наметить последние n точек не будет приемлемым.

Answer 1

Единственная операция, которая не искажает данные и которая может использоваться несколько раз, - это объединение целого числа смежных выборок. Вы, вероятно, захотите 2.

Более конкретно: если вы обнаружите, что добавление нового образца будет превышать границы массива, выполните следующие действия: Начните с начала массива и усредните два последующих образца. Это уменьшит размер массива на 2, и у вас будет место для добавления новых образцов. При этом вы должны отслеживать текущий размер кластера c (количество выборок, составляющих одну запись в массиве). Вы начинаете с одного. Каждое уменьшение умножает размер кластера на два.

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

n++ 
if n = 1 
    append s to array 
else   
    //update the average 
    last array element += (s - last array element)/n 
if n = c 
    n = 0 //start a new cluster 

Так память, что вы на самом деле нужны следующее:

• история массив с заранее определенной длиной
• число элементов в массиве истории
• размера текущего кластера c
• количество элементов в текущем кластере n

Размер дополнительной памяти не зависит от общего количества образцов, следовательно, O(1).