浮動小数点数と整数を比較する場合、一部の値のペアは、同様の大きさの他の値よりも評価に非常に長い時間がかかります。
例えば：
>>> import timeit
>>> timeit.timeit("562949953420000.7 < 562949953421000") # run 1 million times
0.5387085462592742
しかし、浮動小数点数または整数を特定の量だけ小さくしたり大きくしたりすると、比較ははるかに速く実行されます。
>>> timeit.timeit("562949953420000.7 < 562949953422000") # integer increased by 1000
0.1481498428446173
>>> timeit.timeit("562949953423001.8 < 562949953421000") # float increased by 3001.1
0.1459577925548956
比較演算子を変更しても (==またはを>代わりに使用する場合など)、時間に顕著な影響はありません。
これは大きさだけに関連するものではありません。より大きい値またはより小さい値を選択すると比較が速くなる可能性があるため、ビットの並び方が不幸なことに起因しているのではないかと考えています。
明らかに、これらの値の比較は、ほとんどのユースケースでは十分以上の速さです。私は単に、Python が他の値ペアよりも一部の値ペアで苦労するように見える理由が知りたいだけです。
ベストアンサー1
float オブジェクトの Python ソース コード内のコメントでは、次のことが認められています。
これは、浮動小数点数と整数を比較する場合に特に当てはまります。浮動小数点数とは異なり、Python の整数は任意の大きさにすることができ、常に正確だからです。整数を浮動小数点数にキャストしようとすると、精度が失われ、比較が不正確になる可能性があります。浮動小数点数を整数にキャストしても、小数部分が失われるため、うまくいきません。
この問題を回避するために、Python は一連のチェックを実行し、チェックの 1 つが成功した場合に結果を返します。2 つの値の符号を比較し、次に整数が浮動小数点数として「大きすぎる」かどうかを比較し、次に浮動小数点数の指数を整数の長さと比較します。これらのチェックがすべて失敗した場合、結果を取得するために比較する 2 つの新しい Python オブジェクトを作成する必要があります。
float をvinteger/long と比較する場合w、最悪のケースは次のようになります。
vw同じ符号（両方とも正または両方とも負）を持つ、- 整数は
w、保持できるビット数が十分少ないため、size_tタイプ（通常は32または64ビット）、 - 整数は
w少なくとも49ビットである。 - 浮動小数点数の指数は、
vのビット数と同じですw。
そして、これはまさに質問の値です。
>>> import math
>>> math.frexp(562949953420000.7) # gives the float's (significand, exponent) pair
(0.9999999999976706, 49)
>>> (562949953421000).bit_length()
49
49 は浮動小数点数の指数と整数のビット数の両方であることがわかります。両方の数値は正なので、上記の 4 つの条件が満たされます。
値の 1 つを大きく (または小さく) 選択すると、整数のビット数または指数の値が変わる可能性があるため、Python はコストのかかる最終チェックを実行せずに比較の結果を決定できます。
これは言語の CPython 実装に固有のものです。
より詳細な比較
のfloat_richcompare関数は2 つの値の比較を処理しますv。w
以下は、関数が実行するチェックのステップごとの説明です。Python ソース内のコメントは、関数が何を行うかを理解する際に非常に役立つため、関連する箇所に残しておきました。また、回答の末尾にこれらのチェックをまとめたリストも用意しました。
主なアイデアは、Python オブジェクトvとをw2 つの適切な C double とにマップすることです。iこれjにより、簡単に比較して正しい結果が得られます。Python 2 と Python 3 はどちらも同じアイデアを使用してこれを行います (前者は、intとlong型を別々に処理するだけです)。
最初に行うことは、 がv確実に Python float であるかどうかを確認し、それを C double にマップすることですi。次に、関数はwも float であるかどうかを確認し、それを C double にマップします。これは、他のすべてのチェックをスキップできるため、関数にとって最良のシナリオです。関数は、 または であるjかどうかも確認します。vinfnan
static PyObject*
float_richcompare(PyObject *v, PyObject *w, int op)
{
double i, j;
int r = 0;
assert(PyFloat_Check(v));
i = PyFloat_AS_DOUBLE(v);
if (PyFloat_Check(w))
j = PyFloat_AS_DOUBLE(w);
else if (!Py_IS_FINITE(i)) {
if (PyLong_Check(w))
j = 0.0;
else
goto Unimplemented;
}
wこれで、これらのチェックに失敗した場合、Python の float ではないことが分かりました。次に、関数は Python の整数かどうかをチェックします。この場合、最も簡単なテストは、の符号vと の符号w(0ゼロの場合は 、-1負の場合は 、1正の場合は ) を抽出することです。符号が異なる場合、比較の結果を返すために必要な情報はこれだけです。
else if (PyLong_Check(w)) {
int vsign = i == 0.0 ? 0 : i < 0.0 ? -1 : 1;
int wsign = _PyLong_Sign(w);
size_t nbits;
int exponent;
if (vsign != wsign) {
/* Magnitudes are irrelevant -- the signs alone
* determine the outcome.
*/
i = (double)vsign;
j = (double)wsign;
goto Compare;
}
}
このチェックが失敗した場合、vと はw同じ符号を持ちます。
次のチェックでは、整数のビット数を数えますw。ビット数が多すぎる場合は、浮動小数点数として保持できないため、浮動小数点数よりも大きい値にする必要がありますv。
nbits = _PyLong_NumBits(w);
if (nbits == (size_t)-1 && PyErr_Occurred()) {
/* This long is so large that size_t isn't big enough
* to hold the # of bits. Replace with little doubles
* that give the same outcome -- w is so large that
* its magnitude must exceed the magnitude of any
* finite float.
*/
PyErr_Clear();
i = (double)vsign;
assert(wsign != 0);
j = wsign * 2.0;
goto Compare;
}
一方、整数wが 48 ビット以下の場合は、安全に C の double に変換してj比較することができます。
if (nbits <= 48) {
j = PyLong_AsDouble(w);
/* It's impossible that <= 48 bits overflowed. */
assert(j != -1.0 || ! PyErr_Occurred());
goto Compare;
}
ここからは、 がw49 ビット以上であることがわかります。 を正の整数として扱うと便利なのでw、必要に応じて符号と比較演算子を変更します。
if (nbits <= 48) {
/* "Multiply both sides" by -1; this also swaps the
* comparator.
*/
i = -i;
op = _Py_SwappedOp[op];
}
ここで、関数は浮動小数点数の指数を調べます。浮動小数点数は (符号を無視して) 仮数 * 2指数として記述でき、仮数は 0.5 から 1 の間の数値を表すことを思い出してください。
(void) frexp(i, &exponent);
if (exponent < 0 || (size_t)exponent < nbits) {
i = 1.0;
j = 2.0;
goto Compare;
}
これは 2 つのことをチェックします。指数が 0 未満の場合、浮動小数点は 1 未満です (したがって、どの整数よりも大きさが小さくなります)。または、指数がビット数より小さい場合は、仮数 * 2指数が 2 nbits未満であるため、w次のようになります。v < |w|
これら 2 つのチェックに失敗した場合、関数は指数が のビット数より大きいかどうかを確認しますw。これは、仮数 * 2指数が 2 nbitsv > |w|より大きいことを示しています。
if ((size_t)exponent > nbits) {
i = 2.0;
j = 1.0;
goto Compare;
}
このチェックが成功しなかった場合、浮動小数点数の指数vが整数のビット数と同じであることがわかりますw。
2 つの値を比較できる唯一の方法は、 と から 2 つの新しい Python 整数を作成することですv。の小数部を破棄し、整数部分を 2 倍にして、1 を加算するwという考え方です。も 2 倍になり、これら 2 つの新しい Python オブジェクトを比較して正しい戻り値を得ることができます。 値が小さい例を使用すると、は比較によって決定されます(false を返します)。vw4.65 < 4(2*4)+1 == 9 < 8 == (2*4)
{
double fracpart;
double intpart;
PyObject *result = NULL;
PyObject *one = NULL;
PyObject *vv = NULL;
PyObject *ww = w;
// snip
fracpart = modf(i, &intpart); // split i (the double that v mapped to)
vv = PyLong_FromDouble(intpart);
// snip
if (fracpart != 0.0) {
/* Shift left, and or a 1 bit into vv
* to represent the lost fraction.
*/
PyObject *temp;
one = PyLong_FromLong(1);
temp = PyNumber_Lshift(ww, one); // left-shift doubles an integer
ww = temp;
temp = PyNumber_Lshift(vv, one);
vv = temp;
temp = PyNumber_Or(vv, one); // a doubled integer is even, so this adds 1
vv = temp;
}
// snip
}
}
簡潔にするために、Python がこれらの新しいオブジェクトを作成するときに行う追加のエラー チェックとガベージ トラッキングは省略しました。言うまでもなく、これによりオーバーヘッドが追加され、質問で強調表示された値が他の値よりも比較に大幅に時間がかかる理由が説明されます。
比較機能によって実行されるチェックの概要を次に示します。
を floatとしv、それを C double としてキャストします。ここで、wも float の場合:
が または
wであるかどうかを確認します。 そうである場合、 のタイプに応じてこの特殊なケースを個別に処理します。naninfwそうでない場合は、C 倍精度浮動小数点数として表現して直接比較
vします。w
wが整数の場合:
vとの符号を抽出しますw。 これらが異なる場合は、vとwが異なること、およびどちらが大きい値であるかがわかります。(の符号は同じです。 )
wのビット数が多すぎて浮動小数点数にならないかどうか ( より大きいかどうかsize_t) を確認します。多すぎる場合は、wの絶対値は より大きいですv。のビット数が 48 以下かどうかを確認します
w。その場合、精度を失うことなく安全に C double にキャストし、 と比較できますv。(
wは 48 ビットを超えています。w比較演算を適切に変更して、正の整数として扱うようになりました。 )浮動小数点数の指数について考えます
v。指数が負の場合、 はvより小さくなり1、したがって任意の正の整数より小さくなります。そうでない場合、指数が のビット数より小さい場合、wは より小さくなければなりませんw。の指数
vが のビット数より大きい場合w、vは より大きくなりますw。(指数は のビット数と同じです
w。 )最終チェック。
v整数部分と小数部分に分割します。整数部分を 2 倍にして、小数部分を補正するために 1 を加えます。次に、整数を 2 倍にしますw。代わりに、この 2 つの新しい整数を比較して結果を取得します。