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 range
menjadi 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 xrange
di Python 2). Jawaban oleh poke dan oleh wim memberikan kode sumber C yang relevan dan penjelasan untuk mereka yang tertarik.
sumber
bool
ataulong
tipe, dengan tipe objek lain akan menjadi gila. Coba dengan:100000000000000.0 in range(1000000000000001)
range
generator?xrange
sama dengan Python3range
?xrange()
objek tidak memiliki__contains__
metode, sehingga pemeriksaan item harus mengulang semua item. Plus ada beberapa perubahan lain dirange()
dalamnya, seperti mendukung slicing (yang lagi-lagi mengembalikanrange
objek) dan sekarang juga memilikicount
danindex
metode untuk membuatnya kompatibel dengancollections.Sequence
ABC.Jawaban:
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 :Jadi minimal,
range()
objek Anda akan melakukan: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 memberikanrange()
objek nyata nilai non-integer (termasuk subclass dariint
), 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.
sumber
__getitem__
dan__len__
,__iter__
implementasi sebenarnya tidak perlu.xrangeiterator
ditambahkan 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 menggunakanlistiterator
tipe yang sama yanglist
menggunakan.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.range
lebih tua dari*args
(apalagiargclinic
API yang memungkinkan fungsi C-API memiliki tanda tangan Python lengkap). Beberapa fungsi lama lainnya (dan beberapa fungsi yang lebih baru, sepertixrange
,,slice
danitertools.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 menggambarkanrange
dan berteman seolah-olah mereka kelebihan gaya C ++ daripada menunjukkan tanda tangan yang sebenarnya membingungkan.argclinic
diskusi, ketika Nick Coghlan datang dengan cara untuk memungkinkan mendefinisikanrange
secara jelas: "Tolong jangan membuat lebih mudah bagi orang untuk menyalin keputusan desain terburuk saya." Jadi, saya cukup yakin dia setuju bahwarange
ini membingungkan seperti yang tertulis.Kesalahpahaman mendasar di sini adalah dalam berpikir bahwa itu
range
adalah generator. Ini bukan. Sebenarnya, itu bukan jenis iterator.Anda dapat mengatakan ini dengan mudah:
Jika itu generator, iterasi sekali akan menghabiskannya:
Apa yang
range
sebenarnya adalah urutan, seperti daftar. Anda bahkan dapat menguji ini:Ini berarti harus mengikuti semua aturan menjadi urutan:
Perbedaan antara a
range
dan alist
adalah bahwa arange
adalah urutan yang malas atau dinamis ; tidak ingat semua nilai-nilai, hanya ingat nyastart
,stop
, danstep
, dan menciptakan nilai-nilai pada permintaan pada__getitem__
.(Sebagai catatan tambahan, jika Anda
print(iter(a))
, Anda akan melihat bahwarange
menggunakanlistiterator
jenis yang sama denganlist
. Bagaimana cara kerjanya? Alistiterator
tidak menggunakan sesuatu yang khususlist
kecuali untuk fakta bahwa ia menyediakan implementasi C__getitem__
, sehingga berfungsi dengan baik untukrange
terlalu.)Sekarang, tidak ada yang mengatakan bahwa
Sequence.__contains__
itu harus waktu yang konstan — pada kenyataannya, untuk contoh yang jelas dari urutan sepertilist
, tidak. Tapi tidak ada yang mengatakan itu tidak mungkin. Dan lebih mudah diimplementasikanrange.__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
range
benar-benar generator,my_crappy_range
maka 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, apakah1
masihin
generator? Haruskah pengujian untuk1
penyebab iterate dan mengkonsumsi semua nilai hingga1
(atau hingga nilai pertama>= 1
)?sumber
range
terdaftar (bersama denganlist
dantuple
) sebagai jenis urutan .xrange
adalah urutan juga. Lihat 2,7 dokumen . Bahkan, itu hampir selalu berurutan..__iter__()
metode yang akan mengembalikan iterator. Pada gilirannya hanya dapat digunakan sekali.range
tidak memeriksa jenis ketika itu bukan bilangan bulat, karena selalu mungkin jenis memiliki__eq__
yang kompatibel dengannyaint
. Tentu,str
jelas tidak akan berfungsi, tetapi mereka tidak ingin memperlambat semuanya dengan secara eksplisit memeriksa semua jenis yang tidak bisa ada di sana (dan setelah semua,str
subkelas bisa menimpa__eq__
dan terkandung dalamrange
).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:start
danstop
, danMisalnya,
994
ada dirange(4, 1000, 2)
karena:4 <= 994 < 1000
, dan(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:
"Daging" dari gagasan tersebut disebutkan dalam baris :
Sebagai catatan akhir - lihat
range_contains
fungsi 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):sumber
Untuk menambah jawaban Martijn, ini adalah bagian yang relevan dari sumber (dalam C, karena objek rentang ditulis dalam kode asli):
Jadi untuk
PyLong
objek (yang adaint
di Python 3), ia akan menggunakanrange_contains_long
fungsi untuk menentukan hasilnya. Dan fungsi itu pada dasarnya memeriksa apakahob
berada dalam kisaran yang ditentukan (meskipun terlihat sedikit lebih kompleks di C).Jika bukan
int
objek, ia kembali ke iterasi hingga menemukan nilai (atau tidak).Seluruh logika dapat diterjemahkan ke pseudo-Python seperti ini:
sumber
Jika Anda bertanya-tanya mengapa optimasi ini ditambahkan ke
range.__contains__
, dan mengapa itu tidak ditambahkan kexrange.__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,
xrange
adalah objek yang tidak cukup urutan. Seperti yang dikatakan dalam dokumen 3.1 :Ini tidak sepenuhnya benar; sebuah
xrange
objek sebenarnya mendukung beberapa hal lain yang datang secara otomatis dengan pengindeksan danlen
, * 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
/range
diklaim untuk diterapkancollections.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 ditambahkanindex
dancount
kerange
versi 3.2's , itu juga bekerja kembali dioptimalkan__contains__
(yang berbagi matematika yang samaindex
, dan langsung digunakan olehcount
). ** 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_IterSearch
yang pre-3.2range.__contains__
secara implisit digunakan ketika optimasi tidak berlaku.sumber
xrange.__contains__
, sepertinya mereka tidak mendukungnya ke Python 2 hanya untuk meninggalkan elemen kejutan bagi pengguna dan sudah terlambat o_O. Thecount
danindex
Patch ditambahkan di kemudian hari. File pada waktu itu: hg.python.org/cpython/file/d599a3f2e72d/Objects/rangeobject.c2to3
bukan melalui kode dua versi dengan bantuan perpustakaan sepertisix
, itulah sebabnya kami mendapat hal-hal sepertidict.viewkeys
yang 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.Jawaban lain sudah menjelaskannya dengan baik, tetapi saya ingin menawarkan eksperimen lain yang menggambarkan sifat berbagai objek:
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.
sumber
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 cepatkarena 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.
sumber
float(sys.maxsize) != sys.maxsize)
meskipunsys.maxsize-float(sys.maxsize) == 0
.TL; DR
Objek yang dikembalikan
range()
sebenarnya adalahrange
objek. 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 kananin
operator. The__contains__()
kembali metode yangbool
dari apakah atau tidak item di kiri-sisi yangin
ada di objek. Karenarange
objek tahu batas dan langkahnya, ini sangat mudah diimplementasikan dalam O (1).sumber
Ambil contoh, 997 berada dalam kisaran (4, 1000, 3) karena:
4 <= 997 < 1000, and (997 - 4) % 3 == 0.
sumber
Coba
x-1 in (i for i in range(x))
untukx
nilai besar , yang menggunakan pemahaman generator untuk menghindari penerapanrange.__contains__
optimasi.sumber