Kodėl „10000000000000 diapazone (1000000000000001)“ taip greitai „Python 3“?

Suprantu, kad range() funkcija, kuri iš tikrųjų yra objekto tipas Python 3 , generuoja jo turinį skraidant, kaip generatorius.

Šiuo atveju tikiuosi, kad kita eilutė užims pernelyg ilgą laiką, nes norint nustatyti, ar diapazone bus 1 kvadriljonas, turite sukurti kvadratines reikšmes:

 1000000000000000 in range(1000000000000001) 

Be to, atrodo, kad nesvarbu, kiek nulio aš pridėjau, skaičiavimas daugiau ar mažiau užima tą patį laiką (dažniausiai momentinį).

Aš taip pat bandžiau tokius dalykus, tačiau skaičiavimas vis dar yra beveik akimirksniu:

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

Jei bandau įgyvendinti savo diapazono funkciją, rezultatas nėra toks geras!

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

Kas sukuria range() objektą po gaubtu, kuris daro jį taip greitai?


Martijno Pieterso atsakymas buvo pasirinktas dėl jo išsamumo, tačiau taip pat matyti atsakymą į pirmąjį atsakymą už gerą diskusiją apie tai, kas reiškia visą seką „Python 3“, ir tam tikrą informaciją / įspėjimą apie galimus neatitikimus optimizuoti __contains__ funkcijas „Python“ __contains__ . kitas atsakymas išsamiau aptariamas ir jame yra nuorodų tiems, kurie domisi Python 3 optimizavimo istorija (ir „ xrange optimizavimo trūkumu „Python 2“), „ xrange atsakymai ir „ xrange naudojimas suteikia tinkamą C šaltinio kodą ir paaiškinimus tiems, kurie domisi.

1541
06 мая '15 в 18:32 2015-05-06 18:32 Rick Teachey paklausė 06 gegužės 15 d. 18:32 2015-05-06 18:32
@ 9 atsakymai

Python 3 range() objektas iš karto nesukuria numerių; tai protingas sekos objektas, kuris pagal poreikį gamina skaičius. Viskas, kas joje yra, yra jūsų pradžios, sustabdymo ir žingsnių reikšmės, o tada, kai perkeliate per objektą, apskaičiuojama kiekvienos iteracijos kita sveikojo skaičiaus reikšmė.

Objektas taip pat įgyvendina object.__contains__ kablys, ir apskaičiuoja, ar jūsų numeris yra jo diapazono dalis. Skaičiavimas yra pastovaus laiko operacija O (1). Nereikia tikrinti visų galimų sveikų skaičių skaičiaus.

Į range() dokumentaciją:

range tipo pranašumas, palyginti su įprastu list ar tuple yra tas, kad diapazono objektas visada priims tą patį (mažą) atminties kiekį, neatsižvelgiant į diapazono, kurį jis vaizduoja, dydį (nes jis tik išsaugo start , stop ir step reikšmes, apskaičiuoja atskirus elementus ir subrangai, jei reikia).

Taigi bent jau jūsų range() objektas:

 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 

Vis dar yra keletas dalykų, kurių range() palaiko (pvz., .index() arba .count() metodus, maišymą, lygybės tikrinimą arba pjaustymą), bet turėtų suteikti jums idėją.

Taip pat supaprastinau __contains__ įgyvendinimą, kad __contains__ dėmesį tik į visus testus; jei suteikiate realaus range() objektą ne sveikasis skaičius (įskaitant int poklasius), paleidžiamas lėtas nuskaitymas, kad pamatytumėte, ar yra atitikimas, lyg būtumėte, jei naudojote ribojimo testą su visų turimų reikšmių sąrašu. Tai buvo padaryta siekiant toliau remti kitus skaitmeninius tipus, kurie, kaip paaiškėjo, palaikė lygybės bandymus su sveikaisiais skaičiais, tačiau nesitikėjo, kad bus palaikomas sveikasis skaičius. Žr. Pradinė „ Python“ problema , kuri įgyvendino izoliavimo bandymą.

