Pertanyaan Mengapa "1000000000000000 dalam jangkauan (1000000000000001)" begitu cepat dengan Python 3?


Itu adalah pemahaman saya bahwa range() fungsi, yang sebenarnya jenis objek dengan Python 3, menghasilkan isinya dengan cepat, mirip dengan generator.

Ini adalah kasusnya, saya akan mengharapkan baris berikut untuk mengambil banyak sekali waktu, karena untuk menentukan apakah 1 quadrillion berada dalam jangkauan, nilai quadrillion harus dihasilkan:

1000000000000000 in range(1000000000000001)

Lebih lanjut: tampaknya tidak peduli berapa banyak nol yang saya tambahkan, kalkulasi lebih banyak atau kurang membutuhkan jumlah waktu yang sama (pada dasarnya seketika).

Saya juga mencoba hal-hal seperti ini, tetapi perhitungannya masih hampir instan:

1000000000000000000000 in range(0,1000000000000000000001,10) # count by tens

Jika saya mencoba menerapkan fungsi jangkauan saya sendiri, hasilnya tidak begitu bagus !!

def my_crappy_range(N):
    i = 0
    while i < N:
        yield i
        i += 1
    return

Apakah yang range() melakukan objek di bawah kap yang membuatnya begitu cepat?


Jawaban Martijn Pieters dipilih karena kelengkapannya, tetapi juga lihat jawaban pertama abarnert untuk diskusi yang baik tentang apa artinya range menjadi penuh urutan dengan Python 3, dan beberapa informasi / peringatan mengenai potensi inkonsistensi untuk __contains__ optimasi fungsi di seluruh implementasi Python. jawaban lain abarnert masuk ke beberapa detail lebih lanjut dan menyediakan tautan bagi mereka yang tertarik dengan sejarah di balik pengoptimalan dengan Python 3 (dan kurangnya pengoptimalan xrange dengan Python 2). Jawaban dengan poke dan oleh wim memberikan kode sumber C yang relevan dan penjelasan bagi mereka yang tertarik.


1364
2018-05-06 15:32


asal


Jawaban:


The Python 3 range() objek tidak menghasilkan angka dengan segera; itu adalah objek urutan cerdas yang menghasilkan angka sesuai permintaan. Semua yang dikandungnya adalah nilai awal, berhenti, dan langkah Anda, kemudian saat Anda melakukan iterasi terhadap objek, integer berikutnya dihitung setiap iterasi.

Objek juga mengimplementasikan object.__contains__ menghubungkan, dan menghitung jika nomor Anda adalah bagian dari jangkauannya. Menghitung adalah O (1) operasi waktu konstan. Tidak pernah ada kebutuhan untuk memindai semua kemungkinan bilangan bulat dalam rentang.

Dari range() dokumentasi objek:

Keuntungan dari range ketik lebih dari biasa list atau tuple adalah bahwa objek rentang akan selalu mengambil jumlah memori yang sama (kecil), tidak peduli ukuran jangkauan yang diwakilinya (karena hanya menyimpan start, stop dan step nilai, menghitung item individual dan subrang seperlunya).

Jadi minimal, Anda range() objek akan melakukan:

