Anladığım kadarıyla, aslında Python 3'te bir nesne türü olan range()
işlevi, bir üretece benzer şekilde içeriğini anında üretiyor.
Bu durumda, aşağıdaki satırın aşırı miktarda zaman almasını beklerdim, çünkü 1 katrilyonun aralıkta olup olmadığını belirlemek için bir katrilyon değer üretilmesi gerekirdi:
1000000000000000 in range(1000000000000001)
Ayrıca: ne kadar sıfır eklersem ekleyeyim, hesaplama aşağı yukarı aynı süreyi alıyor gibi görünüyor (temelde anlık).
Bunun gibi şeyler de denedim, ancak hesaplama hala neredeyse anlık:
1000000000000000000000 in range(0,1000000000000000000001,10) # count by tens
Kendi aralık işlevimi uygulamaya çalışırsam, sonuç o kadar da güzel olmuyor!
def my_crappy_range(N):
i = 0
while i < N:
yield i
i += 1
return
range()` nesnesi kaputun altında ne yapıyor da bu kadar hızlı çalışıyor?
Martijn Pieters' cevabı eksiksiz olduğu için seçildi, ancak aynı zamanda Python 3'te aralığın' tam teşekküllü bir *dizi* olmasının ne anlama geldiğine dair iyi bir tartışma ve Python uygulamaları arasında
contains' işlev optimizasyonu için potansiyel tutarsızlık hakkında bazı bilgiler/uyarılar için abarnert'in ilk cevabına bakın. abarnert'in diğer cevabı biraz daha ayrıntıya giriyor ve Python 3'teki optimizasyonun (ve Python 2'deki xrange
optimizasyonunun eksikliği) arkasındaki geçmişle ilgilenenler için bağlantılar sağlıyor. poke]5 ve wim tarafından verilen yanıtlar, ilgilenenler için ilgili C kaynak kodunu ve açıklamaları sağlar.
Python 3 range()
nesnesi hemen sayı üretmez; talep üzerine sayı üreten akıllı bir dizi nesnesidir. İçerdiği tek şey başlangıç, bitiş ve adım değerlerinizdir, daha sonra nesne üzerinde yineleme yaptıkça her yinelemede bir sonraki tamsayı hesaplanır.
Nesne ayrıca object.__contains__
kancasını uygular ve sayınızın aralığının bir parçası olup olmadığını hesaplar. Hesaplama O(1) sabit zamanlı bir işlemdir. Aralıktaki tüm olası tamsayıları taramaya asla gerek yoktur.
range()` nesne belgelerinden](https://docs.python.org/3/library/stdtypes.html#range):
gt; range
türünün normal bir list
veya tuple
türüne göre avantajı, bir range nesnesinin temsil ettiği aralığın boyutu ne olursa olsun her zaman aynı (küçük) miktarda bellek kullanmasıdır (yalnızca start
, stop
ve step
değerlerini sakladığından, gerektiğinde tek tek öğeleri ve alt aralıkları hesaplar).
Yani en azından range()
nesneniz işinizi görecektir:
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
Bu, gerçek bir range()
in desteklediği bazı şeyleri (örneğin .index()
veya .count()
yöntemleri, hashing, eşitlik testi veya dilimleme) hala eksiktir, ancak size bir fikir vermelidir.
Ayrıca __contains__
uygulamasını sadece tamsayı testlerine odaklanacak şekilde basitleştirdim; gerçek bir range()
nesnesine tamsayı olmayan bir değer verirseniz (int
alt sınıfları dahil), bir eşleşme olup olmadığını görmek için yavaş bir tarama başlatılır, tıpkı içerilen tüm değerlerin bir listesine karşı bir içerme testi kullandığınızda olduğu gibi. Bu, tamsayılarla eşitlik testini destekleyen ancak tamsayı aritmetiğini de desteklemesi beklenmeyen diğer sayısal türleri desteklemeye devam etmek için yapılmıştır. Kapsama testini uygulayan orijinal Python sorunu'a bakın.
Kaynak]1'i kullan, Luke!
CPython'da, range(...).__contains__
(bir yöntem sarmalayıcı) sonunda değerin aralıkta olup olamayacağını kontrol eden basit bir hesaplamaya delege olacaktır. Buradaki hızın nedeni, aralık nesnesinin doğrudan yinelenmesi yerine, sınırlar hakkında matematiksel akıl yürütme kullanmamızdır. Kullanılan mantığı açıklamak için:
start
ile stop
arasında olup olmadığını kontrol edin veÖrneğin, 994
aralık(4, 1000, 2)
içindedir çünkü:
4 <= 994 < 1000
, ve(994 - 4) % 2 == 0
.Bellek yönetimi ve referans sayma ayrıntıları nedeniyle biraz daha ayrıntılı olan tam C kodu aşağıda yer almaktadır, ancak temel fikir oradadır:
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);
}
Fikrin "et" kısmından satır'de bahsedilmektedir:
/* result = ((int(ob) - start) % step) == 0 */
Son bir not olarak - kod parçasının altındaki range_contains
fonksiyonuna bakın. Tam tip kontrolü başarısız olursa, açıklanan akıllı algoritmayı kullanmayız, bunun yerine _PySequence_IterSearch
kullanarak aralığın aptal bir yineleme aramasına geri döneriz! Bu davranışı yorumlayıcıda kontrol edebilirsiniz (ben burada v3.5.0 kullanıyorum):
>>> 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)
Martijn'in cevabına ek olarak, bu kaynak'ın ilgili kısmıdır (aralık nesnesi yerel kodla yazıldığı için C dilinde):
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);
}
Yani PyLong
nesneleri için (Python 3'te int
olan), sonucu belirlemek için range_contains_long
fonksiyonunu kullanacaktır. Ve bu fonksiyon temel olarak ob
nin belirtilen aralıkta olup olmadığını kontrol eder (C'de biraz daha karmaşık görünmesine rağmen).
Eğer bir int
nesnesi değilse, değeri bulana (ya da bulamayana) kadar yinelemeye devam eder.
Tüm mantık şu şekilde sözde Python'a çevrilebilir:
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