全探索で愚直に一回書いてみる。
// for i in 0 ..< x.count でも動く。 for i in 0..<(x.count - 1) { for j in (i + 1)..<x.count { if x[i] == x[j] { answer += 1 } } }
fn main() { // Rustの文末には絶対にセミコロン先生をつける let x = [1, 2, 3, 1]; let mut answer = 0; // x.len() で配列の長さを取得し、最後の要素まで i をループ for i in 0..x.len() - 1 { for j in (i + 1)..x.len() { if x[i] == x[j] { answer += 1; } } } // println! の「ln」は「line（行）」を意味している。 // 改行付きで出力するマクロ。 println!("{}", answer); }
上記の2つのコードは全探索なので、計算量はO(n2)になる。 明日はもう少し効率が良い方法を考える。
※ こちらは、公立千歳科学技術大学の大学祭にて開催されたゆるちとせで発表したLTの記事版です。
以下の計算を試してください：
let a: Double = 0.1 let b: Double = 0.2 let result = a + b print(result)
期待値は0.3です。
しかし、上記のコードの結果は「0.30000000000000004」になります。 これが丸め誤差です。
今日は、丸め誤差が発生する仕組みについてお話しします。
先ほどのコードに出てきたDoubleは浮動小数点数型の一種です。 浮動小数点数型とは、10進数の実数を、有限桁の2進数の近似値で表現する方法です。 …近似値？ちょっと引っかかる言い方ですね。 近似値の具体を確認するには、「基数変換」を知る必要があります。 おさらいしましょう。
今後の話の前提として、基数変換の方法をおさらいしましょう。 整数部と小数部で若干手順が異なります。
整数部を変換するときは、整数を2で割り続けて、余りを下から上へ並べる方法を使います。
小数部を変換する場合は、小数部分に2を掛け続け、積の整数部分を順に取り出します。
「近似値」の具体に迫りましょう。
先ほどの計算に出てきた0.1は、浮動小数点数において近似値として扱われる数です。
0.1を二進数に基数変換して、「近似値」の具体に迫りましょう。
循環している…？ つまり、0.1は循環小数になってしまうため、 2進数では有限桁数で表現できないのです。 先ほど、浮動小数点数は10進数の実数を、有限桁の2進数の近似値で表現する方法だと説明しました。 ここまでの話を踏まえると、丸め誤差は小数を有限桁の二進数で表現できない時に発生するものであることがわかります。
誤差が発生するにも関わらず浮動小数点数が活用される理由ってなんでしょう。 なにかしらかの、10進数に変わる優位性があるはずです。
そういえば、CPUは2進数で動きますよね。 メモリ的に嬉しい話が背景にありそうな予感がします。
結論から言うと、浮動小数点数の優位性は、 誤差が発生するリスクがあっても、効率的なメモリ利用と高速な演算が可能 な点にあります。
Double型とDecimal型のパフォーマンスの比較がしたいですね。 ベンチマークを取ってみました。 確かにDoubleのほうが早いですね。
一般的に、Decimalは高精度を提供する一方で、パフォーマンスが低いというトレードオフがあります。 したがって、パフォーマンスが重要な場合はDoubleやFloatが推奨され、正確さが求められる計算ではDecimalを選ぶべきです。
2つの方向性があります。 1. 整数で計算した後、10で割る 2. Decimalを使用する。
10進数の整数を2進数に変換する際は常に正確に基数変換できます。 10進数の整数は、単にその値を2の累乗の組み合わせとして表現するだけで済むからです。 10進数の小数を2進数に変換する際のみ、丸め誤差は問題になります。 （2の累乗とは、2を何回か掛けた数のことです。次のような数のことを指します：20 = 1、21 = 2、22 = 4、23 = 8、24 = 16） この方法は、Intで表現可能な範囲内でのみ使用できると言う制限があります。
10進数を使えば問題ないですよね。
許容可能な範囲であれば、DoubleやFloatで十分です。 数値の正確さが必須ではない場面では、むしろDouble・Floatを使うべきでしょう。 一方で、ユーザーに計算結果を見せる必要があるとき。電卓や株価の計算などにおいては、Decimal型を使用する方が適切です。
丸め誤差は、10進数を2進数で表現する際に発生する計算誤差です。浮動小数点数は、誤差を伴うものの、高速でメモリ効率が良いため、広く使用されています。 丸め誤差の回避方法として、整数で計算後に10で割る方法や、Decimal型を使用する手段があります。ただし、どちらも制限があります。 許容できる場面では、FloatやDoubleを選択し、正確さが求められる場面では、Decimalや他の方法を使用します。
近似等価性: 比較する際、誤差を許容したい場合に使う。 区間演算: 計算全体の誤差範囲を管理し、結果がある範囲内に収まることを保証したい場合に使う。
近似等価性は、浮動小数点数の計算で発生する微小な誤差を考慮しながら値を比較する時に役立ちます。 0.1と0.3を足した結果を0.4と比較する際、通常の比較では丸め誤差の影響で正確に一致しませんが、近似等価性を利用すれば、微小な差を許容して「ほぼ等しい」と判断できます。
区間演算は計算全体における誤差を管理する手法。 全ての計算を範囲として扱うことで、複数回の演算で発生する累積誤差を考慮しながら計算を進めることができる。
この記事が詳しいです。 Doubleで意図的に丸め誤差を発生させて、内部でどのような丸め処理が行われているのか解明しようとしています。 結論から言うと、浮動小数点数の丸めは「真の結果に最も近い値」で行われます。
当日話さなかったけど、調べた諸々を供養
ここからは私が実際にコードを書いていて、今日お話しした知識を活用した例を共有させてください。
以下のコードは失敗します。
val str = "111111111111" val num = str.toIntOrNull() // 変換失敗、nullになる
今日話した内容を踏まえるとなんとなく原因に予測が経ちますね。
Kotlinのドキュメントを見てみましょう：
Dobleで表現可能な範囲も確認してみます。
KotlinのDoubleは64ビットまで表現可能のようです。
String -> Doubleなら成功しそうですね。 試してみましょう。
val str = "111111111111" val num = str.toDoubleOrNull() // 変換成功、111111111111.0が返る
変換成功しました！！
今回は変換対象が整数で表現できる値だったのでこれでも問題ありません。 しかし、この方法には精度が犠牲になっているという問題があります。
Kotlinには、この問題を解決する型があります。 それがJavaから引き継いだBigIntegerです。 これは非常に大きな整数を精度を損なうことなく扱うために設計された型です。DoubleやFloatのような浮動小数点数と異なり、BigIntegerは整数を正確に表現でき、桁数が多くても丸め誤差や近似の影響を受けないという特徴があります。 SwiftにもBigIntというよく似た型が実装されています。 状況に応じて適宜使い分けていきましょう(?: 実行環境、CPUとかとこの話は関連しているんだろうか)
-> 10進数リテラルは、コンパイル時にLLVMコンパイラによって2進数に変換され、FPUによって処理されます。 （参考： Expression Integer Operators ） 詳細はよくわからないので調べます。
-> 調べます。 多分10をかけて、整数として扱って計算してるんじゃないかなって予感はする。。。。。。
第二回ができるように頑張ります。
ゆるちとせでご一緒した熊谷さんが実施された、浮動小数点数の発表スライド。私の発表を聞いた次に触れるとちょうど良さそうなレベル感でした。
忙しなくて、余裕のない半年だった。 特に、本業では6月から9月まで毎月260 ~ 300時間超コンスタントに労働(と労働に伴う研鑽)したこと、 また、8月にコアスタッフをやっているフロントエンドカンファレンス北海道が実施されたこともあり、プライベートが消滅していた。
一応まだ実務経験1年ちょいで、ぴよぴよもいいところ。 まだまだ知らないこと・学ぶべきことが個人的に山積している。
ちゃんとした自信を持ちたいなって気持ちがあって、そこに辿り着くには圧倒的な研鑽が一旦必要だなって思っている。 そうしないと、不安の正体が手に取れないような予感がしている。 今年後半戦はもっと、余裕を持って興味・関心と向き合いたいな・・・・・・
カンファレンススタッフ(熟練)の動きを間近で見れて、学びが大きかった。 京都時代の友人がブロックチェーン関係のコミュニティ代表として発表してて、うお〜〜〜ってなった。 わたしももっと励まねば。
友だちが増えた。(嬉しい) 夏の旭川、涼しくてお花綺麗でめちゃよかった。
めちゃめちゃ色々頑張った。 友だちが増えた。 来年もスタッフします。 魂を燃やしましょう。
後半も、前半の自分に負けないように精進したい。