class my_range(object):
    def __init__(self, start, stop=None, step=1):
        if stop is None:
            start, stop = 0, start
        self.start, self.stop, self.step = start, stop, step
        if step < 0:
            lo, hi = stop, start
        else:
            lo, hi = start, stop
        self.length = ((hi - lo - 1) // abs(step)) + 1

    def __iter__(self):
        current = self.start
        if self.step < 0:
            while current > self.stop:
                yield current
                current += self.step
        else:
            while current < self.stop:
                yield current
                current += self.step

    def __len__(self):
        return self.length

    def __getitem__(self, i):
        if i < 0:
            i += self.length
        if 0 <= i < self.length:
            return self.start + i * self.step
        raise IndexError('Index out of range: {}'.format(i))

    def __contains__(self, num):
        if self.step < 0:
            if not (self.stop < num <= self.start):
                return False
        else:
            if not (self.start <= num < self.stop):
                return False
        return (num - self.start) % self.step == 0

Ini masih kehilangan beberapa hal yang nyata range() mendukung (seperti .index() atau .count() metode, hashing, pengujian kesetaraan, atau pemotongan), tetapi seharusnya memberi Anda ide.

Saya juga menyederhanakan __contains__ implementasi untuk hanya fokus pada tes integer; jika kamu memberi yang nyata range() objek nilai non-integer (termasuk subclass dari int), pemindaian lambat dimulai untuk melihat apakah ada kecocokan, sama seperti jika Anda menggunakan uji penahanan terhadap daftar semua nilai yang terkandung. Ini dilakukan untuk terus mendukung jenis angka lain yang kebetulan mendukung pengujian kesetaraan dengan bilangan bulat tetapi tidak diharapkan untuk mendukung aritmatika bilangan bulat juga. Lihat yang asli Masalah Python yang mengimplementasikan uji kontainmen.


1351
2018-05-06 15:33



Kesalahpahaman mendasar di sini adalah dalam pemikiran itu range adalah generator. Ini bukan. Sebenarnya, ini bukan jenis iterator.

Anda dapat mengatakan ini dengan mudah:

>>> a = range(5)
>>> print(list(a))
[0, 1, 2, 3, 4]
>>> print(list(a))
[0, 1, 2, 3, 4]

Jika generator, iterating sekali akan menghabiskannya:

>>> b = my_crappy_range(5)
>>> print(list(b))
[0, 1, 2, 3, 4]
>>> print(list(b))
[]

Apa range sebenarnya, adalah urutan, seperti daftar. Anda bahkan dapat menguji ini:

>>> import collections.abc
>>> isinstance(a, collections.abc.Sequence)
True

Ini berarti harus mengikuti semua aturan menjadi urutan:

>>> a[3]         # indexable
3
>>> len(a)       # sized
5
>>> 3 in a       # membership
True
>>> reversed(a)  # reversible
<range_iterator at 0x101cd2360>
>>> a.index(3)   # implements 'index'
3
>>> a.count(3)   # implements 'count'
1

Perbedaan antara a range dan a list Apakah itu range adalah malas atau dinamis urutan; itu tidak mengingat semua nilai-nilainya, itu hanya mengingatnya start, stop, dan step, dan menciptakan nilai-nilai pada permintaan __getitem__.

(Sebagai catatan tambahan, jika Anda print(iter(a)), Anda akan melihat itu range menggunakan yang sama listiterator ketik sebagai list. Bagaimana cara kerjanya? SEBUAH listiterator tidak menggunakan sesuatu yang spesial list kecuali fakta bahwa ia menyediakan implementasi C __getitem__, sehingga berfungsi dengan baik untuk range terlalu.)


Sekarang, tidak ada yang mengatakan itu Sequence.__contains__ harus menjadi waktu yang konstan — sebenarnya, untuk contoh-contoh sekuens yang jelas seperti itu listtidak. Tapi tidak ada yang mengatakannya tidak bisa menjadi. Dan itu lebih mudah diterapkan range.__contains__ untuk hanya memeriksanya secara matematis ((val - start) % step, tetapi dengan beberapa kerumitan ekstra untuk menghadapi langkah-langkah negatif) daripada benar-benar menghasilkan dan menguji semua nilai, jadi mengapa seharusnya tidak itu melakukannya dengan cara yang lebih baik?

Tapi sepertinya tidak ada apa-apa dalam bahasa itu jaminan ini akan terjadi. Seperti yang ditunjukkan Ashwini Chaudhari, jika Anda memberikan nilai yang tidak terpisahkan, alih-alih mengkonversi ke integer dan melakukan tes matematika, itu akan jatuh kembali ke iterasi semua nilai dan membandingkannya satu per satu. Dan hanya karena versi CPython 3.2+ dan PyPy 3.x kebetulan memuat pengoptimalan ini, dan ini adalah ide yang jelas bagus dan mudah dilakukan, tidak ada alasan bahwa IronPython atau NewKickAssPython 3.x tidak dapat meninggalkannya. (Dan sebenarnya CPython 3.0-3.1 tidak termasuk itu.)


Jika range sebenarnya adalah generator, seperti my_crappy_range, maka tidak masuk akal untuk menguji __contains__ cara ini, atau setidaknya cara itu masuk akal tidak akan jelas. Jika Anda sudah mengulang 3 nilai pertama, adalah 1 masih in generator? Harus menguji untuk 1 menyebabkan iterate dan mengkonsumsi semua nilai hingga 1 (atau hingga nilai pertama >= 1)?


561
2018-05-06 16:01



Menggunakan sumber, Luke!

Di CPython, range(...).__contains__ (pembungkus metode) pada akhirnya akan mendelegasikan ke perhitungan sederhana yang memeriksa apakah nilai mungkin berada dalam jangkauan. Alasan untuk kecepatan di sini adalah kami gunakan penalaran matematis tentang batas, bukan iterasi langsung dari objek jangkauan. Untuk menjelaskan logika yang digunakan:

  1. Periksa apakah jumlahnya antara start dan stop, dan
  2. Periksa bahwa nilai langkahnya tidak "melangkahi" nomor kami.

Sebagai contoh, 994 dalam range(4, 1000, 2) karena:

  1. 4 <= 994 < 1000, dan
  2. (994 - 4) % 2 == 0.

Kode C lengkap disertakan di bawah ini, yang sedikit lebih lengkap karena manajemen memori dan rincian penghitungan referensi, tetapi ide dasarnya ada di sana:

static int
range_contains_long(rangeobject *r, PyObject *ob)
{
    int cmp1, cmp2, cmp3;
    PyObject *tmp1 = NULL;
    PyObject *tmp2 = NULL;
    PyObject *zero = NULL;
    int result = -1;

    zero = PyLong_FromLong(0);
    if (zero == NULL) /* MemoryError in int(0) */
        goto end;

    /* Check if the value can possibly be in the range. */

    cmp1 = PyObject_RichCompareBool(r->step, zero, Py_GT);
    if (cmp1 == -1)
        goto end;
    if (cmp1 == 1) { /* positive steps: start <= ob < stop */
        cmp2 = PyObject_RichCompareBool(r->start, ob, Py_LE);
        cmp3 = PyObject_RichCompareBool(ob, r->stop, Py_LT);
    }
    else { /* negative steps: stop < ob <= start */
        cmp2 = PyObject_RichCompareBool(ob, r->start, Py_LE);
        cmp3 = PyObject_RichCompareBool(r->stop, ob, Py_LT);
    }

    if (cmp2 == -1 || cmp3 == -1) /* TypeError */
        goto end;
    if (cmp2 == 0 || cmp3 == 0) { /* ob outside of range */
        result = 0;
        goto end;
    }

    /* Check that the stride does not invalidate ob's membership. */
    tmp1 = PyNumber_Subtract(ob, r->start);
    if (tmp1 == NULL)
        goto end;
    tmp2 = PyNumber_Remainder(tmp1, r->step);
    if (tmp2 == NULL)
        goto end;
    /* result = ((int(ob) - start) % step) == 0 */
    result = PyObject_RichCompareBool(tmp2, zero, Py_EQ);
  end:
    Py_XDECREF(tmp1);
    Py_XDECREF(tmp2);
    Py_XDECREF(zero);
    return result;
}

static int
range_contains(rangeobject *r, PyObject *ob)
{
    if (PyLong_CheckExact(ob) || PyBool_Check(ob))
        return range_contains_long(r, ob);

    return (int)_PySequence_IterSearch((PyObject*)r, ob,
                                       PY_ITERSEARCH_CONTAINS);
}

"Daging" dari ide tersebut disebutkan dalam garis:

/* result = ((int(ob) - start) % step) == 0 */ 

Sebagai catatan akhir - lihatlah range_contains berfungsi di bagian bawah snipet kode. Jika pemeriksaan tipe yang tepat gagal maka kita tidak menggunakan algoritma pintar yang dijelaskan, alih-alih jatuh kembali ke pencarian iterasi dungu dari jangkauan menggunakan _PySequence_IterSearch! Anda dapat memeriksa perilaku ini di interpreter (saya menggunakan v3.5.0 di sini):

>>> x, r = 1000000000000000, range(1000000000000001)
>>> class MyInt(int):
...     pass
... 
>>> x_ = MyInt(x)
>>> x in r  # calculates immediately :) 
True
>>> x_ in r  # iterates for ages.. :( 
^\Quit (core dumped)

285
2018-05-06 15:41



Untuk menambah jawaban Martijn, ini adalah bagian yang relevan sumber (dalam C, karena objek rentang ditulis dalam kode asli):

static int
range_contains(rangeobject *r, PyObject *ob)
{
    if (PyLong_CheckExact(ob) || PyBool_Check(ob))
        return range_contains_long(r, ob);

    return (int)_PySequence_IterSearch((PyObject*)r, ob,
                                       PY_ITERSEARCH_CONTAINS);
}

Jadi untuk PyLong objek (yang mana int dengan Python 3), ia akan menggunakan range_contains_long berfungsi untuk menentukan hasilnya. Dan fungsi itu pada dasarnya memeriksa apakah ob berada dalam kisaran yang ditentukan (meskipun terlihat sedikit lebih kompleks dalam C).

Jika bukan int objek, itu jatuh kembali ke iterasi sampai menemukan nilai (atau tidak).

Seluruh logika bisa diterjemahkan ke pseudo-Python seperti ini:

def range_contains (rangeObj, obj):
    if isinstance(obj, int):
        return range_contains_long(rangeObj, obj)

    # default logic by iterating
    return any(obj == x for x in rangeObj)

def range_contains_long (r, num):
    if r.step > 0:
        # positive step: r.start <= num < r.stop
        cmp2 = r.start <= num
        cmp3 = num < r.stop
    else:
        # negative step: r.start >= num > r.stop
        cmp2 = num <= r.start
        cmp3 = r.stop < num

    # outside of the range boundaries
    if not cmp2 or not cmp3:
        return False

    # num must be on a valid step inside the boundaries
    return (num - r.start) % r.step == 0

106
2018-05-06 15:41



Jika Anda bertanya-tanya Mengapa optimasi ini ditambahkan ke range.__contains__, dan mengapa tidak ditambahkan ke xrange.__contains__ di 2.7:

Pertama, ketika Ashwini Chaudhary menemukan, masalah 1766304 dibuka secara eksplisit untuk mengoptimalkan [x]range.__contains__. Patch untuk ini diterima dan diperiksa untuk 3.2, tetapi tidak di-backport ke 2,7 karena "xrange telah berperilaku seperti ini untuk waktu yang lama sehingga saya tidak melihat apa yang membeli kita untuk melakukan patch ini terlambat." (2,7 hampir keluar pada saat itu.)

Sementara itu:

Semula, xrange adalah objek yang tidak cukup berurutan. Sebagai dokumen 3.1 mengatakan:

Jarak objek memiliki perilaku yang sangat sedikit: mereka hanya mendukung pengindeksan, iterasi, dan len fungsi.

Ini tidak sepenuhnya benar; sebuah xrange objek sebenarnya mendukung beberapa hal lain yang datang secara otomatis dengan pengindeksan dan len,* termasuk __contains__ (melalui pencarian linear). Tapi tidak ada yang berpikir itu layak membuat mereka urutan penuh pada saat itu.

Kemudian, sebagai bagian dari implementasi Kelas Basis Abstrak PEP, penting untuk mengetahui tipe bawaan apa yang harus ditandai sebagai penerapan ABC, dan xrange/range mengaku menerapkan collections.Sequence, meskipun itu masih hanya menangani "perilaku yang sangat kecil" yang sama. Tidak ada yang memperhatikan masalah itu sampai masalah 9213. Tambalan untuk masalah itu tidak hanya ditambahkan index dan count menjadi 3,2 range, itu juga kembali dioptimalkan __contains__ (yang berbagi matematika yang sama dengan index, dan langsung digunakan oleh count).**  Perubahan ini masuk untuk 3,2 juga, dan tidak kembali ke 2.x, karena "itu adalah perbaikan bug yang menambahkan metode baru". (Pada titik ini, 2,7 sudah melewati status rc.)

Jadi, ada dua peluang untuk mendapatkan pengoptimalan ini menjadi 2,7, tetapi keduanya ditolak.


* Bahkan, Anda bahkan mendapatkan iterasi secara gratis len dan pengindeksan, tapi di 2.3  xrange objek mendapat iterator khusus. Yang kemudian hilang di 3.x, yang menggunakan yang sama listiterator ketik sebagai list.

** Versi pertama benar-benar menerapkannya kembali, dan mendapatkan detail yang salah - misalnya, itu akan memberi Anda MyIntSubclass(2) in range(5) == False. Tapi versi update Daniel Stutzbach dari patch memulihkan sebagian besar kode sebelumnya, termasuk fallback ke generic, slow _PySequence_IterSearch yang pra-3.2 range.__contains__ secara implisit menggunakan ketika optimasi tidak berlaku.


79
2018-05-06 21:42



Jawaban lainnya menjelaskannya dengan baik, tetapi saya ingin menawarkan eksperimen lain yang menggambarkan sifat objek jangkauan:

>>> r = range(5)
>>> for i in r:
        print(i, 2 in r, list(r))

0 True [0, 1, 2, 3, 4]
1 True [0, 1, 2, 3, 4]
2 True [0, 1, 2, 3, 4]
3 True [0, 1, 2, 3, 4]
4 True [0, 1, 2, 3, 4]

Seperti yang Anda lihat, objek jangkauan adalah objek yang mengingat jangkauannya dan dapat digunakan berkali-kali (bahkan ketika iterasi di atasnya), bukan hanya generator satu kali.


35
2018-05-06 16:04



Ini semua tentang pendekatan malas untuk evaluasi, dan beberapa tambahan optimalisasi range. Nilai dalam rentang tidak perlu dihitung hingga penggunaan nyata, atau bahkan lebih jauh karena optimalisasi ekstra.

By the way integer Anda tidak begitu besar, pertimbangkan sys.maxsize

sys.maxsize in range(sys.maxsize)  cukup cepat

karena pengoptimalan - sangat mudah untuk membandingkan bilangan bulat yang diberikan hanya dengan min dan jangkauan maksimum.

tapi:

float(sys.maxsize) in range(sys.maxsize)  sangat lambat.

(dalam hal ini tidak ada pengoptimalan di range, jadi karena menerima float yang tak terduga, python akan membandingkan semua angka)


3
2018-03-16 10:47