[解決済み】float < integerの比較で4倍遅くなるものがあるのはなぜですか？

質問

浮動小数点数と整数を比較するとき、ある値の組は他の同じ大きさの値より評価にずっと時間がかかる。

例えば

>>> import timeit
>>> timeit.timeit("562949953420000.7 < 562949953421000") # run 1 million times
0.5387085462592742

しかし、floatやintegerをある量だけ小さくしたり大きくしたりすると、比較はもっと速く実行されます。

>>> timeit.timeit("562949953420000.7 < 562949953422000") # integer increased by 1000
0.1481498428446173
>>> timeit.timeit("562949953423001.8 < 562949953421000") # float increased by 3001.1
0.1459577925548956

比較演算子を変更する（例えば == または > を使用しても、タイムに顕著な影響はありません。

これは もっぱら 大きい値や小さい値を選ぶと比較は速くなるので、大きさとは関係ないのですが、ビットの並び方が悪いのではないかと思います。

明らかに、これらの値を比較することは、ほとんどのユースケースで十分すぎるほど高速です。私は、なぜPythonがある値のペアと他の値でより苦労しているように見えるのか、単に興味があるだけです。

解決方法は？

Pythonのソースコードにあるfloatオブジェクトのコメントで、そのことを認めています。

<ブロッククオート

比較はかなり悪夢です

なぜなら、Pythonの整数はfloatとは異なり、任意の大きさにすることができ、常に正確だからです。整数をfloatにキャストしようとすると、精度が落ち、比較が不正確になるかもしれません。floatを整数にキャストしようとしても、分数部分が失われるため、うまくいきません。

この問題を回避するために、Pythonは一連のチェックを行い、いずれかのチェックが成功した場合に結果を返します。2つの値の符号を比較し、整数が浮動小数点になるには大きすぎるかどうか、そして浮動小数点数の指数と整数の長さを比較します。これらのチェックがすべて失敗した場合、結果を得るために2つの新しいPythonオブジェクトを構築して比較する必要があります。

floatを比較する場合 v を整数/長さ w という、最悪のケースを想定しています。

• v と w は同じ符号（両方が正または両方が負）である。
• 整数の 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つの条件を満たしています。

どちらかの値を大きく（または小さく）することを選択すると、整数のビット数、または指数の値が変わるので、Pythonは高価な最終チェックを実行せずに比較結果を決定することができるのです。

これは、CPythonの実装言語に特有のものです。

---

比較の詳細

は float_richcompare 関数は、2 つの値の比較を処理します。 v と w .

以下は、この関数が実行するチェックを順を追って説明したものです。Pythonのソースにあるコメントは、関数が何をするのか理解するのにとても役に立つので、関連する部分にはそのまま残しています。また、これらのチェックを回答の末尾にリストとしてまとめました。

主なアイデアは、Pythonのオブジェクトをマッピングすることです。 v と w を2つの適切なC言語のダブルに変換します。 i と j というように、正しい結果を得るために簡単に比較することができます。Python 2とPython 3はどちらも同じ考え方でこれを行います(前者は単に int と long の型を別々に作成する必要があります)。

まず最初に確認することは v は間違いなく Python の float であり、それを C の double にマップします。 i . 次にこの関数は w も float であり、C 言語の double にマップされます。 j . これは，他のすべてのチェックを省略できるため，この関数にとって最良のケースと言えます．また，この関数は v は inf または nan :

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 . もしビットが多ければ、float として保持することはできないので、float よりも大きなサイズを指定する必要があります。 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;
    }

この時点から、次のことがわかります。 w は49ビット以上である。のように扱うと便利です。 w を正の整数とみなし、必要に応じて符号と比較演算子を変更する。

    if (nbits <= 48) {
        /* "Multiply both sides" by -1; this also swaps the
         * comparator.
         */
        i = -i;
        op = _Py_SwappedOp[op];
    }

ここで、この関数はfloatの指数を調べます。浮動小数点は（符号を無視して）シグニフィカント * 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 より小さい場合、float は 1 よりも小さくなります (つまり、どの整数よりも大きさが小さくなります)。あるいは、指数が w であれば、その v < |w| シグニフィカント * 2 なので ^指数 は2より小さい ^nbits .

この2つのチェックに失敗した場合，この関数は指数が w . これは、シグニフィカント * 2 ^指数 は2より大きい ^nbits というように v > |w| :

    if ((size_t)exponent > nbits) {
        i = 2.0;
        j = 1.0;
        goto Compare;
    }

このチェックがうまくいかなかった場合、float の指数が v は整数のビット数と同じです。 w .

2 つの値を比較する唯一の方法は、2 つの新しい Python 整数を v と w . の分数部分を破棄することです。 v を、整数部を2倍にして、1つ足す。 w も2倍になり、これら2つの新しいPythonオブジェクトを比較することで、正しい戻り値を得ることができます。小さな値の例で説明します。 4.65 < 4 は、比較によって決定されます。 (2*4)+1 == 9 < 8 == (2*4) (falseを返す)。

    {
        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がこれらの新しいオブジェクトを作成するときに行う追加のエラーチェックとガベージトラッキングは省いています。言うまでもなく、これはさらなるオーバーヘッドを追加し、質問で強調された値が他の値よりも比較に著しく時間がかかる理由を説明します。

---

比較機能で行われるチェックをまとめてみました。

をさせる。 v をfloatとし、C言語のdoubleとしてキャストします。今、もし w も浮動小数点数です。

• をチェックします。 w は nan または inf . その場合、この特殊なケースを w .

• そうでない場合、比較 v と w をC言語のダブルとして表現することで直接的に表現しています。

もし w は整数です。

• の符号を抽出する。 v と w . もしそれらが異なるなら、私たちは v と w が異なり、どちらの値が大きいか。

• ( 符号は同じです。 ) を確認する w は、float にするにはビットが多すぎます。 size_t ). もしそうなら w よりも大きい。 v .

• チェック項目 w は48ビット以下である。もしそうなら，精度を失うことなく安全にCのdoubleにキャストして v .

• ( w は48ビット以上である。ここで w を正の整数とみなし、比較演算子を適切に変更しました。 )

• 浮動小数点数の指数を考える v . もし指数が負であれば v よりも小さい。 1 であり、任意の正整数より小さい。そうでない場合，指数が w よりも小さくなければならない。 w .

• の指数が0になった場合 v のビット数より大きい。 w では v よりも大きい。 w .

• ( のビット数と同じ指数となる。 w . )

• 最終チェックです。スプリット v を整数部と分数部に分割する。整数部を2倍にして、分数部に1を足して補正する。次に整数の w . この2つの新しい整数を代わりに比較し、結果を得ます。