Mengapa "1000000000000000 dalam jangkauan (100000000000000001)" begitu cepat di Python 3?

2116

Ini adalah pemahaman saya bahwa range()fungsi, yang sebenarnya merupakan tipe objek di Python 3 , menghasilkan kontennya dengan cepat, mirip dengan generator.

Karena itu, saya akan mengharapkan baris berikut untuk mengambil jumlah waktu banyak, karena untuk menentukan apakah 1 kuadriliun berada dalam kisaran, nilai kuadriliun harus dihasilkan:

1000000000000000 in range(1000000000000001)

Lebih lanjut: tampaknya tidak peduli berapa banyak angka nol yang saya tambahkan, perhitungannya kurang lebih sama dengan waktu (pada dasarnya instan).

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

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

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

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

Apa yang range()dilakukan objek di bawah kap yang membuatnya begitu cepat?


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

Rick mendukung Monica
sumber
70
Perhatikan bahwa ini hanya terjadi jika item yang kami periksa adalah a boolatau longtipe, dengan tipe objek lain akan menjadi gila. Coba dengan:100000000000000.0 in range(1000000000000001)
Ashwini Chaudhary
10
Siapa yang bilang itu rangegenerator?
abarnert
7
@abarnert Saya pikir suntingan yang saya buat membuat kebingungan tetap utuh.
Rick mendukung Monica
5
@AshwiniChaudhary bukankah Python2 xrangesama dengan Python3range ?
Biasa
28
@Superbest xrange()objek tidak memiliki __contains__metode, sehingga pemeriksaan item harus mengulang semua item. Plus ada beberapa perubahan lain di range()dalamnya, seperti mendukung slicing (yang lagi-lagi mengembalikan rangeobjek) dan sekarang juga memiliki countdan indexmetode untuk membuatnya kompatibel dengan collections.SequenceABC.
Ashwini Chaudhary

Jawaban:

2171

range()Objek Python 3 tidak menghasilkan angka dengan segera; itu adalah objek urutan pintar yang menghasilkan angka sesuai permintaan . Semua yang dikandungnya adalah nilai awal, berhenti, dan langkah Anda, lalu saat Anda mengulangi objek, bilangan bulat berikutnya dihitung setiap iterasi.

Objek juga mengimplementasikan object.__contains__pengait , dan menghitung jika nomor Anda adalah bagian dari jangkauannya. Menghitung adalah operasi waktu konstan (dekat) * . Tidak pernah ada kebutuhan untuk memindai melalui semua bilangan bulat yang mungkin dalam jangkauan.

Dari range()dokumentasi objek :

Keuntungan dari rangetipe melebihi reguler listatau tupleadalah bahwa objek rentang akan selalu mengambil jumlah memori yang sama (kecil), tidak peduli ukuran rentang yang diwakilinya (karena hanya menyimpan start, stopdan stepnilai, menghitung item individual dan subranges sesuai kebutuhan).

