Каким должен быть оптимальный способ найти среднее из большого числа целых чисел?

Question

Каждое из целых чисел может быть размером с целое число (Java int-32 бит), поэтому сохранение суммы целых чисел в целочисленной переменной не вариант. Боюсь, использование Java BigInts может сильно повлиять на производительность.

Сейчас я пытаюсь разделить и победить, используя long для хранения суммы.

Есть ли лучшие решения?

Answer 1

Вы можете использовать long (64-bit) для хранения суммы. Если вы переиграете это, BigInteger - верный путь.

Answer 2

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

Answer 3

Как насчет long типа данных?Это должно быть довольно быстро даже на 32-битных машинах.

Answer 4

Если вы знаете заранее количество усредненных чисел, вы можете выполнить деление один за другим

int [] a;
int average;
int remainder;
int alen = a.length;

for( int i = 0; i < alen; i++ ) {
  int q = a[i] / alen;  //calculate the quotient and the remainder for the current element
  int r = a[i] % alen;
  average += q; // add up the averages and the remainders
  remainder += r;
  if( remainder >= alen ) { //roll the average over if needed 
    remainder -= alen;
    average++;
  }
}

Конечно, на практике это не имеет значения, потому что вы можетене может содержать более 2 ³¹ элементов в массиве, что означает, что вы можете сохранить сумму в long.

Answer 5

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

Answer 6

Вы можете хранить более 2 миллиардов целых.В чем проблема?Хорошо, если вам нужно еще больше целых.Сделайте простой класс, содержащий несколько длинных (и long [] подойдёт), и добавьте поверх первого.Каждые 2 миллиарда добавлений получают новый новый длинный.

В конце (avg) суммируйте длинные в BigInteger и разделите.В коде практически нет накладных расходов, один дополнительный счетчик и одна дополнительная проверка (это предсказано с помощью ветвления).

[надеюсь, я не сделал глупость на 1;)]

package t1;

import java.math.BigInteger;
import java.util.Arrays;

public class Avg {
    long sum;
    long[] totals = new long[0];

    int counter;

    public void add(int v){
        if (counter++==Integer.MAX_VALUE){
            counter = 0;
            int len =totals.length;
            totals = Arrays.copyOf(totals, len+1);
            totals[len]=sum;
            sum = 0;
        }
        sum+=v;         
    }

    public int avg(){
        long count = this.counter;
        count+=totals.length*(long)Integer.MAX_VALUE;

        BigInteger sum = BigInteger.valueOf(this.sum);
        for (long subSum : totals)
            sum=sum.add(BigInteger.valueOf(subSum));

        return sum.divide(BigInteger.valueOf(count)).intValue();//tweak if you need be
    }
}

Answer 7

Используйте число с плавающей запятой с суммированием Кахана .

Answer 8

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