J'essaie d'obtenir la moyenne pondérée de quelques numéros. Fondamentalement, j'ai:
double optimalPrice = 0;
int totalQuantity = 0;
double rolling = 0;
System.out.println(rolling);
Iterator it = orders.entrySet().iterator();
while(it.hasNext()) {
System.out.println("inside");
Map.Entry order = (Map.Entry)it.next();
double price = (Double)order.getKey();
int quantity = (Integer)order.getValue();
System.out.println(price + " " + quantity);
rolling += price * quantity;
totalQuantity += quantity;
System.out.println(rolling);
}
System.out.println(rolling);
return rolling/totalQuantity;
7 Réponses :
Une solution consiste à utiliser java.math.biginteger pour les deux roulant et totalQuanity et ne les divisez que à la fin. Cela a une meilleure stabilité numérique, car vous n'avez qu'une seule division à virgule flottante à la fin et tout le reste est des opérations entière.
BigInteger est fondamentalement sans bornes afin que vous ne devriez pas circuler dans des débordements.
double de toute façon. Peut-être que cela vaut la peine de contourner cela en le multipliant avec 100 puis de la conversion de 100, puis de la conversion en BigInteger - car je vois dans votre exemple, il a exactement 2 chiffres à droite du point décimal - puis la diviser par 100 à la fin, Bien que ce soit un peu de hack.
1.055 -> 105 , vous devez ajouter 0.005 à la valeur avant de multiplier par 100 ou 0.5 après la multiplication par 100 mais avant la conversion entier, telle que: 1.055 -> 106 , qui est le bon arrondi.
@Pindatjuh: L'idée n'est pas de perdre de précision du tout. J'ai suggéré de multiplier par 100 car il semble que les prix de l'OP ont précisément deux chiffres après le point, pas plus.
Bien sûr, mais ce n'était pas critique à votre excellente suggestion (+1), juste une note pour un meilleur arrondi lors de l'utilisation du "hack" de multiplier par 100 et de la conversion d'un entier, dans un cas où il y a plus de 2 chiffres .
Un double peut contenir un très grand nombre (environ 1,7 x 10 ^ 308, selon les documents), mais vous ne devriez probablement pas l'utiliser pour des valeurs où la précision exacte est requise (telles que les valeurs monétaires).
Consultez le BigDecimal classe plutôt. Cette question sur SO en parle plus en détail.
Pour une flexibilité maximale, utilisez BigDecimal pour roulant et BigInteger pour totalQuanity . Après la division (note, vous l'avez à l'envers; il devrait être roulant / totalquantité), vous pouvez renvoyer un bigdecimal ou utiliser doublevalue à une perte de précision.
à n'importe quel point, vous avez enregistré à la fois la valeur totale La prochaine étape Ajoute, par exemple, un poids de La valeur que vous devez ajouter dans cette itération est, naturellement, qui ne peut pas être simplifié à un point où le facteur par lequel vous multipliez q afin d'obtenir la prochaine moyenne; Mais encore une fois, D'autres ont mentionné des variables de précision arbitraires, et c'est une bonne solution ici. La taille de AX + par + CZ + ... = PQ et le poids total A + B + c + ... = p . Connaître les deux alors vous donne la valeur moyenne pq / p = q . Le problème est que pq et p sont de grosses sommes qui débordent, même si vous voulez juste que la taille moyenne q . R et une valeur s . Vous souhaitez trouver la nouvelle somme (PQ + RS) / (p + r) en utilisant uniquement la valeur de q , qui ne peut arriver que si p < / Code> et PQ en quelque sorte "Annihilate" en étant dans le numérateur et le dénominateur de la même fraction. C'est impossible, comme je montrerai. p * q et p disparaît. Vous pouvez également trouver pq et p reste. Donc, il n'y a pas de solution intelligente. p et pq augmente linéairement avec le nombre d'entrées et la vitesse d'utilisation de la mémoire et de calcul des entiers / flotteurs augmente logarithmiquement avec la taille des valeurs. Donc, la performance est O (log (n)) contrairement au désastre que ce serait si p était en quelque sorte le multiple de nombreux chiffres.
Tout d'abord, je ne vois pas comment vous pourriez "maximiser" la variable Deuxièmement, votre utilisation d'une carte roulant . Comme @ash souligne, il peut représenter des valeurs jusqu'à environ 1.7 x 10 ^ 308 . La seule possibilité que je peux penser, c'est que vous avez des valeurs mauvaises dans votre contribution. (Peut-être que le vrai problème est que vous perdez de la précision ...)
de manière à représenter les commandes est étrange et probablement cassée. La façon dont vous l'utilisez actuellement, vous ne pouvez pas représenter des commandes impliquant deux éléments ou plus avec le même prix.
Oui, pourquoi pas seulement stocker des commandes dans une liste?
Une partie antérieure du programme combine des ordres avec le même prix.
Votre résultat final est une moyenne pondérée de précis, vous n'avez donc probablement pas besoin de suivre les règles utilisées lors du calcul des balances de compte, etc. Si je suis correct sur ce qui précède, vous n'avez pas besoin d'utiliser < Code> bigdecimal , Le problème du débordement peut être résolu en stockant une "moyenne courante" et en le mettant à jour avec chaque nouvelle entrée. À savoir, laissez
a_n = (somme_ {i = 1} ^ n x_i * w_i) / (sum_ {i = 1} ^ n w_i)
pour n = 1, ..., N. Vous commencez par a_n = x_n, puis ajoutez
d_n: = a_ {n + 1} - a_n
dessus. La formule pour d_n est
d_n = (x_ {n + 1} - w_ {n + 1} * a_n) / w_ {n + 1}
où w_n: = somme_ {i = 1} ^ n w_n. Vous devez garder une trace de w_n, mais ce problème peut être résolu en le stockant comme Pour obtenir une précision supplémentaire, vous pouvez utiliser Sommation compensée .
Explication préemptive: il est correct d'utiliser l'arithmétique de point flottant ici. Disclaimer: Si vos poids sont complètement fous (l'un est 1, un autre est 10000000), alors je ne suis pas sûr à 100% si vous obtiendrez une précision satisfaisante, mais vous pouvez le tester sur un exemple lorsque vous savez quelle est la réponse. être. double suffira.
double (ce sera ok car nous ne sommes intéressés que par la moyenne). Vous pouvez également normaliser les poids, si vous savez que tous vos poids sont des multiples de 1000, divisez-les de 1000.
double a une précision relative de 2E-16. L'OP est la moyenne de chiffres positifs, il n'y aura donc aucune erreur d'annulation. Ce que les partisans de l'arithmétique de la précision arbitraire ne vous disent-ils pas, c'est que, laissant de côté des règles d'arrondi, dans les cas où il vous donne beaucoup de précision supplémentaire sur l'arithmétique de point flottant IEEE754, cela viendra à l'importante Coût de la mémoire et de la performance. Point flottant Arithmétique a été conçu par des personnes très intelligentes (le professeur Kahan, entre autres), et s'il y avait un moyen de plus en plus de précision arithmétique sur ce qui est offert par point flottant, ils le feraient.
Vous avez toujours le problème que W_N augmente de taille avec le nombre de paires (quantité, prix). Mais cela peut ne pas être un problème avec un maximum de 60 paires.
Eh bien, il ne va probablement pas trop déborder double .
Faites deux boucles: calculez la totalité de la totalité de la première boucle. Puis dans la seconde boucle accumulez le prix * (Quantité / totalQuantité).
Ensuite, l'OP peut avoir une incidence au lieu de débordement.