Jadi minimal, range()objek Anda 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, step = stop, start, -step
        else:
            lo, hi = start, stop
        self.length = 0 if lo > hi else ((hi - lo - 1) // 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 melewatkan beberapa hal yang range()didukung nyata (seperti metode .index()atau .count(), hashing, pengujian kesetaraan, atau pemotongan), tetapi harus memberi Anda ide.

Saya juga menyederhanakan __contains__implementasi untuk hanya fokus pada tes integer; jika Anda memberikan range()objek nyata 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. Hal ini dilakukan untuk terus mendukung tipe numerik lainnya yang kebetulan mendukung pengujian kesetaraan dengan bilangan bulat tetapi tidak diharapkan untuk mendukung aritmatika bilangan bulat juga. Lihat masalah Python asli yang menerapkan uji penahanan.


* Waktu dekat konstan karena bilangan bulat Python tidak terikat dan operasi matematika juga tumbuh dalam waktu ketika N tumbuh, menjadikan ini operasi O (log N). Karena semuanya dijalankan dalam kode C yang dioptimalkan dan Python menyimpan nilai integer dalam potongan 30-bit, Anda akan kehabisan memori sebelum Anda melihat dampak kinerja apa pun karena ukuran bilangan bulat yang terlibat di sini.

Martijn Pieters
sumber
58
Fakta menyenangkan: karena Anda memiliki implementasi yang berhasil __getitem__dan __len__, __iter__implementasi sebenarnya tidak perlu.
Lucretiel
2
@ Lucretiel: Dalam Python 2.3 , khusus xrangeiteratorditambahkan khusus karena itu tidak cukup cepat. Dan kemudian di suatu tempat di 3.x (saya tidak yakin apakah itu 3.0 atau 3.2) itu dilempar dan mereka menggunakan listiteratortipe yang sama yang listmenggunakan.
abarnert
1
Saya akan mendefinisikan konstruktor sebagai def __init__(self, *start_stop_step)dan menguraikannya dari sana; cara argumen diberi label sekarang agak membingungkan. Namun demikian, +1; Anda masih jelas menjelaskan perilakunya.
Cody Piersall
1
@CodyPiersall: Sayangnya, itulah tanda tangan dari inisialisasi kelas nyata. rangelebih tua dari *args(apalagi argclinicAPI yang memungkinkan fungsi C-API memiliki tanda tangan Python lengkap). Beberapa fungsi lama lainnya (dan beberapa fungsi yang lebih baru, seperti xrange,, slicedan itertools.islice, untuk konsistensi) bekerja dengan cara yang sama, tetapi untuk sebagian besar, Guido dan sisa pengembang inti tampaknya setuju dengan Anda. 2.0+ dokumen bahkan menggambarkan rangedan berteman seolah-olah mereka kelebihan gaya C ++ daripada menunjukkan tanda tangan yang sebenarnya membingungkan.
abarnert
2
@CodyPiersall: Sebenarnya, inilah kutipan dari Guido argclinicdiskusi, ketika Nick Coghlan datang dengan cara untuk memungkinkan mendefinisikan rangesecara jelas: "Tolong jangan membuat lebih mudah bagi orang untuk menyalin keputusan desain terburuk saya." Jadi, saya cukup yakin dia setuju bahwa rangeini membingungkan seperti yang tertulis.
abarnert
845

Kesalahpahaman mendasar di sini adalah dalam berpikir bahwa itu rangeadalah generator. Ini bukan. Sebenarnya, itu 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 itu generator, iterasi sekali akan menghabiskannya:

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

Apa yang rangesebenarnya 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 rangedan a listadalah bahwa a rangeadalah urutan yang malas atau dinamis ; tidak ingat semua nilai-nilai, hanya ingat nya start, stop, dan step, dan menciptakan nilai-nilai pada permintaan pada __getitem__.

(Sebagai catatan tambahan, jika Anda print(iter(a)), Anda akan melihat bahwa rangemenggunakan listiteratorjenis yang sama dengan list. Bagaimana cara kerjanya? A listiteratortidak menggunakan sesuatu yang khusus listkecuali untuk fakta bahwa ia menyediakan implementasi C __getitem__, sehingga berfungsi dengan baik untuk rangeterlalu.)


Sekarang, tidak ada yang mengatakan bahwa Sequence.__contains__itu harus waktu yang konstan — pada kenyataannya, untuk contoh yang jelas dari urutan seperti list, tidak. Tapi tidak ada yang mengatakan itu tidak mungkin. Dan lebih mudah diimplementasikan range.__contains__hanya dengan memeriksanya secara matematis ( (val - start) % step, tetapi dengan beberapa kompleksitas tambahan untuk menangani langkah-langkah negatif) daripada benar-benar menghasilkan dan menguji semua nilai, jadi mengapa tidak melakukannya dengan cara yang lebih baik?

Tapi sepertinya tidak ada apa pun dalam bahasa yang menjamin ini akan terjadi. Seperti yang ditunjukkan Ashwini Chaudhari, jika Anda memberikan nilai non-integral, alih-alih mengonversi bilangan bulat dan melakukan tes matematika, itu akan kembali ke pengulangan semua nilai dan membandingkannya satu per satu. Dan hanya karena versi CPython 3.2+ dan PyPy 3.x mengandung optimasi ini, dan ini merupakan ide yang bagus dan mudah dilakukan, tidak ada alasan bahwa IronPython atau NewKickAssPython 3.x tidak dapat mengabaikannya. (Dan sebenarnya CPython 3.0-3.1 tidak memasukkannya.)


Jika rangebenar-benar generator, my_crappy_rangemaka tidak masuk akal untuk menguji __contains__dengan cara ini, atau setidaknya cara yang masuk akal tidak akan terlihat jelas. Jika Anda sudah mengulangi 3 nilai pertama, apakah 1masih ingenerator? Haruskah pengujian untuk 1penyebab iterate dan mengkonsumsi semua nilai hingga 1(atau hingga nilai pertama >= 1)?

abarnert
sumber
10
Ini adalah hal yang cukup penting untuk diluruskan. Saya kira perbedaan antara Python 2 dan 3 mungkin telah menyebabkan kebingungan saya pada titik ini. Bagaimanapun, saya harus menyadari sejak rangeterdaftar (bersama dengan listdan tuple) sebagai jenis urutan .
Rick mendukung Monica
4
@ RickTeachey: Sebenarnya, dalam 2.6+ (saya pikir; mungkin 2.5+), xrangeadalah urutan juga. Lihat 2,7 dokumen . Bahkan, itu hampir selalu berurutan.
abarnert
5
@ RickTeachey: Sebenarnya, saya salah; di 2.6-2.7 (dan 3.0-3.1), ia mengklaim sebagai urutan, tapi itu masih hanya urutan-hampir. Lihat jawaban saya yang lain.
abarnert
2
Ini bukan iterator, ini adalah urutan (Iterable dalam hal Java, IEnumerable dari C #) - sesuatu dengan .__iter__()metode yang akan mengembalikan iterator. Pada gilirannya hanya dapat digunakan sekali.
Smit Johnth
4
@ThomasAhle: Karena rangetidak memeriksa jenis ketika itu bukan bilangan bulat, karena selalu mungkin jenis memiliki __eq__yang kompatibel dengannya int. Tentu, strjelas tidak akan berfungsi, tetapi mereka tidak ingin memperlambat semuanya dengan secara eksplisit memeriksa semua jenis yang tidak bisa ada di sana (dan setelah semua, strsubkelas bisa menimpa __eq__dan terkandung dalam range).
ShadowRanger
377

Gunakan sumbernya , Luke!

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

  1. Pastikan nomornya antara startdan stop, dan
  2. Pastikan nilai langkahnya tidak "melangkahi" nomor kami.

Misalnya, 994ada di range(4, 1000, 2)karena:

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

Kode C lengkap termasuk di bawah ini, yang sedikit lebih verbose 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 gagasan tersebut disebutkan dalam baris :

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

Sebagai catatan akhir - lihat range_containsfungsi di bagian bawah potongan kode. Jika pemeriksaan tipe yang tepat gagal maka kami tidak menggunakan algoritma pintar yang dijelaskan, sebaliknya kembali ke pencarian iterasi yang bodoh menggunakan rentang _PySequence_IterSearch! Anda dapat memeriksa perilaku ini dalam juru bahasa (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)
wim
sumber
144

Untuk menambah jawaban Martijn, ini adalah bagian yang relevan dari 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 PyLongobjek (yang ada intdi Python 3), ia akan menggunakan range_contains_longfungsi untuk menentukan hasilnya. Dan fungsi itu pada dasarnya memeriksa apakah obberada dalam kisaran yang ditentukan (meskipun terlihat sedikit lebih kompleks di C).

Jika bukan intobjek, ia kembali ke iterasi hingga menemukan nilai (atau tidak).

Seluruh logika dapat 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
menyodok
sumber
11
@ ChrisWesseling: Saya pikir ini adalah informasi yang cukup berbeda (dan cukup) bahwa mengedit jawaban Martijn tidak akan sesuai di sini. Ini panggilan penghakiman, tetapi orang biasanya melakukan kesalahan karena tidak melakukan perubahan drastis pada jawaban orang lain.
abarnert
105

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

Pertama, seperti yang ditemukan Ashwini Chaudhary, edisi 1766304 dibuka secara eksplisit untuk dioptimalkan [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 kami untuk melakukan patch selambat-lambatnya." (2,7 hampir keluar pada saat itu.)

Sementara itu:

Awalnya, xrangeadalah objek yang tidak cukup urutan. Seperti yang dikatakan dalam dokumen 3.1 :

Objek jangkauan memiliki perilaku yang sangat sedikit: mereka hanya mendukung pengindeksan, iterasi, dan lenfungsi.

Ini tidak sepenuhnya benar; sebuah xrangeobjek 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 untuk membuat urutan penuh pada saat itu.

Kemudian, sebagai bagian dari implementasi PEP Kelas Dasar Abstrak , penting untuk mengetahui tipe builtin mana yang harus ditandai sebagai penerapan ABC mana, dan xrange/ rangediklaim untuk diterapkan collections.Sequence, meskipun masih hanya menangani "perilaku sangat sedikit" yang sama. Tidak ada yang memperhatikan masalah itu sampai masalah 9213 . Tambalan untuk masalah itu tidak hanya ditambahkan indexdan countke rangeversi 3.2's , itu juga bekerja kembali dioptimalkan __contains__(yang berbagi matematika yang sama index, dan langsung digunakan oleh count). ** Perubahan ini berlaku untuk 3.2 juga, dan tidak di-backport ke 2.x, karena "ini adalah perbaikan bug yang menambahkan metode baru". (Pada titik ini, 2,7 sudah melewati status rc.)

Jadi, ada dua peluang untuk mendapatkan optimasi ini di-backport ke 2,7, tetapi keduanya ditolak.


* Bahkan, Anda bahkan mendapatkan iterasi secara gratis dengan pengindeksan saja, tetapi dalam 2,3 xrange objek mendapat iterator khusus.

** Versi pertama benar-benar mengimplementasikannya, dan mendapatkan rincian yang salah — misalnya, itu akan memberi Anda MyIntSubclass(2) in range(5) == False. Tetapi versi terbaru patch Daniel Stutzbach memulihkan sebagian besar kode sebelumnya, termasuk fallback ke generik, lambat _PySequence_IterSearchyang pre-3.2 range.__contains__secara implisit digunakan ketika optimasi tidak berlaku.

abarnert
sumber
4
Dari komentar di sini: tingkatkanxrange.__contains__ , sepertinya mereka tidak mendukungnya ke Python 2 hanya untuk meninggalkan elemen kejutan bagi pengguna dan sudah terlambat o_O. The countdan index Patch ditambahkan di kemudian hari. File pada waktu itu: hg.python.org/cpython/file/d599a3f2e72d/Objects/rangeobject.c
Ashwini Chaudhary
12
Saya memiliki kecurigaan yang menyeramkan bahwa beberapa devs python inti adalah sebagian dari "cinta yang kuat" untuk python 2.x karena mereka ingin mendorong orang untuk beralih ke python3 yang jauh lebih unggul :)
wim
4
Saya juga yakin itu adalah beban yang sangat besar untuk harus menambahkan fitur baru ke versi lama. Bayangkan jika Anda pergi ke Oracle dan berkata, "Lihat, saya di Jawa 1.4 dan saya pantas mendapatkan ungkapan lambda! Backport mereka tanpa biaya."
Rob Grant
2
@ RickTeachey ya itu hanya sebuah contoh. Jika saya mengatakan 1,7 itu masih akan berlaku. Ini perbedaan kuantitatif bukan kualitatif. Pada dasarnya para pengembang (yang belum dibayar) tidak selamanya dapat membuat barang baru yang keren di 3.x dan mendukungnya menjadi 2.x untuk mereka yang tidak ingin memperbarui. Ini beban yang sangat besar dan konyol. Apakah Anda pikir masih ada yang salah dengan alasan saya?
Rob Grant
3
@RickTeachey: 2.7 berada di antara 3.1 dan 3.2, bukan sekitar 3.3. Dan itu berarti 2,7 berada di rc ketika perubahan terakhir ke 3.2 masuk, yang membuat komentar bug lebih mudah dimengerti. Lagi pula, saya pikir mereka membuat beberapa kesalahan dalam retrospeksi (terutama dengan asumsi orang akan bermigrasi melalui 2to3bukan melalui kode dua versi dengan bantuan perpustakaan seperti six, itulah sebabnya kami mendapat hal-hal seperti dict.viewkeysyang tidak akan pernah digunakan oleh siapa pun), dan ada beberapa perubahan yang baru saja terlambat di 3.2, tetapi untuk sebagian besar 2.7 adalah rilis "2.x terakhir" yang cukup mengesankan.
abarnert
47

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

>>> 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 saat iterasi di atasnya), bukan hanya generator satu kali.

Stefan Pochmann
sumber
27

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

Omong-omong, bilangan bulat Anda tidak terlalu besar, pertimbangkan sys.maxsize

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

karena optimasi - mudah untuk membandingkan bilangan bulat yang diberikan hanya dengan rentang min dan maks.

tapi:

Decimal(sys.maxsize) in range(sys.maxsize) cukup lambat .

(dalam hal ini, tidak ada optimasi dalam range, jadi jika python menerima Desimal yang tak terduga, python akan membandingkan semua angka)

Anda harus mengetahui detail implementasi tetapi tidak boleh diandalkan, karena ini dapat berubah di masa depan.

Sławomir Lenart
sumber
4
Hati-hati mengambang bilangan bulat besar. Pada kebanyakan mesin, float(sys.maxsize) != sys.maxsize)meskipun sys.maxsize-float(sys.maxsize) == 0.
holdenweb
18

