Mengapa beberapa perbandingan float <integer empat kali lebih lambat dari yang lain?

Ketika membandingkan pelampung dengan bilangan bulat, beberapa pasang nilai membutuhkan waktu lebih lama untuk dievaluasi daripada nilai lain dengan besaran yang sama.

Sebagai contoh:

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

Tetapi jika float atau integer dibuat lebih kecil atau lebih besar dengan jumlah tertentu, perbandingan berjalan jauh lebih cepat:

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

Mengubah operator perbandingan (misalnya menggunakan ==atau >sebagai gantinya) tidak mempengaruhi waktu dengan cara apa pun yang terlihat.

Ini tidak semata - mata terkait dengan besarnya karena memilih nilai yang lebih besar atau lebih kecil dapat menghasilkan perbandingan yang lebih cepat, jadi saya curiga ini tergantung pada beberapa cara yang disayangkan bit berbaris.

Jelas, membandingkan nilai-nilai ini lebih dari cukup cepat untuk sebagian besar kasus penggunaan. Saya hanya ingin tahu mengapa Python tampaknya lebih banyak berjuang dengan beberapa pasang nilai daripada dengan yang lain.

Sebuah komentar dalam kode sumber Python untuk objek float mengakui bahwa:

Perbandingan cukup banyak mimpi buruk

Ini terutama benar ketika membandingkan float dengan integer, karena, tidak seperti float, integer dengan Python bisa berukuran besar dan selalu tepat. Mencoba melemparkan bilangan bulat ke pelampung mungkin kehilangan presisi dan membuat perbandingan tidak akurat. Mencoba melemparkan pelampung ke bilangan bulat tidak akan berhasil karena bagian pecahan akan hilang.

Untuk mengatasi masalah ini, Python melakukan serangkaian pemeriksaan, mengembalikan hasilnya jika salah satu pemeriksaan berhasil. Ini membandingkan tanda-tanda dari dua nilai, lalu apakah bilangan bulat "terlalu besar" untuk menjadi pelampung, kemudian membandingkan eksponen float dengan panjang bilangan bulat. Jika semua pemeriksaan ini gagal, perlu untuk membangun dua objek Python baru untuk membandingkan untuk mendapatkan hasilnya.

Ketika membandingkan float vdengan integer / long w, kasus terburuknya adalah:

• vdan wmemiliki tanda yang sama (baik positif atau negatif),
• integer wmemiliki beberapa bit yang cukup yang dapat disimpan dalam size_ttipe (biasanya 32 atau 64 bit),
• integer wmemiliki setidaknya 49 bit,
• eksponen float vsama dengan jumlah bit dalam w.

Dan inilah tepatnya yang kita miliki untuk nilai-nilai dalam pertanyaan:

>>> import math
>>> math.frexp(562949953420000.7) # gives the float's (significand, exponent) pair
(0.9999999999976706, 49)
>>> (562949953421000).bit_length()
49

Kita melihat bahwa 49 adalah eksponen float dan jumlah bit dalam bilangan bulat. Kedua angka positif dan keempat kriteria di atas terpenuhi.

Memilih salah satu nilai yang lebih besar (atau lebih kecil) dapat mengubah jumlah bit integer, atau nilai eksponen, sehingga Python dapat menentukan hasil perbandingan tanpa melakukan pemeriksaan akhir yang mahal.

Ini khusus untuk implementasi bahasa CPython.

Perbandingannya lebih detail

The float_richcompareFungsi menangani perbandingan antara dua nilai vdan w.

Di bawah ini adalah deskripsi langkah-demi-langkah dari pemeriksaan yang dilakukan fungsi. Komentar dalam sumber Python sebenarnya sangat membantu ketika mencoba memahami apa fungsinya, jadi saya meninggalkannya di tempat yang relevan. Saya juga meringkas cek-cek ini dalam daftar di bagian bawah jawabannya.

Ide utamanya adalah untuk memetakan objek Python vdan wdua C yang sesuai ganda, idan j, yang kemudian dapat dengan mudah dibandingkan untuk memberikan hasil yang benar. Baik Python 2 dan Python 3 menggunakan ide yang sama untuk melakukan ini (yang sebelumnya hanya menangani intdan longmengetik secara terpisah).

