Точное текущее статистическое среднее большого массива байтов

Question

У меня есть двумерный массив байтов, который выглядит следующим образом:

int n = 100000;
int d = 128;
byte[][] samples = new byte[n][d]
/* proceed to fill samples with some delicious data */
byte[] mean = new byte[d];
findMean(mean,samples);

Моя функция findMean продолжает заполнять среднее значение так, что:

mean[k] = mean(samples[:][k])

Пока достаточно просто. Проблема в том, что из-за проблем переполнения эта средняя функция не может просто делать сумму и делить. Поэтому моя текущая попытка состоит в том, чтобы вычислить среднее значение, рабочая лошадка которого выглядит примерно так:

for(int i = 0; i < samples.length; i++){
    byte diff = samples[i][k] - mean[k]
    mean[k] = (byte)((double)mean[k] + (Math.round( (double) ( diff ) / (double) (i + 1) )))

Теперь это совсем не работает, каждый раунд потери точности приводит к тому, что среднее значение довольно далеко от правильного значения, которое я проверял на небольших (поэтому рассчитываемых) наборах из 1000 случайных выборок.

Кроме того, из-за проблем с памятью, которые я пытаюсь избежать, используя в первую очередь байтовые массивы, совершенно невозможно выделить большой прокси-массив с плавающей запятой для вычисления истинного среднего значения, а затем привести к байту ,

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

В любом случае, точное вычисление среднего значения для массива байтов с использованием алгоритма выполнения, чтобы избежать проблем переполнения. Здесь есть хорошее решение?

Приветствия

Answer 1

Вы можете использовать целочисленный тип большего размера (long / bigInt) или даже арифметику произвольной точности , чтобы вычислить сумму.В этом случае вам не нужен онлайн-алгоритм, хотя его сохранение не окажет никакого влияния, кроме замедления вычислений.

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

Answer 2

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

Проблема заключалась в том, что я подходил к этой задаче следующим образом:

for each sample, get the array it is to update
    for each dimension in that array, calculate it's running mean given the new sample

Проблема сто есть, что double [] [] должен был бы содержать текущее среднее значение для каждого измерения каждого элемента для обновления.Поэтому я теперь перестроил свой цикл так, чтобы он выглядел так:

for each array to be updated
    for each sample that will update this array
        for each dimension in the array to be updated calculate the running mean

. Для этого обхода требуется некоторая предварительная обработка, мне нужно пройтись по всем выборкам, чтобы найти, какие выборки обновят какие массивы (aединый массив индексов), но мое общее спасение заключается в том, что теперь я могу содержать ОДИН двойник, который обновляется для каждого образца, который обновляет данный массив для данного измерения этого образца.

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

Общая экономия с точки зрения дискового пространства, на которое я изначально рассчитывал, составила:

замените целые числа (стоимостью 4 * 128 * numberOfSamples) байтами (стоимостью 1 * 128 * numberOfSamples)

, которые не сработали, но сейчас я сформулировал решение, которое стоит что-то вроде: (128 *numberOfSamples + numberOfSamples).Экономия 127 * число образцов.Что в моем худшем случае составляет что-то около 15 Гб оперативной памяти: -)

Так что да, мы идем, ночной сон, и я ответил на свой вопрос.

Спасибо за помощь, ребята!

Answer 3

Если вы рассчитываете 128, значит, вы не можете выделить 128 двойных (скажем, dmean] для их хранения, используйте

double diff = samples [i] [k] - dmean [k];

dmean [k] = dmean [k] + diff / (i + 1);

для обновления среднего?