TL; DR

Objek yang dikembalikan range()sebenarnya adalah rangeobjek. Objek ini mengimplementasikan antarmuka iterator sehingga Anda dapat beralih pada nilainya secara berurutan, seperti generator, daftar, atau tupel.

Tetapi juga mengimplementasikan __contains__antarmuka yang sebenarnya dipanggil ketika sebuah objek muncul di sisi kanan inoperator. The __contains__()kembali metode yang booldari apakah atau tidak item di kiri-sisi yang inada di objek. Karena rangeobjek tahu batas dan langkahnya, ini sangat mudah diimplementasikan dalam O (1).

RBF06
sumber
0
  1. Karena optimasi, sangat mudah untuk membandingkan bilangan bulat yang diberikan hanya dengan kisaran min dan maks.
  2. Alasan bahwa fungsi range () begitu cepat di Python3 adalah bahwa di sini kita menggunakan penalaran matematis untuk batas, daripada pengulangan langsung objek jangkauan.
  3. Jadi untuk menjelaskan logika di sini:
    • Periksa apakah nomornya antara awal dan berhenti.
    • Periksa apakah nilai presisi langkah tidak melampaui angka kami.
  4. Ambil contoh, 997 berada dalam kisaran (4, 1000, 3) karena:

    4 <= 997 < 1000, and (997 - 4) % 3 == 0.

Naruto
sumber
1
Bisakah Anda berbagi sumber untuk itu? Bahkan jika itu kedengarannya sah, akan baik untuk mendukung klaim ini dengan kode aktual
Nico Haase
Saya pikir ini adalah contoh yang bisa diterapkan. Bukan cara yang tepat diterapkan. Meskipun tidak ada referensi yang disediakan itu adalah petunjuk yang cukup baik untuk memahami mengapa memeriksa inklusi untuk rentang dapat lebih cepat daripada daftar atau tuple
Mohammed Shareef C
0

Coba x-1 in (i for i in range(x))untuk xnilai besar , yang menggunakan pemahaman generator untuk menghindari penerapan range.__contains__optimasi.

benjimin
sumber