Nun, es ist nicht überraschend für diejenigen, die es wissen.
Wenn Sie in Ruby ein Array von Zahlen erhalten und die Summe seiner Elemente ermitteln möchten, Array # sum Als Faustregel gilt sum.html).
Vergleichen wir den folgenden Code.
numbers = Array.new(1000){ rand }
# (1)
numbers.inject(&:+)
# (2)
numbers.inject(:+)
# (3)
numbers.sum
Die Geschwindigkeit erhöht sich in der Größenordnung von (1) → (2) → (3). Von diesen ist (3) die schnellste und einfachste, und das allein ist der Grund, warum "Summe" angenommen werden sollte. Aber das ist nicht alles.
Wenn der numerische Wert Integer oder Rational ist, liegt zunächst kein Berechnungsfehler vor. Wenn der numerische Wert jedoch Float ist, muss der Berechnungsfehler berücksichtigt werden.
Gleitkomma-Arithmetik ist häufig fehleranfällig. Es kann an sich nicht geholfen werden, aber wenn Sie den Vorgang mehr als einmal wiederholen, müssen Sie die ** Anhäufung ** des Fehlers berücksichtigen.
Um die Schlussfolgerung zuerst zu schreiben, ist der dritte Grund, warum "Summe" angenommen werden sollte, dass "Summe" den "Kahan-Additionsalgorithmus" verwendet, der die Anhäufung von Fehlern unterdrückt. Referenz: [Kahans Additionsalgorithmus-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)
Bevor ich zum Hauptthema komme, möchte ich einige Hintergrundkenntnisse klären.
Es ist bekannt, dass die Zahl 0.1 nicht durch eine binäre Gleitkommazahl dargestellt werden kann. Einfach ausgedrückt ist die Zahl 0.1 ein unendlicher Bruchteil der Binärzahl und kann nicht durch eine endliche Anzahl von Ziffern dargestellt werden.
Also in Ruby
puts 0.1
Was bedeutet es, dass bei der Ausführung "0.1" auf dem Terminal angezeigt wird?
Zunächst betrachtet das Ruby-Verarbeitungssystem ein Gleitkommazahl-Literal mit dem Namen "0.1" und erstellt ein "Float" -Objekt. Dies stellt eine Gleitkommazahl dar, die "sehr nahe bei 0,1, aber nicht gleich" liegt. Grob gesagt handelt es sich um einen numerischen Wert mit einer Genauigkeit von etwa 15 Stellen (in Dezimalzahlen). Tatsächlich ist die Art der Bitfolge, durch die das Ruby Float-Objekt dargestellt wird, von der Umgebung abhängig, aber es scheint, dass sie in vielen Umgebungen auf dem numerischen Typ der C-Sprache double basiert, und in diesem Fall ist dies der Fall. Der gesamte Inhalt dieses Artikels basiert auf dieser Prämisse, und die Ergebnisse können in einer nicht zutreffenden Umgebung abweichen.
Warum wird es als "0.1" angezeigt, obwohl ich eine Zahl anzeige, die nicht 0.1 ist? Das liegt daran, dass die Methode "to_s" beim Festlegen eines Float-Objekts für "Puts" zunächst in ein String-Objekt mit dem Namen "Dezimalzahl-String" konvertiert wird. Das Ergebnis ist jedoch der String "0,1". Ist. Im Gegensatz zu binär → binär macht die binäre → dezimale Umwandlung keinen endlichen Bruch in einen unendlichen Bruch [^ go]. Tatsächlich ist das durch das Gleitkomma-Literal "0.1" dargestellte Float-Objekt (die durch dargestellte Zahl) in Dezimalschreibweise.
[^ go]: Dies liegt daran, dass die Basis 10 ein Vielfaches von 2 ist.
0.1000000000000000055511151231257827021181583404541015625
Es scheint ein endlicher Bruch mit 55 Nachkommastellen zu sein (es sei denn, ich habe irgendwo einen Fehler gemacht).
Rubys Float # to_s Methode gibt jedoch keine solche Zeichenfolge zurück.
Es wird nur die Anzahl der Stellen verwendet, die das Float-Objekt haben kann, und es wird die Zeichenfolge "0.1" zurückgegeben. Dies ist eine Spezifikation von to_s.
(Ich bin damit nicht sehr vertraut. Wenn Sie also Fehler oder Ergänzungen haben, bitte.)
Sehen wir uns ein Beispiel an, in dem sich das Ergebnis zwischen "sum" und "inj ((+)" unterscheidet, was das Hauptthema ist.
numbers = [0.1] * 6
puts numbers.sum == numbers.inject(:+)
# => false
Die Summe der sechs "0,1" stimmt nicht überein (auch hier können die Ergebnisse je nach Umgebung variieren). Lassen Sie uns jedes Ergebnis mit "Puts" anzeigen.
numbers = [0.1] * 6
puts numbers.sum # => 0.6000000000000001
puts numbers.inject(:+) # => 0.6
Wenn Sie dies betrachten, machen Sie keinen schnellen Konsens darüber, dass "Eh?Inject (: +)genauer ist als sum! Liar!" [^ Ten].
[^ ten]: Es gibt eine Seite, die erklärt, dass "Puts" genauer sind als das Ergebnis des Hinzufügens von 10 0,1s, aber dies ist auch nicht gültig.
Wie wir bereits gesehen haben, ist die Zahl, die durch das durch Rubys Gleitkomma-Literal "0.1" erzeugte Float-Objekt dargestellt wird, nicht 0.1.
Übrigens wird das Ergebnis der "Inject" -Version als "0,6" angezeigt, dies bedeutet jedoch nicht, dass der Rückgabewert 0,6 beträgt (ein Float-Objekt, das die Zahl darstellt). Das Ergebnis von to_s, dem Rückgabewert, ist nur die Zeichenfolge" 0.6 ".
Woher wissen Sie genau, was der Fehler ist? Verwenden Sie dazu Float # to_r, um das Float-Objekt in ein Rational-Objekt zu konvertieren. Diese Methode gibt ein rationales Objekt zurück, das genau der von Float dargestellten Zahl entspricht.
Es ist so.
puts 0.1.to_r
# => 3602879701896397/36028797018963968
Irgendwie wurde ein großer Bruchteil angezeigt, aber es ist kein Fehler. Ein "Float" -Objekt, das auf dem "0.1" -Literal basiert, repräsentiert eine solche Zahl. Auf den ersten Blick sieht es aus wie eine Folge von Zahlen, aber wenn Sie genau hinschauen, sind die Zahlen im Molekül und im Nenner bis auf das Ende gleich und die Anzahl der Moleküle ist eine Ziffer weniger. Mit anderen Worten ist ersichtlich, dass es sehr nahe am numerischen Wert von 0,1 liegt.
Wenn Sie es zu Rational bringen, gibt es keinen Berechnungsfehler zusätzlich zu Subtraktion, Multiplikation und Division. Lass es uns so machen. Die Gesamtsumme, die nach der Erstellung von Rational entnommen wurde, wird als "wahre Summe" bezeichnet. Der absolute Wert ** der Differenz ** zwischen der durch "sum" und "injizieren" erzeugten Summe und der wahren Summe ** wird als "Fehler" bezeichnet. Um zu vergleichen, welches den kleineren Fehler aufweist, berechnen Sie den Fehler der "Summen" -Version abzüglich des Fehlers der "Injektions" -Version. Wenn dies positiv ist, ist der Fehler der "Summen" -Version groß, und wenn er negativ ist, ist der Fehler der "Injektions" -Version groß.
#Nummer zum Hinzufügen
x = 0.1
#Nummer zum Hinzufügen
n = 6
#Wahre Summe (rational)
exact_sum = x.to_r * n
#Ein Array von n x
numbers = [x] * n
#Summe für Summe (rational)
sum_by_sum = numbers.sum.to_r
#Dieser Fehler
error_by_sum = (exact_sum - sum_by_sum).abs
#Rational durch Injektion
sum_by_inject = numbers.inject(:+).to_r
#Dieser Fehler
error_by_inject = (exact_sum - sum_by_inject).abs
#Vergleich
puts sum_by_sum - sum_by_inject # => 1/9007199254740992
puts error_by_sum - error_by_inject # => 0/1
Das? Die Summe der "Summen" -Version und die Summe der "Injektions" -Version unterscheiden sich zwar geringfügig, aber sind die Fehler genau gleich? Auf den ersten Blick ist es rätselhaft, aber nichts Seltsames. Dies liegt daran, dass der Absolutwert bei der Berechnung des "Fehlers" verwendet wird. Die Summe der Versionen "sum" und "injizieren" existiert im gleichen Abstand ** links und rechts von der wahren Summe. Der Wert der Summe selbst ist unterschiedlich, aber die Abweichung von der wahren Summe ist gleich.
"Hmm? War es dann eine Lüge zu sagen, dass" Summe "genauer ist als" Injizieren "?" Ich möchte, dass du die Geschichte bis zum Ende hörst [^ sho].
[^ sho]: Um ehrlich zu sein, habe ich dieses Ergebnis selbst gesehen und für einen Moment gedacht, dass etwas nicht stimmt.
In diesem Fall, dh wenn 6 "0,1" (Float by the Literal) addiert werden, gibt es keinen Unterschied in der Genauigkeit. Dies war ein Glücksfall für die "Inject" -Version. Gibt es dann einen Fall, in dem die "Summen" -Version tatsächlich näher an der wahren Summe liegt? Oder gibt es den umgekehrten Fall? Lassen Sie es uns wie folgt überprüfen. Die hinzuzufügende Zahl ist "0.1" (Float by the Literal), und die hinzuzufügende Zahl wird geändert.
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 sollte 1 zurückgeben, wenn die sum-Version einen größeren Fehler aufweist, -1, wenn das Gegenteil der Fall ist, und 0, wenn der Fehler der gleiche ist. ..
Das Ergebnis ist wie folgt.
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
Wie Sie sehen können, hatten 11 der 1 bis 100 die gleiche Fehlergröße. Alles andere ist in der "Summen" -Version kleiner. Immerhin im Rahmen dieses Experiments
Getroffen. Aber natürlich können die Ergebnisse eines solch einfachen Experiments nicht verallgemeinert werden. Jetzt kann ich nur noch an Kahans Algorithmus glauben und sicherstellen, dass ich im Rahmen der obigen Experimente die erwarteten Ergebnisse erhalte.
Übrigens gab es 7 Fälle, in denen die "Summen" -Version mit der wahren Summe übereinstimmte. Von diesen stimmten drei auch mit der "Inject" -Version überein.
Verwenden Sie sum anstelle von injizieren (: +), um die Summe zu erhalten.
Es ist einfacher und schneller. Und wenn der numerische Wert eine Gleitkommazahl ist, kann die Anhäufung von Fehlern unterdrückt werden.
Recommended Posts