Hal pertama yang harus dilakukan adalah memeriksa apakah vitu benar-benar float Python dan memetakannya ke C ganda i. Selanjutnya fungsi melihat apakah wjuga float dan memetakannya ke C ganda j. Ini adalah skenario terbaik untuk fungsi karena semua pemeriksaan lainnya dapat dilewati. Pemeriksaan fungsi juga untuk melihat apakah vadalah infatau 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;
    }

Sekarang kita tahu bahwa jika wgagal memeriksa ini, itu bukan float Python. Sekarang fungsinya memeriksa apakah itu bilangan bulat Python. Jika demikian, tes termudah adalah mengekstraksi tanda vdan tanda w(kembali 0jika nol, -1jika negatif, 1jika positif). Jika tanda-tandanya berbeda, ini semua informasi yang diperlukan untuk mengembalikan hasil perbandingan:

    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;
        }
    }   

Jika pemeriksaan ini gagal, maka vdan wmemiliki tanda yang sama.

Pemeriksaan selanjutnya menghitung jumlah bit dalam bilangan bulat w. Jika bitnya terlalu banyak, maka tidak mungkin disimpan sebagai float dan karenanya harus lebih besar daripada 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;
    }

Di sisi lain, jika integer wmemiliki 48 bit atau lebih sedikit, ia dapat dengan aman diubah menjadi C ganda jdan membandingkan:

    if (nbits <= 48) {
        j = PyLong_AsDouble(w);
        /* It's impossible that <= 48 bits overflowed. */
        assert(j != -1.0 || ! PyErr_Occurred());
        goto Compare;
    }

Dari titik ini dan seterusnya, kita tahu bahwa wmemiliki 49 bit atau lebih. Akan nyaman untuk diperlakukan wsebagai bilangan bulat positif, jadi ubah tanda dan operator pembanding sesuai kebutuhan:

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

Sekarang fungsinya terlihat pada eksponen float. Ingat bahwa pelampung dapat ditulis (tanda abaikan) sebagai signifikansi * 2 ^eksponen dan yang signifikan mewakili angka antara 0,5 dan 1:

    (void) frexp(i, &exponent);
    if (exponent < 0 || (size_t)exponent < nbits) {
        i = 1.0;
        j = 2.0;
        goto Compare;
    }

Ini memeriksa dua hal. Jika eksponen kurang dari 0 maka float lebih kecil dari 1 (dan besarnya lebih kecil dari bilangan bulat apa pun). Atau, jika eksponen kurang dari jumlah bit wmaka kita memiliki itu v < |w|karena signifikansi * 2 ^eksponen kurang dari 2 ^nbits .

Gagal dari kedua pemeriksaan ini, fungsinya terlihat untuk melihat apakah eksponen lebih besar dari jumlah bit w. Ini menunjukkan bahwa signifikansi * 2 ^eksponen lebih besar dari 2 ^nbits dan karenanya v > |w|:

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

Jika pemeriksaan ini tidak berhasil, kita tahu bahwa eksponen float vsama dengan jumlah bit dalam bilangan bulat w.

Satu-satunya cara kedua nilai dapat dibandingkan sekarang adalah dengan membangun dua bilangan bulat Python baru dari vdan w. Idenya adalah untuk membuang bagian fraksional v, menggandakan bagian integer, dan kemudian menambahkan satu. wjuga dua kali lipat dan dua objek Python baru ini dapat dibandingkan untuk memberikan nilai kembali yang benar. Menggunakan contoh dengan nilai kecil, 4.65 < 4akan ditentukan oleh perbandingan (2*4)+1 == 9 < 8 == (2*4)(return 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
    }
}

Untuk singkatnya saya telah meninggalkan tambahan pemeriksaan kesalahan dan pelacakan sampah yang harus dilakukan Python ketika membuat objek baru ini. Tidak perlu dikatakan, ini menambah overhead tambahan dan menjelaskan mengapa nilai-nilai yang disorot dalam pertanyaan jauh lebih lambat dibandingkan dibandingkan yang lain.

