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

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

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 случайных выборок.

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

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

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

Ваше здоровье


mean statistics overflow bytearray
person sinjax    schedule 02.09.2010    source источник

Ответы (3)


arrow_upward
2
arrow_downward

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

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

person Ani    schedule 02.09.2010
comment
использование целочисленного типа большего размера потребовало бы больше памяти и, даже если бы оно удерживалось только в течение времени, в течение которого вычислялись средние значения, привело бы к превышению разумных накладных расходов. В конце концов я исправил эту проблему, изменив цикл, который я использовал для вычисления среднего значения, в любом случае спасибо! :-) - person sinjax; 03.09.2010
comment
Значение long заняло бы еще четыре байта и вряд ли могло бы привести к переполнению. Это была бы вполне практичная вещь. - person Tom Anderson; 03.09.2010

arrow_upward
0
arrow_downward

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

двойная разница = образцы [i] [k] - dmean [k];

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

обновить среднее значение?

person dmuir    schedule 02.09.2010
comment
нет, к сожалению, для всего сэмпла это довольно быстро станет довольно дорогим. Я исправил эту проблему, изменив цикл, который я использовал для вычисления среднего значения, как я объяснил выше. - person sinjax; 03.09.2010

arrow_upward
0
arrow_downward

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

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

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

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

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

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

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

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

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

это не сработало, но теперь я сформулировал решение, которое стоит что-то вроде: (128*numberOfSamples + numberOfSamples). Экономия 127*numberOfSamples. Что в моем худшем случае приближается к 15 ГБ ОЗУ :-)

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

Спасибо за помощь товарищи!

person sinjax    schedule 03.09.2010