1539 m
06 мая '15 в 18:33 2015-05-06 18:33 Atsakymą pateikė Martijn Pieters gegužės 06 d. 15, 18:33 2015-05-06 18:33

Pagrindinis nesusipratimas yra tas, kad range yra generatorius. Ne tai. Tiesą sakant, tai nėra tam tikras iteratorius.

Tai gana lengvai galite pasakyti:

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

Jei tai būtų generatorius, kartą kartojant jį būtų išnaudota:

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

Tiesą sakant, range yra seka, kaip ir sąrašas. Jūs netgi galite jį patikrinti:

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

Tai reiškia, kad jis privalo laikytis visų sekos taisyklių:

 >>> 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 
border=0

Skirtumas tarp range ir list yra tas, kad range yra tingus arba dinamiška seka; jis neprisimena visų savo vertybių, jis tiesiog prisimena savo start , stop ir step ir sukuria vertes pagal užklausą __getitem__ .

(Atkreipkite dėmesį, kad jei print(iter(a)) , pastebėsite, kad range naudoja tą patį listiterator tipą kaip list . Kaip jis veikia? listiterator nenaudoja nieko ypatingo list išskyrus tai, kad jis suteikia C __getitem__ todėl jis puikiai tinka range .)


Dabar nėra nieko, kas Sequence.__contains__ manyti, kad Sequence.__contains__ turėtų būti pastovus laikas - iš tikrųjų, jei yra akivaizdžių sekų, pvz., list , pavyzdžių, tai nėra taip. Tačiau nėra nieko, kas pasakytų, kad tai negali būti. Taip pat lengviau įgyvendinti range.__contains__ kad tiesiog matematiniu būdu patikrintumėte ( (val - start) % step , bet su tam tikru papildomu sudėtingumu, kad susidorotumėte su neigiamais žingsniais), nei iš tikrųjų generuoja ir išbando visas vertes, todėl kodėl gi ne geriau

Bet niekas, atrodo, neįvyksta kalba, užtikrindama, kad tai atsitiks. Kaip nurodo Ashwini Chaudhary, jei jūs suteikiate jam ne sveikasis skaičius, o ne konvertuoti jį į sveikąjį skaičių ir atliksite matematinį testą, jis sugrįš prie visų vertybių kartojimo ir jų palyginimo po vieną. Ir tik todėl, kad CPython versija 3.2+ ir PyPy 3.x yra šios optimizacijos, ir tai yra akivaizdi gera idėja ir lengva padaryti, nėra jokios priežasties, kodėl IronPython arba NewKickAssPython 3.x negalėtų tai atmesti. (Ir iš tiesų, CPython 3.0-3.1 neįsijungė.)


Jei range tikrųjų buvo generatorius, pvz., my_crappy_range , tai būtų beprasmiška tokiu būdu patikrinti __contains__ arba bent jau prasminga, tai nebūtų akivaizdu. Jei jau pakartojote pirmas 3 reikšmes, ar tai dar 1 generatorius? Jei bandymas atliekamas 1 , jis kartojasi ir suvartoja visas reikšmes iki 1 (arba iki pirmosios vertės >= 1 )?

631
06 мая '15 в 19:01 2015-05-06 19:01 atsakymas į abarnertą 06.05.15 val. 19:01 2015-05-06 19:01

Naudokite šaltinį , Luke!

CPython, range(...).__contains__ (metodas apvyniojimas) galiausiai perduoda paprastą skaičiavimą, kuris patikrina, ar vertė gali būti intervale. Greičio priežastis yra matematinių argumentų naudojimas apie ribas, o ne tiesioginis diapazono objekto iteravimas . Paaiškinti naudojamą logiką:

  • Įsitikinkite, kad numeris yra tarp start ir stop , ir
  • Įsitikinkite, kad žingsnio vertė „neperžengia“ mūsų numerio.

