Wie lässt sich der Durchschnitt einer großen Anzahl von ganzen Zahlen optimal ermitteln?

Question

Jede der Ganzzahlen kann so groß sein wie eine Ganzzahl selbst (Java int-32 Bits), so dass das Speichern der Summe der Ganzzahlen in einer Ganzzahlvariablen keine Option ist. Ich befürchte, dass die Verwendung von Java BigInts die Leistung stark beeinträchtigen könnte.

Im Moment versuche ich, zu teilen und zu erobern, indem ich lang um die Summe zu speichern.

Gibt es bessere Lösungen?

Answer 1

Sofern Sie nicht den Durchschnitt von Milliarden von Zahlen berechnen, sollte die Verwendung von BigInteger keine großen Auswirkungen auf die Leistung haben. Sie sollten versuchen, mit BigInteger zu kodieren und dann entscheiden, ob es schnell genug ist.

Answer 2

Sie können über 2 Milliarden Ints in einem Long speichern. Wo liegt das Problem? Nun, wenn Sie noch mehr Ints benötigen. Machen Sie eine einfache Klasse, die mehrere longs (und long[] wird tun), und fügen Sie auf der Oberseite des 1. Jedes Mal, wenn 2 Milliarden hinzugefügt werden, erhält man einen neuen Long.

Am Ende (avg) werden die Longs in einem BigInteger summiert und geteilt. Der Code hat so gut wie keinen Overhead, einen zusätzlichen Zähler und eine zusätzliche Prüfung (das ist die Verzweigung vorhergesagt).

(Hoffentlich habe ich nicht irgendeinen dummen Fehler gemacht ;))

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
    }
}