Berikut ini adalah ringkasan dari pemeriksaan yang dilakukan oleh fungsi perbandingan.

Membiarkan vmenjadi pelampung dan melemparkannya sebagai C ganda. Sekarang, jika wjuga pelampung:

• Periksa apakah wini nanatau inf. Jika demikian, pegang kasing khusus ini secara terpisah tergantung pada jenis w.

• Jika tidak, bandingkan vdan wlangsung dengan representasi mereka sebagai C berlipat ganda.

Jika wbilangan bulat:

• Ekstrak tanda-tanda vdan w. Jika mereka berbeda maka kita tahu vdan wberbeda dan mana yang nilainya lebih besar.

• ( Tanda-tandanya sama. ) Periksa apakah wbit terlalu banyak untuk mengapung (lebih dari size_t). Jika demikian, wmemiliki besaran lebih besar dari v.

• Periksa apakah wmemiliki 48 bit atau lebih sedikit. Jika demikian, dapat dengan aman dilemparkan ke C ganda tanpa kehilangan presisi dan dibandingkan dengan v.

• ( wmemiliki lebih dari 48 bit. Sekarang kami akan memperlakukan wsebagai bilangan bulat positif setelah mengubah op pembanding yang sesuai. )

• Pertimbangkan eksponen float v. Jika eksponen negatif, maka vkurang dari 1dan karena itu kurang dari bilangan bulat positif. Lain, jika eksponen kurang dari jumlah bit wmaka itu harus kurang dari w.

• Jika eksponen vlebih besar dari jumlah bit wmaka vlebih besar dari w.

• ( Eksponen sama dengan jumlah bit dalam w. )

• Pemeriksaan terakhir. Dibagi vmenjadi bagian bilangan bulat dan pecahannya. Gandakan bagian integer dan tambahkan 1 untuk mengkompensasi bagian fraksional. Sekarang gandakan integer w. Bandingkan kedua bilangan bulat baru ini untuk mendapatkan hasilnya.

Menggunakan gmpy2dengan float presisi presisi dan bilangan bulat dimungkinkan untuk mendapatkan kinerja perbandingan yang lebih seragam:

~ $ ptipython
Python 3.5.1 |Anaconda 4.0.0 (64-bit)| (default, Dec  7 2015, 11:16:01) 
Type "copyright", "credits" or "license" for more information.

IPython 4.1.2 -- An enhanced Interactive Python.
?         -> Introduction and overview of IPython's features.
%quickref -> Quick reference.
help      -> Python's own help system.
object?   -> Details about 'object', use 'object??' for extra details.

In [1]: import gmpy2

In [2]: from gmpy2 import mpfr

In [3]: from gmpy2 import mpz

In [4]: gmpy2.get_context().precision=200

In [5]: i1=562949953421000

In [6]: i2=562949953422000

In [7]: f=562949953420000.7

In [8]: i11=mpz('562949953421000')

In [9]: i12=mpz('562949953422000')

In [10]: f1=mpfr('562949953420000.7')

In [11]: f<i1
Out[11]: True

In [12]: f<i2
Out[12]: True

In [13]: f1<i11
Out[13]: True

In [14]: f1<i12
Out[14]: True

In [15]: %timeit f<i1
The slowest run took 10.15 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 441 ns per loop

In [16]: %timeit f<i2
The slowest run took 12.55 times longer than the fastest. This could mean that an intermediate result is being cached.
10000000 loops, best of 3: 152 ns per loop

In [17]: %timeit f1<i11
The slowest run took 32.04 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 269 ns per loop

In [18]: %timeit f1<i12
The slowest run took 36.81 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 231 ns per loop

In [19]: %timeit f<i11
The slowest run took 78.26 times longer than the fastest. This could mean that an intermediate result is being cached.
10000000 loops, best of 3: 156 ns per loop

In [20]: %timeit f<i12
The slowest run took 21.24 times longer than the fastest. This could mean that an intermediate result is being cached.
10000000 loops, best of 3: 194 ns per loop

In [21]: %timeit f1<i1
The slowest run took 37.61 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 275 ns per loop

In [22]: %timeit f1<i2
The slowest run took 39.03 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 259 ns per loop