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

Sie können long (64-Bit) verwenden, um die Summe zu speichern. Wenn Sie das überschreiten, ist BigInteger die richtige Wahl.

Answer 2

BigInt ist ziemlich schnell. Wie ich immer sage, erst richtig machen, dann profilieren und optimieren.

Answer 3

Wie wäre es mit long Datentyp? Es sollte sogar auf 32-Bit-Maschinen ziemlich schnell sein.

Answer 4

Sie können Fließkommazahlen verwenden und das Ergebnis dann wieder in eine Ganzzahl umwandeln. Das ist zwar nicht optimal, sollte aber schnell genug (und unkompliziert) sein

Answer 5

Wenn Sie die Anzahl der zu mittelnden Ints im Voraus kennen, können Sie die Division einzeln durchführen

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

In der Praxis spielt das natürlich keine Rolle, denn man kann nicht mehr als 2 31 Elemente in einem Array, was bedeutet, dass Sie die Summe in einem long .