[RUBY] Et si les résultats de sum et inject (: +) sont différents?

Eh bien, ce n'est pas surprenant pour ceux qui le savent.

Trouver la somme des nombres en rubis

Si vous recevez un tableau de nombres en Ruby et que vous voulez trouver la somme de ses éléments, [Array # sum](https://docs.ruby-lang.org/ja/2.7.0/method/Array/i/ La règle d'or est d'utiliser sum.html).

Comparons le code ci-dessous.

numbers = Array.new(1000){ rand }

# (1)
numbers.inject(&:+)

# (2)
numbers.inject(:+)

# (3)
numbers.sum

La vitesse augmente dans l'ordre de (1) → (2) → (3). Parmi ceux-ci, (3) est le plus rapide et le plus simple, et c'est à lui seul que «somme» devrait être adoptée. Mais ce n'est pas tout.

précision

Si la valeur numérique est Integer ou Rational, il n'y a pas d'erreur de calcul en premier lieu, mais si la valeur numérique est Float, l'erreur de calcul doit être prise en compte.

L'arithmétique à virgule flottante est souvent sujette aux erreurs. Cela ne peut pas être aidé en soi, mais si vous répétez l'opération plus d'une fois, vous devez tenir compte de la ** accumulation ** de l'erreur.

Pour écrire la conclusion en premier, la troisième raison pour laquelle «somme» devrait être adoptée est que «somme» adopte «l'algorithme d'addition de Kahan» qui supprime l'accumulation d'erreurs. Référence: [Algorithme d'addition de Kahan-Wikipedia](https://ja.wikipedia.org/wiki/%E3%82%AB%E3%83%8F%E3%83%B3%E3%81%AE%E5% 8A% A0% E7% AE% 97% E3% 82% A2% E3% 83% AB% E3% 82% B4% E3% 83% AA% E3% 82% BA% E3% 83% A0)

Exemple d'erreur

À propos du nombre représenté par Float

Avant d'entrer dans le sujet principal, je voudrais faire le tri des connaissances de base.

Il est bien connu que le nombre 0,1 ne peut pas être représenté par un nombre binaire à virgule flottante. En termes simples, le nombre 0,1 est une fraction infinie en binaire et ne peut pas être représenté par un nombre fini de chiffres.

Donc en Ruby

puts 0.1

Que signifie le fait que «0,1» s'affiche sur le terminal lorsque vous exécutez?

Tout d'abord, le système de traitement Ruby examine un nombre littéral à virgule flottante appelé «0,1» et crée un objet «Float». Cela représente un nombre à virgule flottante qui est "très proche de 0,1 mais pas le même". En gros, c'est une valeur numérique avec une précision d'environ 15 chiffres (en décimal). En fait, le type de chaîne de bits par laquelle l'objet Ruby Float est représenté dépend de l'environnement, mais dans de nombreux environnements, il semble être basé sur le type numérique de langage C double, auquel cas c'est le cas. Tout le contenu de cet article est écrit sur cette prémisse et les résultats peuvent différer dans un environnement qui ne s'applique pas.

Pourquoi est-il affiché comme «0,1» alors que j'affiche un nombre qui n'est pas 0,1? C'est parce que lorsque vous donnez un objet Float à met, la méthode to_s le convertit d'abord en un objet String appelé" chaîne numérique décimale ", mais le résultat est la chaîne" "0,1". Est. Contrairement à binaire → binaire, la conversion binaire → décimale ne transforme pas une fraction finie en une fraction infinie [^ go]. En fait, l'objet Float (le nombre représenté par) représenté par le littéral à virgule flottante «0,1» est en notation décimale.

[^ go]: C'est parce que la base 10 est un multiple de 2.

0.1000000000000000055511151231257827021181583404541015625

Cela semble être une fraction finie avec 55 chiffres après la virgule décimale (sauf si j'ai fait une erreur quelque part). Cependant, la méthode Ruby Float # to_s ne renvoie pas une telle chaîne. Il ne prend que le nombre de chiffres correspondant à la précision que peut avoir l'objet Float et renvoie la chaîne «" 0,1 "». Ceci est une spécification de to_s. (Je ne suis pas très familier avec cela, donc si vous avez des erreurs ou des suppléments, s'il vous plaît.)

Erreur cumulative

Voyons un exemple où les résultats sont différents pour le sujet principal sum et ʻinject (: +)`.

numbers = [0.1] * 6

puts numbers.sum == numbers.inject(:+)
# => false

La somme des six «0,1» ne correspond pas (encore une fois, les résultats peuvent varier en fonction de l'environnement). Affichons chaque résultat avec «put».

numbers = [0.1] * 6

puts numbers.sum        # => 0.6000000000000001
puts numbers.inject(:+) # => 0.6

En regardant cela, ne faites pas un point de départ de dire, "Eh? ʻInjecter (: +) est plus précis que somme`! Menteur! "[^ Ten].

[^ ten]: Il y a un site qui explique que «put» est plus précis que le résultat de l'ajout de 10 0,1s, mais ce n'est pas non plus valide.

Comme nous l'avons déjà vu, le nombre représenté par l'objet Float généré par le littéral à virgule flottante de Ruby «0,1» n'est pas 0,1. Au fait, bien que le résultat de la version ʻinject soit affiché comme 0.6, cela ne signifie pas que la valeur de retour est 0.6 (un objet Float représentant le nombre). Le résultat de to_s la valeur de retour est juste la chaîne de caractères" 0.6 "`.

Évaluation des erreurs

Alors, comment savez-vous exactement quelle est l'erreur? Pour ce faire, utilisez Float # to_r pour convertir l'objet Float en objet Rational. Cette méthode renvoie un objet rationnel qui correspond exactement au nombre représenté par Float.

C'est comme ça.

puts 0.1.to_r
# => 3602879701896397/36028797018963968

D'une certaine manière, une grande fraction a été affichée, mais ce n'est pas une erreur. Un objet «Float» basé sur le littéral «0,1» représente un tel nombre. À première vue, cela ressemble à une chaîne de nombres, mais si vous regardez de près, les nombres dans la molécule et le dénominateur sont les mêmes sauf pour la fin, et le nombre de molécules est d'un chiffre en moins. En d'autres termes, on peut voir qu'il est très proche de la valeur numérique de 0,1.

Si vous l'amenez à Rational, il n'y aura pas d'erreur de calcul d'addition, de soustraction, de multiplication et de division. Faisons comme ça. La somme totale prise après l'avoir rendue rationnelle est appelée «somme vraie». La valeur absolue ** de la différence ** entre la somme créée par sum et ʻinjectet la vraie somme ** est appelée" erreur ". Pour comparer celui qui a la plus petite erreur, calculez l'erreur de la version «sum» moins l'erreur de la version «inject». Si c'est positif, l'erreur de la versionsum est grande, et si elle est négative, l'erreur de la version ʻinject est grande.

#Numéro à ajouter
x = 0.1

#Numéro à ajouter
n = 6

#Somme vraie (rationnelle)
exact_sum = x.to_r * n

#Un tableau de n x
numbers = [x] * n

#Somme par somme (rationnelle)
sum_by_sum = numbers.sum.to_r

#Cette erreur
error_by_sum = (exact_sum - sum_by_sum).abs

#Rational par injection
sum_by_inject = numbers.inject(:+).to_r

#Cette erreur
error_by_inject = (exact_sum - sum_by_inject).abs

#Comparaison
puts sum_by_sum - sum_by_inject     # => 1/9007199254740992
puts error_by_sum - error_by_inject # => 0/1

Cette? La somme de la version sum et la somme de la version ʻinject` sont certes légèrement différentes, mais les erreurs sont-elles exactement les mêmes? À première vue, c'est déroutant, mais rien d'étrange. En effet, la valeur absolue est prise lors du calcul de l '"erreur". La somme des versions «sum» et «inject» existe à la même distance ** à gauche et à droite de la vraie somme. La valeur de la somme elle-même est différente, mais le montant de l'écart par rapport à la somme réelle est le même.

"Hmm? Alors, était-ce un mensonge de dire que" somme "est plus précise que" injecter "?" Je veux que vous écoutiez l'histoire jusqu'à la fin [^ sho].

[^ sho]: Pour être honnête, j'ai moi-même vu ce résultat et j'ai pensé un instant que quelque chose n'allait pas.

Dans ce cas, c'est-à-dire que lorsque 6 "0,1" (Flottant par le littéral) sont additionnés, il n'y a pas de différence de précision. C'était un cas chanceux pour la version ʻinject`. Alors, y a-t-il un cas où la version «somme» est en fait plus proche de la vraie somme? Ou y a-t-il le cas contraire? Vérifions cela comme suit. Le nombre à ajouter est «0,1» (Float par le littéral), et le nombre à ajouter est modifié.

x = 0.1

1.upto(100) do |n|
  exact_sum = x.to_r * n
  numbers = [x] * n

  sum_by_sum = numbers.sum.to_r
  error_by_sum = (exact_sum - sum_by_sum).abs

  sum_by_inject = numbers.inject(:+).to_r
  error_by_inject = (exact_sum - sum_by_inject).abs

  puts "%4d %2d" % [n, (error_by_sum <=> error_by_inject)]
end

ʻError_by_sum <=> error_by_inject doit retourner 1si la versionsomme de l'erreur est supérieure, -1si le contraire est vrai et0` si l'erreur est la même. ..

Le résultat est le suivant.

   1  0
   2  0
   3  0
   4  0
   5  0
   6  0
   7 -1
   8 -1
   9 -1
  10 -1
  11 -1
  12  0
  13  0
  14  0
  15 -1
  16 -1
  17 -1
  18 -1
  19 -1
  20 -1
  21 -1
  22 -1
  23 -1
  24 -1
  25 -1
  26 -1
  27 -1
  28 -1
  29 -1
  30 -1
  31 -1
  32 -1
  33 -1
  34 -1
  35 -1
  36 -1
  37 -1
  38 -1
  39 -1
  40 -1
  41 -1
  42 -1
  43 -1
  44  0
  45  0
  46 -1
  47 -1
  48 -1
  49 -1
  50 -1
  51 -1
  52 -1
  53 -1
  54 -1
  55 -1
  56 -1
  57 -1
  58 -1
  59 -1
  60 -1
  61 -1
  62 -1
  63 -1
  64 -1
  65 -1
  66 -1
  67 -1
  68 -1
  69 -1
  70 -1
  71 -1
  72 -1
  73 -1
  74 -1
  75 -1
  76 -1
  77 -1
  78 -1
  79 -1
  80 -1
  81 -1
  82 -1
  83 -1
  84 -1
  85 -1
  86 -1
  87 -1
  88 -1
  89 -1
  90 -1
  91 -1
  92 -1
  93 -1
  94 -1
  95 -1
  96 -1
  97 -1
  98 -1
  99 -1
 100 -1

Comme vous pouvez le voir, 11 des 1 à 100 avaient la même ampleur d'erreur. Tout le reste est plus petit dans la version «sum». Après tout, dans le cadre de cette expérience

Rencontré. Mais, bien entendu, les résultats d'une expérience aussi simple ne peuvent être généralisés. Tout ce que je peux faire maintenant est de croire en l'algorithme de Kahan et de m'assurer que j'obtiens les résultats attendus dans le cadre des expériences ci-dessus.

À propos, il y a eu 7 cas où la version «somme» correspondait à la vraie somme. Parmi ceux-ci, trois correspondaient également à la version ʻinject`.

Résumé

Utilisez sum au lieu de ʻinject (: +)` pour obtenir la somme. C'est plus simple et plus rapide. Et lorsque la valeur numérique est un nombre à virgule flottante, l'accumulation d'erreurs peut être supprimée.

Recommended Posts

Et si les résultats de sum et inject (: +) sont différents?
Quels sont les avantages de DI et de Thymeleaf?
[Java] Que faire si le contenu enregistré dans la base de données et le nom de l’énumération sont différents dans l’énumération qui reflète la définition de la base de données
Quelles sont les fonctionnalités mises à jour de Java 13
[Ruby] Les résultats du calcul entre les points décimaux sont différents, différents ou pas ce que vous vouliez.
[Note] Sortie Java de la somme des éléments pairs et impairs
Découvrez ce que font de nombreux threads à partir des résultats de jstack
'% 02d' Quel est le% de% 2?
Ceci et cela de JDK
Quelles sont les règles de JUnit?
[Java] Que sont les remplacements et les surcharges?
Agréger les résultats du questionnaire de la «saison préférée», agréger par sexe et par âge
Une collection de phrases qui impressionne le "sentiment différent" de Java et de JavaScript
Le contenu de la valeur de retour de executeBatch est différent entre 11g et 12c
Qu'est-ce qu'un test? ・ À propos de l'importance d'un test
Pliage et dépliage du contenu de la vue Recycleur
À propos du fonctionnement de next () et nextLine ()
Quelle est la structure des données d'ActionText?
Sortie de la somme de chaque nom et de son contenu à partir du tableau multiple
Que faire si les modifications ne sont pas reflétées dans le fichier manifeste JAR
Si vous utilisez Android Room et que vous souhaitez modifier la définition de colonne