普通のプログラマなら直感的、反射神経的に理解しているような、
初歩的で単純な小ネタを記事にしていこうかと思います。
初歩的が故に、私のようなヘボなプログラマは、
(理解していたつもりでも)よくやらかします。
誤りや適切でない内容がある場合は、コメントいただければ、
修正、内容の調整等検討します。
今回は、
『破滅的プログラミングの末路#01 「整数の絶対値でやらかす」』
のコメント欄の投稿をネタ元に記事を書きました。
コメントいただいた方ありがとうございました。
1. 左辺と右辺の比較
プログラミングは、時に数学であり、時に数学ではありません。
数学のある分野では、
a > bなら、a - b > 0は正しいことでしょう。
プログラミングでは、
a > bは成り立っても、a - b > 0は成り立たないケースは多々あります。
同様に、
-
a < bは成り立っても、a - b < 0は成り立たない -
a <= bは成り立っても、a - b <= 0は成り立たない -
a >= bは成り立っても、a - b >= 0は成り立たない -
a == bは成り立っても、a - b == 0は成り立たない
ケースはたくさんあります。
2. 今回は整数型の話しです
今回は、整数型に限定して考えます。
浮動小数点型の場合は、また別の次元での注意も必要なので、
また別の機会に記事にしようと思います。
話を簡単にするために、
32bitの符号付き整数型を考えます。
JavaやC#、C/C++では、int型とか呼ばれているやつです。
(C/C++では、int型が32bitの処理系を想定。
人によっては、int32とかInt32を思い描いてもよいです。)
32ビットの符号付の整数型が表現できる範囲は多くのプログラミング言語の場合は、
-2147483648 から 2147483647
になっているはずです。
1.3. とりあえず、やってみよう
Java, C#あたりで、以下のようなコードを実行してみます。
a > bとa - b > 0の真偽値(TrueかFalseか)を表示しているだけです。
aとbに、いくつか値を入れて試してみます。
とりあえず、C#でやってみます。
JavaとかC/C++でやる場合も、画面出力部分がちょっと違うだけ。
// aとbそれぞれに、値を入れて、いろいろ試してみます。
int a = 100;
int b = 100;
// Javaなら、System.out.printf("a > b : %s%n", (a > b));とか。
Console.WriteLine("a > b : {0}", (a > b));
Console.WriteLine("a - b > 0 : {0}", (a - b > 0));
いくつか試すとこんな感じです。
| aの値 | bの値 | a > b | a - b > 0 |
|---|---|---|---|
| 100 | 100 | False | False |
| 100 | 50 | True | True |
| -2000000000 | 500000000 | False | True |
| 2000000000 | -500000000 | True | False |
上２つは、a > bとa - b > 0の真偽が一致していますが、
下２つは一致していません。
3. 四則演算でも、いつも注意は必要
加減乗除の四則演算(+, -, *, /)程度の単純な演算でも、いつも注意は必要です。
整数型の場合、
加減乗除(+, -, *, /)は、オーバーフローする可能性があります。
さらに、整数の除算(/)は、多くの言語・環境では、0で割るとエラー(例外、クラッシュなど)になります。
また、負の整数を含む除算では、難しい状況を生む場合があります。
例えば、
int a = 5;
int b = -2;
int answer = a / b;
などとやった場合、answerが、-2になる言語・環境や、-3になる言語・環境があります。
例えば、整数の割り算に切り落としの動作をするようになっていれば、-2ですが、
**Floor関数(床関数)**の動作をするようになっていれば、
演算結果より小さな整数値が採用されるので、-3になります。
同様に、負の整数を含む剰余演算(%)でも、言語・環境によって異なる動作をする場合があります。
整数の除算(/)では、オーバーフローしないと信じている方は、
(int型の最小値) / (-1)を試してみると良いかもしれません。
(この演算は、言語・環境によっては、特殊な扱いになっている場合もあります。)
少し話しがそれましたが、今回は、オーバーフローを考えていきます。
4. 引き算でオーバーフローするのを、うっかり忘れることがある
-2147483648 から 2147483647までしか表現できないのであれば、
加算(+)、乗算(*)で、オーバーフローする可能性があるのは、すぐ想像できると思います。
減算(-)で、オーバーフローする可能性も当然といえば当然ですが、
状況次第では、うっかり忘れてしまう場合があります。
以下、表現できる範囲を超えてオーバーフローしてしまう例です。
| 演算 | 手で計算した演算結果 | Javaで計算してみた結果 |
|---|---|---|
| 2147483647 + 5 | 2147483652 | -2147483644 |
| 2147483 * 10000 | 21474830000 | -6480 |
| 2147483647 - (-5) | 2147483652 | -2147483644 |
| -2147483648 - 5 | -2147483653 | 2147483643 |
一番下の演算は、負の範囲で表現できる下限を下回りますが、
これもオーバーフロー(負の方向へのオーバーフロー)したことになります。
これを「アンダーフロー」と呼ぶ人もいますが、一般的には、
浮動小数点の精度で表現できないほど、0に近い数値になった場合を、
アンダーフローと呼ぶのが正しいはず。
整数値における上記の状況を、アンダーフローというのは厳密には誤用。
(普通は話の流れで忖度できる範囲なので指摘するかまでは微妙。)
5. 末路
複雑な計算をするようなプログラムを組むときは、
オーバーフローには、そこそこ気が回ることも多いと思います。
単純なケースで、かつ、
一見すると今回の話しと直接結びつかないと思えるようなケースでやらかす可能性が考えられます。
具体的な例を１つあげると、
ComparatorやComparableインタフェースなどの、
オブジェクトのインスタンスの順序付けをする仕組みでやらかすケースが散見されるようです。
例えば、リスト内のインスタンスをプログラマの思い通りにソートさせたい場合などに使うやつです。
あるオブジェクトのインスタンスAとBがあった場合に、
順序としてどちらが先かを決定付けるために使うアレです。
クラスを使った例だと、コードが長くなるので、値型の例でいきます。
以下は、C#の例ですが、Javaでも似たような感じです。
最近だとラムダ式が使える言語が増えてきたので、ラムダ式で書きます。
(もう少しすっきり書けますが、分かりやすさ重視で冗長な書き方してます。)
// 整数値の配列
var array = new int[] { 3, 1, -2147483647, -5 };
// リストに格納
var list = new List<int>(array);
// ラムダ式で評価してソート
list.Sort(
(a, b) =>
{
return (a - b);
}
);
foreach (var item in list)
{
Console.WriteLine(item);
}
ポイントはラムダ式の部分です。
(a, b) =>
{
return (a - b);
}
ですが、
int compare(int a, int b)
{
return (a - b);
}
と考えると分かりやすいと思います。
多くのフレームワーク等では、Comparatorの比較メソッド、比較関数は、
-
aがbより小さい場合は、負の整数。 -
aとbが等しい場合は、0。 -
aがbより大きい場合は、正の整数。
を返すように実装することになっています。
この仕様であれば、プログラマなら、演算一発で求めたい気持ちは非常によく分かります。
アプリの仕様上(a - b)が、
オーバーフローする可能性がない範囲に収まることがはっきりしているのであれば、
return (a - b);でも問題ありません。
オーバーフローする可能性があるのであれば、期待したソート結果にならない場合があります。
上記のコード例では、小さい順に数値がソートされることを意図していますが、
結果は以下のようになります。
1
3
-2147483647
-5
全然、小さい順になってません。
元の配列array内の、初期の順番によっても結果が異なってくることにも注意。
5. 対策
基本的には、四則演算するならオーバーフローの可能性は常に注意が必要です。
Comparatorの例では、四則演算する必要がないのであれば、
四則演算しない実装にする方法もあります。
プログラミングでは、素朴でアホな実装な方が、現実的には安全であったり効率が良い場合も、
まあまああります。
今回の例では、arrayがint型の配列だったので、
そもそも自分でソートを定義する必要はないのですが、
自分で定義したオブジェクトのソートの場合に適当に読み替えて考えていただければと思います。
list.Sort(
(a, b) =>
{
int result = -1;
if( a > b )
{
result = 1;
}
else if( a == b )
{
result = 0;
}
return result;
}
);
とか、3項演算子使うなら、
list.Sort(
(a, b) =>
{
return (a > b) ? 1 : ((a == b) ? 0 : -1);
}
);
とか、素朴な実装なら、うまくいきます。
なお、比較対象のオブジェクトなどに、Comparableな実装があるなら、
それを活用するのが良いでしょう。
C#だと、
list.Sort(
(a, b) =>
{
return a.CompareTo(b);
}
);
のような感じです。
Javaの場合は、
Integer.compare(a, b)を利用するなどになると思います。