Pavyzdžiui, 994 yra range(4, 1000, 2) , nes:

  • 4 <= 994 < 1000 ir
  • (994 - 4) % 2 == 0 .

Visas C kodas rodomas žemiau, kuris yra šiek tiek išsamesnis dėl atminties valdymo ir atskaitos skaičiavimo detalių, tačiau pagrindinė idėja:

eilutėje : 

  

Kaip paskutinę pastabą, pažiūrėkite į „ range_contains funkciją kodo fragmento apačioje. Jei nėra atliekamas tikslus tipo patikrinimas, nenaudojame aprašyto protingo algoritmo, o mes grįžtame prie tylios paieškos diapazono iteracijai naudojant _PySequence_IterSearch ! Šį elgesį galite patikrinti vertėjas (čia naudoju v3.5.0):

 >>> 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) 
307
06 мая '15 в 18:41 2015-05-06 18:41 Atsakymas pateikiamas gegužės 06 d. 15 val. 18:41 2015-05-06 18:41

Norėdami pridėti atsakymą į „Martijns“, tai yra svarbi šaltinio dalis (C, nes diapazono objektas yra parašytas gimtąja kodu):

115
06 мая '15 в 18:41 2015-05-06 18:41 atsakymas duotas 06 gegužės 15 d. 18:41 2015-05-06 18:41

Jei įdomu, kodėl šis optimizavimas buvo įtrauktas į range.__contains__ ir kodėl ji nebuvo pridėta prie xrange.__contains__ 2.7 versijoje:

Pirma, kaip Ashwini Chaudhary atrado, klausimas 1766304 buvo atviras optimizavimui [x]range.__contains__ yra__ . Šio pleistras buvo patvirtintas ir išbandytas 3,2 , tačiau nebuvo skirtas 2.7, nes „Xrange taip ilgai elgėsi taip, kad nematau, kad pastaruoju metu mes perkame mus.“ (2.7 beveik nebuvo šiuo metu.)

Temos:

Iš pradžių xrange buvo ne sekos objektas. Kaip 3.1 dokumentai sako:

Diapazono objektai turi labai mažą elgesį: jie palaiko tik indeksavimą, iteraciją ir len funkciją.

Tai nebuvo visiškai teisinga; „ xrange objektas faktiškai palaikė keletą kitų dalykų, kurie automatiškai rodomi su indeksavimu ir „ len *, įskaitant __contains__ (per linijinę paiešką). Bet niekas nemanė, kad tuo metu verta juos užbaigti.

Tada, įgyvendinant abstrakčias PEP bazines klases , svarbu išsiaiškinti, kurie įmontuoti tipai turėtų būti pažymėti kaip ABC diegimas, o xrange / range nurodė, kad ji vykdo collections.Sequence xrange , nors vis dar apdoroja tą patį „labai mažą elgesį“. Niekas nepastebėjo šios problemos iki 9213 išdavimo . Šios problemos pleistras ne tik pridėjo index ir count į 3,2 range , bet ir pakeitė optimizuotą __contains__ (kuris dalijasi ta pačia matematika su index ir tiesiogiai naudoja count ) ** Šis pakeitimas tęsėsi 3,2, ir nebuvo adresuotas 2.x, nes „šis pataisymas prideda naujų metodų“. (Šiuo metu 2.7 jau išlaikė rc statusą.)

Taigi buvo dvi galimybės optimizuoti šią problemą: 2.7, tačiau abi buvo atmestos.


* Tiesą sakant, jūs netgi galite gauti iteraciją nemokamai, naudodami „ len ir „ xrange , bet 2,3 xrange objektų, iš kurių gaunamas individualus iteratorius. Tada jie prarado 3.x, kuris naudoja tą patį list tipą kaip list .

** Pirmoji versija iš naujo ją apibrėžė ir neteisingai nurodė detales - pavyzdžiui, ji suteiks jums „ MyIntSubclass(2) in range(5) == False . Tačiau Danielis Stutzbachas atnaujino pataisos versiją, atkurė didžiąją dalį ankstesnio kodo, įskaitant bendrą, lėtą _PySequence_IterSearch , kuris prieš 3.2. _PySequence_IterSearch range.__contains__ netiesiogiai naudojamas, kai optimizavimas nebuvo taikomas.

87
07 мая '15 в 0:42 2015-05-07 00:42 atsakymas pateikiamas abarnert 07 gegužės 15 d. 0:42 2015-05-07 00:42

Kiti atsakymai jau buvo gerai paaiškinti, bet norėčiau pasiūlyti dar vieną eksperimentą, iliustruojantį diapazone esančių objektų pobūdį:

 >>> 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] 

Kaip matote, diapazono objektas yra objektas, kuris prisimena jos diapazoną ir gali būti naudojamas daug kartų (net ir per ją), o ne tik vienkartinis generatorius.

40
06 мая '15 в 19:04 2015-05-06 19:04 atsakė Stefan Pochmann 06.05.15 val. 19:04 2015-05-06 19:04

Viskas apie tingų požiūrį į kainodarą ir tam tikrą papildomą range optimizavimą. Vertės intervaluose neturėtų būti apskaičiuojamos prieš faktinį naudojimą ar net dėl ​​papildomo optimizavimo.

Beje, jūsų sveikasis skaičius nėra toks didelis, apsvarstykite sys.maxsize

sys.maxsize in range(sys.maxsize) gana greitai

optimizavimo dėka lengva palyginti tam tikrą sveiką skaičių su minimaliu ir maksimaliu diapazonu.

a

float(sys.maxsize) in range(sys.maxsize) veikia gana lėtai.

(šiuo atveju range nėra optimizavimo, nes gavęs netikėtą plūdurą, bus lyginami visi numeriai)

11
16 марта '18 в 13:47 2018-03-16 13:47 Atsakymą Sławomiras Lenartas pateikia kovo 18 d. 18 val. 13:47 2018-03-16 13:47

Čia yra panašus įgyvendinimas C# . Jūs galite pamatyti, kaip Contains O (1) laiko.

 public struct Range : IRange, IEnumerable<int>, IEquatable<Range> { private readonly int _start; private readonly int _stop; private readonly int _step; //other methods/properties omitted public bool Contains(int number) { // precheck: if the number isnt in valid point, return false // for example, if start is 5 and step is 10, then its impossible that 163 be in range at any interval if ((_start % _step + _step) % _step != (number % _step + _step) % _step) return false; // vector represents direction: 1 means positive step, -1 means negative step // this value makes final checking formula straightforward. int vector = Math.Abs(_step) / _step; // so, no need to write if/else to handle both cases: negative and positive step return vector * number >= vector * _start  vector * number < vector * _stop; } } 
4
14 дек. Atsakymą pateikė Sanan Fataliyev gruodžio 14 d. 2018-12-14 11:19 '18, 11:19

Tl; DR

Objektas, grąžintas pagal range() iš tikrųjų yra range objektas. Šis objektas įgyvendina iteratoriaus sąsają, todėl galite paversti savo vertybes, kaip generatorius, tačiau jis taip pat įgyvendina __contains__ sąsają, kuri faktiškai vadinama, kai objektas pasirodo operatoriaus dešinėje. __contains__() metodas grąžina loginę vertę, ar elementas yra objekte. Kadangi range objektai žino jų ribas ir aukštį, tai labai lengva įdiegti O (1).

0
15 янв. atsakymas pateikiamas RBF06 15 sausio. 2019-01-15 19:56 '19, 19:56 pm

Kiti klausimai apie žymių arba „ Ask a question“