Un for dynamique

Lorsqu'on fait des boucles for on parcourt un ensemble de données qui peut être une liste, un dictionnaire ou n'importe quoi qui est itérable, comprendre qui offre une méthode pour parcourir l'ensemble de ses données.

Ceux qui ont connu Python 2 ont peut-être été surpris de découvrir que range(10) ne retourne pas la liste [0,1,2,3,4,5,6,7,8,9] :

print(range(10))
type(range(10))

range(0, 10)

range

range() retourne donc un range et non plus une liste. Pour avoir la liste il faut le convertir.

list(range(10))

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Le monde de l'optimisation

L'idée est qu'il n'est pas nécessaire de construire un ensemble de données avec toutes les données seulement pour une boucle, il suffit de donner à la boucle les éléments un par un que l'on construit à la volée.

Regardons cet exemple qui désire faire la somme des N premiers factoriels. On construit

• un générateur qui calculera les valeurs demandées à la volée : (factorial(i) for i in range(1000)) défini avec des parenthèses
• une liste qui calcule toutes les valeurs et les stocke en mémoire : [factorial(i) for i in range(1000)] définie avec des crochets

from math import factorial

gen = (factorial(i) for i in range(10000))
lis = [factorial(i) for i in range(10000)]

gen

<generator object <genexpr> at 0x7f14dd436b30>

Regardons le temps de construction du générateur et de la liste :

%timeit (factorial(i) for i in range(10000))

361 ns ± 12.9 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

%timeit [factorial(i) for i in range(10000)]

7.66 s ± 14.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Sans surprise on constate que le générateur est bien plus rapide (d'un facteur 25 millions sur ma machine) puisqu'il ne fait rien pour l'instant. Il calculera à la volée la valeur suivante lorsqu'on lui demandera.

De plus l'occupation mémoire est quasiment nulle pour le générateur.

import sys

print(sys.getsizeof(gen))
print(sys.getsizeof(lis))

112
87616

Donc victoire sans appel pour le générateur mais on se dit qu'on va le payer à l'exécution puisque le génerateur va devoir calculer ce que la liste a déjà en mémoire.

%time sum(gen)

CPU times: user 7.77 s, sys: 0 ns, total: 7.77 s
Wall time: 7.77 s

2846544363824575411974133954272619447111476638986894150012068192690648834822200375328623622649745580730890329122417061399092026367020912838755646170763908089934263209682209676395802305048393839091236470474746103428494533306061637172900505116511423331761625723616902965848646144551445843453846601043472140662768746876455627207172302258019849932982986172347202808699197500145264692178231587867662062549429711726296104245560244800328117790974954274775113117954784558630938125324273430112543205480861675651721627094367916546971289233044597490676922741513533077983261454279143861733997064136506468583014643578449887422109896384223975107657283065356625047353369121126710585754986841505084319859185693074595980106439823016770720114936030638192079242528151508509453651260413563942407746086542464468798628153168566253427058189953115669810936028069337688050383655751449626149958745333417122255040192992590152142618889918050674820940189690936512153268955306076044738454065677445507497956298031359601460367688123266887407344527837034309657698507862661999741532135891188296772291635681752303038172869531003223585402881390352766425619307435012467320183719687432594324680313288252624242375547112390108053017995207632836834150270789473466371686004337524599724740217981823616290088586476828101799644024744426478583726007888483264414554576305602530855056181263518809361459388852398362047950800131137495032222648513578141077248463979823869139860815403856130492247559755892995167553333224974779391126764697778076426829111376006060545847483757890898006274736768319058986311096687542618253624486468868725256035010229277952796635850928901479716426794120662258316292264250967727926004512503274777609080671425302740687757372996123918141094091193982621777991477755327127633302538305482538054051626059422151028115545481979087246407512893443284100119581177881959766159964495179499286146163903490422234385433657118291345894580636366781894966217065024421175587401876155198441396792500685769104016737183666833177485769214532968463249068944579900820399160086485553759152015879779185583488564365971795010517215769981674461364752853509589251752862536295732482411885635226343327653727873663671894405284455124011910658188814408622643501663319543292027524523922495560386863821765829130657380834313878766854120042276219799225342085380997669521124494851955656077827887030486351082366882208471287748817054316050107367560969009693282756370472732021261303106425078877265159573484298300310617225618494554270567290041105781150281831591592109244118532878725466135569732211174564485617093980109027839564785141458625886797987204861020824764731436681556386922671088897865299421217279461134563652990841385932187925461051951940996619068739335001584501274021170189440819037046767067662893632724766003004567705781930829019319143985210860581069812804196559369206300181574397330972510925294834995373002301338698683743974893077640309963046456309618657832422797475818501015135906852080424133895494911183976328817926091022772243592459251888090147670287057585643275323939660320881180648902555638589673578617724238289116175077203222490898823699175460573599023599805417309765692714820463526045449960916874222673187703850319713340282078401730535036080820597052071005348515550129411869300808960274115568225369100194447467417531966980542490591995708755346795350887711952843240361569994219984238656364681756133283743169786685259452684011014727358883391099902477877780572220391954021259499834676538271762258604649928946322739410116864248127277877860900639787353103463444689684398081714097160618256576903798719246382080757297823076585775740327759258144506146007261826196350241272260815247354578089083716618365176721669572212667865905139727680240151496953498983419303669888661532448006157909512589237835571794150065789870495161363770041729927562723221458431224345732864680363325965277508696836977488581506164594543479676348467917092163953133579185037435295317733629631655691514338973029644674599596479518891770604926519771963147129099887179621712593311676704409319010280137557783139301957804760406930017493686233362208364230617280461390899520576847483959481124558945353376421772444655328002107480917667008464220843783560800966308955975969217869908159966317288711502615333317831238269693152317818591471840178937590957290503203513742997896626731194635318459449846704786150818784862780108352745197991359921126806007801453342396700113404536582067564862435492971468357364663069521391548113957170831985270800785893952034319484803063923703153023412579045834223616714712005395633620158498430139948416727930632407064810917294083622442609192004080154535128424767087101088860542648984252466083781639375670226095629017829648659180673789697118950563819451655702961480927330475708686337238206894381595329488475573308998998864736057827508866225449588186313486902616171403007326992545089806509185827908638249101741162517437136360363628780394246957996832664070822067157600004451979508587799087315803508277041676119659570676762040300857411118688833145379143175827627498031694645774838349116519123953213602265414589851322066085337171114150391934722208344065668445767810641865704232248865627820228967397926847000089884331454665171586252481095398733639112462924857478780620176528242691276634510127267531669918913777747770329826458753195182505488986704004818722197721404661583006853833119189168898056896659060659228111428731895554476958866987064509112719501279754428704389833195449841875857379612101154140187894017964563387312753598319256941530621711873010180550751576423437604136535568732156313839670560998504024828143380871169979056162555608434194698196431813075045398460601061176555422140530287023870433597371081073380271894716314387370071895136929280618104499327345625746424568408402747780599378813910034316157021980484397235462755208736407825765495137015655722558195455824438986914759637791941086837924650057743135378174275288319957011948388074327904881213865693052667851320960968892112245359052843125953856427540278995968624226079415319455156545501125022224434457734016917010908430282911556378455276750609256427774300949210042917746212439969193975746260676752217188298140217795159993722902906134601678423001525309914688492821891174278240840062617451968697701066775639504476696561536410098357044759773163289648906818777525689029488241629023817183043564237990777646330229394878046183790173084540342950518117711061358954284710195847824048772896841380008311768561147592963612785201284932803264504889663521846901315483141972410967842134181723060051899938171814159734826506187697938976807342131047570070309895889138743702457136853469546059244777350447512983486831672806392240388113740007767880114866549988741658800245027962329703526537747171703662538797189218822853919527803245925498247164304074019663424341928677725406367267123211155630112831946876340951577947839636601098370253308940280050297551725292375998292064743993636636705544671836027979251282549761940302241951232127867283327517699625980111641079873017145152142383757815545777475099039312313360838415899215408959437431583219873180758529220656214248053970295390592750950129209286486400399970169446914465134606408743304026767950849139126983595850930556047595985832179076559161018529829121086102684361227639522685959304582898352733618175969943143897386889079796769166157247322289172486204813921591438513195589633490255873492314139796957330040657579662189241437889909784846038287972242114064274391789491950984713377907783313985461288193463360376977994457348918289973562150111161243037468457105496521139385420933051150388930492610434304737895498035958225210091353378276458920317479822448043909109375361037850159958626257240791680127773803855875499984472237526662151489297173148768933873518622250791927751678405193844107427759917642162633579045204576116998833344029963863106563691977509328121086705743811033976751541061809550835866869877290294522138069963891796305336318519317054349357978083786647769258301322767992545754321660794712451027967611248813874316940112286634895162325845297513829862678933299535244376702936806434584521948153686384138141597697804137154560741602923047693474687080427849917462464836569000015148492487059355231428731091696933932186955413106999384100115443262140752221290238595846876879279727346501580349318370270821197342032169791465233130058432117177302662534391027664532559454433905139486164160233659674607306523831032287565593770243770490573578491984080697537038443594469427707907945351271866425343167358595723228055824162952823683214941170027690390104655655033935987156114269493297872299393798277483213852979240853706205411430632121233745613418542056385859441867512634788280517938358387256820821871813786662285563829666377669407910114112588283016804059979654682197387153340625106230979820457108058186633072798659431659439862250946348173229997382145717628768544517808121017802474137927521243625882913496568417856523634360537968959381884773006751163214796762968824240414185859427217704796256118529261953200853848047160335085116226288058315915678998966432747429588593543072246672029067249659791319702006532778038126081162091348525364163536830343349521142351164573284541328483456416683624011128673080060777185424930872291187800409647400266028804971997371007292391301157444191623334969357661248948249752684856244493961031679974967122508189494078738124797293960831203869646019809320883972756548548153487928523196407548541835202480850822841057602875772418384599548920836355665905628764809247617542623571229552176774112221405174710132147071448774914071551138497246619026361888362328497167788476616649558000870225615111503401956884906343196911211835417922453933770893656449011327215730748018288186384814937360055888780775226875498272321961073652722648210963467432016959485154072862000549258684866150188417591397346713658328482309349360694560529921622355858671733522812298050747793314543937573543605718722148997184723667311604788139318459028050677345078250457774992868501863273815558099275267550797237794100107831432852490759979122764959012196830340742068374247529512964186248109183123185470445253484832378480373352997554883826604817710574997771159291187589649293684868409642521904275692633651157450836371808574970653202995981435060722897075271745476058381320615871680049576353747342825609127521326722661494896610110119937583238761822892402927781903916264632614871357065787904741336675580888485819536121141355078348655558727473127846243624281821937663970679840039741452049153434508695363046215346539228248206742806000674389618855879059577320600436847695512107817731723537767398536305915747334418207319732670545481401639525412853130162715790866797184511928669623740280930837337046810572943968136710846525528711411327683351932351555382597020261992756453869943183278681466878081509095703953422292638441301730866605863295208142028480929051194222412264963783300760977248452685981306204517591371233605455363536354980942754446191074302322390931115640763332488467606273700385601463486962314844879498148599369928778499919394896603765032960053180539121227374598668422776385958231539487516184294599362785315569893634872021954621965034931870707379531186024360170289598599981678873613895333704654565486550938264267539979660445857067297948963911760107967923863592061500280468727670622220113684277878337850430345453405087010339108904818510535856093615268637862808641345731453023403138928994640616889981948409592097705693460579988028576391227100244049270757817972877962740392568941193514652103522130777321129313171847270564233786683041730418233270505968142240619413130121633036575457260979912713488578359872228579236404352972139045782603048806207924184623627046557125366794269665922963776815742204116124717382110688680772964921023247725782964834112270735161101393879765779325488000387127584197550898630552323568156042437442464730582752470731590026556557117234281807277477697281850316734395508184144471273327353695496798649281092437318086503263565485471298262023349583065815768688320486843431636254606438084901002677298764479982584966202226040516979442030475436420594330492770069157265426523852967717046703108261341869248385200169742146799039249351865776710654476557679703864303801106154659776925227192622225960964491730070235887846458518055067868858757303568280640225365328582958877548219684249654236776573820217360611919961876124190706427655783056248363862532447426994612580575155974227976780384140194272993292199121644420158749329979071512216383728776915440846975400660224566204231572270250408665576896300396643974459720700246568127354064139544895116502857798234955997590723529820457963796742340173907480105427930770925255088907753913741618722411431871357854696109786753041685072450529266367079668279777347509294782599547785519423599713758918986498455699391662537379930188633688970205963679965895038811674130152636679870332388814497382386889829026477722327114652066019563180709726657078488551102861203844610535028906686887857891790123237575924387962516298773590385326186165409351702802049608288610889621976267473065814482084936668768812760072113226472247569914253301376356716992508125447511248332556028650154921761646249146915107374117755074309257435782529058074655869831102980119072937401678640025549757375046681847489183716208283138123311208140250914487687251653086000679716567534196922591723825756739635210870761371926500435267927711770505837308829454766348749502655048289945415073234089310159577322901394847349645181046483471000764691687046866891489918486823455656203418863293036303534394167014714259109260007927530954823022797065022167769862282684822581618955567619588842395033327924030680177208213539771639867281298278936513981649554492119312997792804305789580290619392589635365072839674153274714248799905848137389658711106332875202853343679387301093148424437872885944757288158225415488222271383828659825032287780754085779456462918796944603587639527319557817315202136207274366309928967020457365157933987846882080034170514476011758061599768409534498173003597891874007323989703252368219422299642777693688378500864147651306006328980334133208577919486565661429316044100255281841978846661682058873018110491065319452522233063574563838075768791030694284648767595985930452950656091338899125556689420876014759608278221711802350228953234765405512646863120629052014943126807209559642860175011559493818733632737781373603133136578562528742028715004105775493667098554895779702408691107923289105280700178955065325806507792567757465387106804248028649623856516040303169675654702316855237092242828135529308029019481091318501297048311419084419024948218613446243959961036258504238021498014859906748762757323221388356473475700402635295539790312793745069946215826025387663633173432781052928631578291923338335649666333060724049374366612138618341822362591988257805775469125905710052403450673298636689497040374236090921871286316928137019747334166641655563980597536060722223517755502018285586406152705454130604202367353478974627423209381702703928075819054157672701444298577499597380483651886001988628250405749795751986633646190113754465351441619889760787811575844668233334255905670949048995326932587277609271163675159110497951222189793774923314590855656366194351417636898943035965240231592194435286854162158649159798611907537796514598785612077796415381629607113838480329755745073391617450862208108584219939846552143708161529748853894734259361445370320825513857022480851376309969273096204626650071068244937799063018469565102541697798543709860560630851651750310313143403561809946619912429799668057686207924377761158365881887633144552268714444666080669140724549718476074108707279258157203006329783317887840803107599228337654745026893494048894208681719330498657497514895486828249259584795070066267021672085246422274695910311992459825378153709053034589336339476529364922588890336728179491094014795007520601582582694103227481150953730407232520186770370593101471865095653973788285475041620337493784383510124766189496445829349771498381373940047122336692596808821662482750147102799317105172079963277413592222203735042484538306877243459647966913221048128375813742393616918518074240444595658909401444859144674690663451872998214025418125724562571998333117312226389571128889099778561231148103946962925609186758550512845539611357161303751532679949978553952910255567841785638140100441566471202545385080773236198515075768487935051286692032755574774832245359320399439403451691419169945702797475659327986432720818599359420034233941550386729803053162827392640635342041157730363098669274113809641750302699517672883577239049543079696710228316401918033262002906198632050076851356919416488582397621698140409687408698831799223424559154316659318985822567751004746320033714516934754675082872488544341973819249222452169618736286969371973502227256613223998444298569701504964856389792612322193972465102612630272455986763456418629137191149977239416428896369304029860570025799901819853421926922419128224899963206237371852090707404231153723615481762645327532601413991434746774634595321142503881898512396548331534490928445639777657098533229556236415407342711358818928222563757921437592855919258263789288596651329573640680334938359399376176461006717275994697973181096117933185178529603129977357133687303969731879365934282755173731921441017187980673721654125664609562938209846332963706089857722065526057966377127998341287137417097540276553407000260824864396225109481614674698747710045657094897924476027083600293773236826931024678299918932908466833168462685367460294733320932161534165531199257510178603584893959144485913587838358895966251745512153641980174015077484897203839925383707077759773288744285191546216371019417442891451933607780062164230479831866247571295204274506595727239214310578552258702273686664444452583896052117950437151763850836003756218367346479726469429415567574258384649653070275217153795664162662737571981211059483568637048210405535424208367524206730354571948751316682202920833694927884841944656053484454354715254007474430607338545475888447583961637132524115966819865607565131430348357651055442065966774342719678999589661962175687277812618119004128835213011084269684525686309965630633313345049841752578295801796961578588638198885947540185008517533477286080412818665856563608273327664314903739513058799721462377407050643505195015853455816838055808807596609763343842383737671832934498926936065029276957105618306880285495472780682464092558564630571634920891566583669953821196082328713409790904033523655484122881335162250248922055352001961337250056437702462895506892567971609280314447121020658399251232833019247811108551706435000774915321662187216453886359940217666703140462675249544964328162794346661116745902769357164239679910899979956913682836726300405379643941441961443942315543767005837309236439062218301090706367390282070234714107070061767723031063355294799993277284711949409540308510868205457343019459629305568074454165002732188310008221197253490479038659851198798762019962381204413243681060302116064539032742388781178591311341395665180704914178776709179287308081290777260920418416136549956644219052377254973246741127103563386747201234578693183093604201274990292283652576384999335810416770544627394374302776352641967477958641363148302596099519124733943851809368746190878677615185038480301292373164794677751765168502130118932711664594168588027302645676261815510858591546751816763605050409941963927903197132620625995321556950846258683997290739156392572056863876684228346472150490694779973959729181381081731316618668140294014944952290223080684966227705263910878450941474836426509753311398454941532265798612490607420407614980774435425701856130484428731682129279911209078827492117672243000821810773884927286402364429915192483847205727231118033913579558182759951989805233293302943024666506847569471297331207832386082155258164939744954925710760909769432563281594463443621286353085241455483691421294380089280231565348682349911395690671279025576184598574915024466440650869339112033361315372297217136092813547962887562728932913864914257869496850844216028491516977776607993020138674184109719861450347858506425095910173979309923081805581979862199682106823300585952135321275623270500954310019885066854840460989090062202906504885018896848001822151328109925559143984199435072902247697665375684941977923302183733846318973282461436844296959232436025793981587201106787924300333379294995563825683011537703073403390237770818378253860922731208146614082323503870160644515145613986692934459238308838715021660229670919836910972630175161758057117296799961722428263712641478533584584442718087516353260417200391272638476078925263589318587414594830819988715373411689143648943645804602648865569130540567312691218622585732766551104543543910981794794718780401691730812765177258213438852583337938710990471725283785144305512185526556663287556981070161996840808458321329678998390020884643833722560347846092815890874267511941743481260359950635364410000810830381450955365054762448866295745093766914320263063475930963046663565257493124175443192433491652790839498975458516155505749220190735574786123501567634648423388661660515353422791283265947598116129029818487183480550633307418735202975785219012378406172039847466161854824063734829694861146113638250846536275367762261798958604040467894143262626259360224780276304357613896366909054399481232380963984805927099406881844746689359240322799366913241895930165370376400782442583595698607557248037875860609584742611378301192583896811016230260282847489282279138045433623160714376959647743302538387870549668107273519326085785434859304995462898982320280501578229999392870335704050603978552744479841195850559847013379283412086851321524683988322997473565752677374388768615970731049113905053789005320571802279990917346571034906874395590475531680116898590211794938348600571408446581411749413689570514546495600749589230126110107968380167750869676043215874913187218397788329708552049802547639764178112435788554280446500233698864615214378918270290191372847941219758373244569970675859009946861895681310804913016729051236103989498847805161571874952837662947921112789029497139412324293933907423369320245852577938888284303197203411702716408159758186392624482118818190763590953287447396625100674896019857068539480616897517261700591633934027596781020109378374922133881019242763861335296643942466165512007413207561807721014739740059392560325879030410061574137266492076443235827672006675407090125792312745106999454830240581956056165742648328458030515087459016310236076369165404272730569011168547503798323962029211658730559312083954270121557890345216294966715758686982232398054132031388653576289411856924254512184684089360592356800137703152802684003206964453334711505578046081386653636074504634521813558122415812672007467221460271013544913277924543481076730129874463051145770535828557994769284948663444278561804117085800754581644284880584065262599053979435478870308411500725509808923610309109481834676455377833683360601665906706889255102414472829748440649785352643487961460200778246980692499330860009480909683675294608130250465360926756115243573868880793269368104712278138073259897806544308739601341850352932262290792631788519516943532542863256164656816588435535844191672941803687773884927977373088194421096317820144620181509974537494727564380719099498908180315548665736176159049600283073523688376756899298671828927109970640312555423291722328717941336797029425003424579881127806340599291764811273593267544232529655270160427779254039942668002859586518845163993869678548270891968641073882951875861374341313974488399769746011612951316394263087792621312720479808757482107242467333615265055157064669821188808331465553401865407309110132668233334730568910033793619897145142979667572858737214217592396164003529905081518285548071201159848615980711468198714466034717110606762575778240210444098912355901464931885547876364635508844533734042117945729708144689201750418544246407214510960779680344394312790515395234662443530581771061967127731823869654926741869912699338394026999489618046507191108970483793279445229226954450781633903057367655426116814004487356712024537743569130207407732676538620089549182031456495647999269224664072917955464526126261543881576356311631923768421827148556437568158883858501131538629350127194769413725622548701527166292008947552371881995295052715659117398182161897001331720996478213359971567413654749223115055477770842888298375306066790590199430015370676800855346547656449321887714390817377322482052372393058341882278542753040476733240432252785285352625680027726395839945039119398404218630951211849260422801082844268386707859035023520718130502690139151216424746339624273435849713760472550371080098706056258183707105957735511972385225211111277793064863953400202409588565512519407297700790498499328810584798983623446441129679922533395511126167373346806511940146010189696686144365091575342268154955629816037746132325615733123030537154442992149510277383271697066854240694309679685126039647886254946579035720346433860876024579704489127516392664988560246075873372901887444595832001282239924522919414271006781242509947130717289126528166506281190277605638886975293637553289657853865496526831622319486318683559578524308755996114949038100108561015055440232312435055080365270042070375614011731063577981687906744459117632015001364477407003362801353815141399671325575199897099310830128879808368514327854959193943174648847715565320559220946963955104795592198357294334183943003406698015192170882576882230780852679425950094216073786431587949119739275741623065931564023288136917750360187478755888468568887946818155339319698738486397119156423262067677824704333728588580608874711844204539020992363791541938446815059071258707815644869736483944743451542419682519757689965142961255671228974462738727080694259844919607137619168635702721515625617888683934614892822718537783212442704285519730102353341506877319344102014446571880755666951868703817215705619501096392553810193035594029648960398814417548530820033301017767312953149060073125408159201204885438329357783882734807864484474976151025742581987746706683673427799067670737133504527452632974410186476985329602901538207687438691723963038188634669575847995214824079446210516499706343431511614849174443572397656993662935239993463728744351149928112413059837849346599343360483747599995379921950230545797975053769975546031926884476821421618255113455873712877972793661419924106263133190807173948966787703127912112276007523752607269592725597596351294438520909743539064276337027589597344968648863336993642686319374358785979150621902405809119916354788357707230479721385294593228088252131386216374044597143597273532208341858105902575789783746448481475395216366066104617688067607965136246625605192197425395643490340491843704982317569184485977526246052075212853764034045488162837385370239579065129529530858239345711239737115323337196074663649252133562718991850491704593474703215849996540984204591037927440651821407068294091340808948232861170637896332711071313012518165637309876495965510861065665041860133015301375244349063162853712084125775615281153922673153168800048924669675121207833851584692329866905498163624748916393471626458227240892490585401834172939140669261885903919307397324599967287726458065326673575766884779970345602090709627125360654845126958256174099674444511395248794459023453667649646771945913412771813215379276953669480111389950230186578924512685475179270417987964242090846912740221864962916460767538435550899614405730240464867346377460009701561436137371947646079851856509965793286278396510607652072490298372228826814376657678131511421375295980856099021412490396285960309366865156281692273400387392024948179863918676306828761091782123897369852573855383164111237714863114578306463639566715174112124483445863948030037772151323738073756528257074202167081794230486330244511470104251792018530004796166035811553891720639376337558914056395941817932821558819281887608273407243612818503945964383155657339340884063148689324728825562128082656749289199722392296871368691184718704222958504701519976258218928112000992954492032461781506866949735951494287839052851680860034808292435882781192349256342198506484164889186822898203229149984099186526810399322276795907637283102363003753791139083602501725106004771671801701606126298667283409507087488729623441004286246897080965445686518502301204839030852189106579566875006028170754337878812675463198141055195864959097833509161632217904499588147548623432199416378856775752123882107690515315617738920186719355441967332363010171318479356615467224308322093237908727490993264972766556815852598839113406554398689391103782747149557795373849117483993660588466367221008336235862614677827113698031084530609432095366044785406019419081591348715211451082803040430714043822002942378292959270007944579556231541173912573479207798032283561480549906742174785768708248216158628231409254302396823383819434916689247004555380385159447377959202928865349779544735376706317536279466759834390074163528407944092990804516877746822632517129667407625317128409129067221917599565244069220708125642855987253435638959646485727973414404474869259638520135909120394479136747074980023521890554291907882459972598333917525910553988897572886819500901077718580677691555632738733275432954730639734813952936535149916645991583164734695483638933451487062614993198523971891012531741704387903182960880388534079348718513826787996019140562228758866766287662107346227525201871559141706994808048016468067594568983937216387124927677501024300637685211063971814369318919942050317615965064740375667612010583664157675587806714411647534753052230674432478579229851441706535372701722659331348260016996254462102886625936886487410350531406385134694205228919734067767808184980257809421316628714079104709678662063615510961230548336004824179964191113237613158851548064680488303226673254822634972659588309469056892026154625531136103222562878694231298965622650144305952210404932034764572257025401946990032804933911649102861138425939763457147099403095251498164752742776686163371586030096548071402351372400454915071725616730570664573976833086296244974346812342194830215953331865476068456609730668870490809270729062970379333868140951220871292300813649317920043154042894673564191879876978285604710654837630388825825784556443494673180935285286112500335576932860618372735928017595130208472822257032327924140958502034573293368234982928465651284466271189779914271597214036325109417228079076732062260318980260241660599644056705781252048052521881617818005474563160932689634088401436701031866480004473923110987935502991853899978032905434365390370110564477941729982291410447544743315218031213854491161919468112406452756086775494591661277739817973865730667440319896617117466154843755390935203426789583963629311212489453718637187335407790658213567531086266534785813714970960440477447829197671014509438505752493277345435782327595123740763779925743660312465440685925215533184369018277329270744665034919214234582383832511447778611638713254275949703409110686022448098321264119182638308863403080934712317602484454017482237969388618710998156015741198629554279740439942936179307742105389975964111231943676476946347439052463799807518538934997662783041985293525086185976184215365829493326135937135677314825846542993873729592911316996762716831820335071229024450539585663347908936706305440808696715366108897706156894478928094133544636956559069545125989720128897833600105013595018140854370238986075729563643722279254789512392364080254370291518283397049947915986026883262680070284121189894367621969750572817122969904055255025553403384168145975986913275069371184057437855838805331722120608419670732245981916900933475075732584143889473129099899433598869750426671516384821967914477942194407990204364780553664652043808719025149593488881280548484305811371988138429165256161796559685341779230417774835047176924234723805955917383607362971773364056797362960468331690684791489045358157574330533119163863521871693389155952457186897645981766570243477465294491208995009811520893241767328465668285013707957646611094835998610780093348395238293672905820065747459872617538463313731555284715964565538025405896789922743410424189610661974915895612979873626578563603856147944992827888304150990470261262576991334860305069969262662096906907599063908499524260869564103243566639378799998761477438620222654420309060979141746191170365223836811519292475660186414770629465317909415616099702071683968784501986100070048184314678256173404221707529136068009576521810056261045797427919443441727959299746131537851900657644226471850851586258965235856526566374142616166434632988607623368587672635760420096625386157064890601002524005265277333471981081419373992490467447447229033804868181604501484617983745207855817402842614247614909926757182902605403214822297140604891688029934893988840269876117233693490714966085067532582501710232402090596971675721027377081069468253884802274214546628926066259216054178771076914199674617930716352431895145101706440101411112553866987555578743271164381329380270841888858978293168932833188290452274538831547394698918284675165283427869429295523748973927144760502112771674593118818755987685130420565952203839150589786595970015423884711862458955879750997307107247170800874866298936738419825242331751500856875208143209779663496688170543235760494673445725889561456394967197911453976226211025374162948387726319660508038411910592678895189559377896359742856348261521852222921257449294138738337290310960132131089516757863586889183415568548061672213981295052062680572982887921381283463210700797696517757876076181451722499864842333901587387270305752512972440560447817787193995933812644833847996828454381661870398572667146023492561497079264979875554548449626513562106751715222246333991806550756849597694267646468284582362694818512169923548577382148083872457596546235211809351387283488753782434611638471991442102986142060795383108996912102397784987103805602644046160723187101800899543712127480218164651776014766190293969010454606354236544020162568776844735881243557169913006393604606476359750660038147448683920053213300937812639012330227807348722638345421147255238535275392268057675167505496057071543471523296678539961768576206213751973613620657818771084258159273867148855880557090022508577292475786926574748196056212732281329447368700262206575620692323535992472410358221117070133316844374233653152389037703695671723641746904278621257525566819020858931565743236306107142210012354212819530254418673041669021018031436221112892209649222134313442355397131361805507756252272905998423670395656947214471242972480569588050776566423771154645692633972815423462520390919543406820856312114396640156919209634402841148526690304683134201759883824142955888267507668069255299224775437139815139410456237823051821557014732836707089677755609989860232129105330778350809306192041877940702406305029581069336412558457018190440683058217591137270464386404066008277942165809194993445012738112325304424111121444030528640829554078433293700726437888859746062400726336693185069610927998642401599048768128483019716872405172742366702333027235689529262225394430280389948716219976266660523362913521759724963758488348561063862344031260705381010426269814723953534762058096919042403454487728324190915109538606756997416423550092894166173335045268625659870980470914434163630084041548845738160399041740877665243238388098679321484363303613179051872770432355211034038352984233805697178957680419990935517493580707432780441230424632829229716105041261594083452244993017506583870024332476723942239942275630968576224669066665048909559644342959549925429103815747664276051837088059701997477107440425021981051740905844053995746925171844037841823522441611867345433208379741347009406659919379208878761799827677548449306681397552694707427117631406144007450882969740049818323455858551317207197201589704858224388374914095841726938767482243085025897244690463595978336569707778625455613570273121541638995145894561079999213500076101248781500642979091198044736325729107144579768273776743716439557581557253878204647391176582851167312182026188795156620056856503340092247479478684738621107994804323593105039052556442336528920420940314

%time sum(lis)

CPU times: user 22.7 ms, sys: 0 ns, total: 22.7 ms
Wall time: 22.5 ms

2846544363824575411974133954272619447111476638986894150012068192690648834822200375328623622649745580730890329122417061399092026367020912838755646170763908089934263209682209676395802305048393839091236470474746103428494533306061637172900505116511423331761625723616902965848646144551445843453846601043472140662768746876455627207172302258019849932982986172347202808699197500145264692178231587867662062549429711726296104245560244800328117790974954274775113117954784558630938125324273430112543205480861675651721627094367916546971289233044597490676922741513533077983261454279143861733997064136506468583014643578449887422109896384223975107657283065356625047353369121126710585754986841505084319859185693074595980106439823016770720114936030638192079242528151508509453651260413563942407746086542464468798628153168566253427058189953115669810936028069337688050383655751449626149958745333417122255040192992590152142618889918050674820940189690936512153268955306076044738454065677445507497956298031359601460367688123266887407344527837034309657698507862661999741532135891188296772291635681752303038172869531003223585402881390352766425619307435012467320183719687432594324680313288252624242375547112390108053017995207632836834150270789473466371686004337524599724740217981823616290088586476828101799644024744426478583726007888483264414554576305602530855056181263518809361459388852398362047950800131137495032222648513578141077248463979823869139860815403856130492247559755892995167553333224974779391126764697778076426829111376006060545847483757890898006274736768319058986311096687542618253624486468868725256035010229277952796635850928901479716426794120662258316292264250967727926004512503274777609080671425302740687757372996123918141094091193982621777991477755327127633302538305482538054051626059422151028115545481979087246407512893443284100119581177881959766159964495179499286146163903490422234385433657118291345894580636366781894966217065024421175587401876155198441396792500685769104016737183666833177485769214532968463249068944579900820399160086485553759152015879779185583488564365971795010517215769981674461364752853509589251752862536295732482411885635226343327653727873663671894405284455124011910658188814408622643501663319543292027524523922495560386863821765829130657380834313878766854120042276219799225342085380997669521124494851955656077827887030486351082366882208471287748817054316050107367560969009693282756370472732021261303106425078877265159573484298300310617225618494554270567290041105781150281831591592109244118532878725466135569732211174564485617093980109027839564785141458625886797987204861020824764731436681556386922671088897865299421217279461134563652990841385932187925461051951940996619068739335001584501274021170189440819037046767067662893632724766003004567705781930829019319143985210860581069812804196559369206300181574397330972510925294834995373002301338698683743974893077640309963046456309618657832422797475818501015135906852080424133895494911183976328817926091022772243592459251888090147670287057585643275323939660320881180648902555638589673578617724238289116175077203222490898823699175460573599023599805417309765692714820463526045449960916874222673187703850319713340282078401730535036080820597052071005348515550129411869300808960274115568225369100194447467417531966980542490591995708755346795350887711952843240361569994219984238656364681756133283743169786685259452684011014727358883391099902477877780572220391954021259499834676538271762258604649928946322739410116864248127277877860900639787353103463444689684398081714097160618256576903798719246382080757297823076585775740327759258144506146007261826196350241272260815247354578089083716618365176721669572212667865905139727680240151496953498983419303669888661532448006157909512589237835571794150065789870495161363770041729927562723221458431224345732864680363325965277508696836977488581506164594543479676348467917092163953133579185037435295317733629631655691514338973029644674599596479518891770604926519771963147129099887179621712593311676704409319010280137557783139301957804760406930017493686233362208364230617280461390899520576847483959481124558945353376421772444655328002107480917667008464220843783560800966308955975969217869908159966317288711502615333317831238269693152317818591471840178937590957290503203513742997896626731194635318459449846704786150818784862780108352745197991359921126806007801453342396700113404536582067564862435492971468357364663069521391548113957170831985270800785893952034319484803063923703153023412579045834223616714712005395633620158498430139948416727930632407064810917294083622442609192004080154535128424767087101088860542648984252466083781639375670226095629017829648659180673789697118950563819451655702961480927330475708686337238206894381595329488475573308998998864736057827508866225449588186313486902616171403007326992545089806509185827908638249101741162517437136360363628780394246957996832664070822067157600004451979508587799087315803508277041676119659570676762040300857411118688833145379143175827627498031694645774838349116519123953213602265414589851322066085337171114150391934722208344065668445767810641865704232248865627820228967397926847000089884331454665171586252481095398733639112462924857478780620176528242691276634510127267531669918913777747770329826458753195182505488986704004818722197721404661583006853833119189168898056896659060659228111428731895554476958866987064509112719501279754428704389833195449841875857379612101154140187894017964563387312753598319256941530621711873010180550751576423437604136535568732156313839670560998504024828143380871169979056162555608434194698196431813075045398460601061176555422140530287023870433597371081073380271894716314387370071895136929280618104499327345625746424568408402747780599378813910034316157021980484397235462755208736407825765495137015655722558195455824438986914759637791941086837924650057743135378174275288319957011948388074327904881213865693052667851320960968892112245359052843125953856427540278995968624226079415319455156545501125022224434457734016917010908430282911556378455276750609256427774300949210042917746212439969193975746260676752217188298140217795159993722902906134601678423001525309914688492821891174278240840062617451968697701066775639504476696561536410098357044759773163289648906818777525689029488241629023817183043564237990777646330229394878046183790173084540342950518117711061358954284710195847824048772896841380008311768561147592963612785201284932803264504889663521846901315483141972410967842134181723060051899938171814159734826506187697938976807342131047570070309895889138743702457136853469546059244777350447512983486831672806392240388113740007767880114866549988741658800245027962329703526537747171703662538797189218822853919527803245925498247164304074019663424341928677725406367267123211155630112831946876340951577947839636601098370253308940280050297551725292375998292064743993636636705544671836027979251282549761940302241951232127867283327517699625980111641079873017145152142383757815545777475099039312313360838415899215408959437431583219873180758529220656214248053970295390592750950129209286486400399970169446914465134606408743304026767950849139126983595850930556047595985832179076559161018529829121086102684361227639522685959304582898352733618175969943143897386889079796769166157247322289172486204813921591438513195589633490255873492314139796957330040657579662189241437889909784846038287972242114064274391789491950984713377907783313985461288193463360376977994457348918289973562150111161243037468457105496521139385420933051150388930492610434304737895498035958225210091353378276458920317479822448043909109375361037850159958626257240791680127773803855875499984472237526662151489297173148768933873518622250791927751678405193844107427759917642162633579045204576116998833344029963863106563691977509328121086705743811033976751541061809550835866869877290294522138069963891796305336318519317054349357978083786647769258301322767992545754321660794712451027967611248813874316940112286634895162325845297513829862678933299535244376702936806434584521948153686384138141597697804137154560741602923047693474687080427849917462464836569000015148492487059355231428731091696933932186955413106999384100115443262140752221290238595846876879279727346501580349318370270821197342032169791465233130058432117177302662534391027664532559454433905139486164160233659674607306523831032287565593770243770490573578491984080697537038443594469427707907945351271866425343167358595723228055824162952823683214941170027690390104655655033935987156114269493297872299393798277483213852979240853706205411430632121233745613418542056385859441867512634788280517938358387256820821871813786662285563829666377669407910114112588283016804059979654682197387153340625106230979820457108058186633072798659431659439862250946348173229997382145717628768544517808121017802474137927521243625882913496568417856523634360537968959381884773006751163214796762968824240414185859427217704796256118529261953200853848047160335085116226288058315915678998966432747429588593543072246672029067249659791319702006532778038126081162091348525364163536830343349521142351164573284541328483456416683624011128673080060777185424930872291187800409647400266028804971997371007292391301157444191623334969357661248948249752684856244493961031679974967122508189494078738124797293960831203869646019809320883972756548548153487928523196407548541835202480850822841057602875772418384599548920836355665905628764809247617542623571229552176774112221405174710132147071448774914071551138497246619026361888362328497167788476616649558000870225615111503401956884906343196911211835417922453933770893656449011327215730748018288186384814937360055888780775226875498272321961073652722648210963467432016959485154072862000549258684866150188417591397346713658328482309349360694560529921622355858671733522812298050747793314543937573543605718722148997184723667311604788139318459028050677345078250457774992868501863273815558099275267550797237794100107831432852490759979122764959012196830340742068374247529512964186248109183123185470445253484832378480373352997554883826604817710574997771159291187589649293684868409642521904275692633651157450836371808574970653202995981435060722897075271745476058381320615871680049576353747342825609127521326722661494896610110119937583238761822892402927781903916264632614871357065787904741336675580888485819536121141355078348655558727473127846243624281821937663970679840039741452049153434508695363046215346539228248206742806000674389618855879059577320600436847695512107817731723537767398536305915747334418207319732670545481401639525412853130162715790866797184511928669623740280930837337046810572943968136710846525528711411327683351932351555382597020261992756453869943183278681466878081509095703953422292638441301730866605863295208142028480929051194222412264963783300760977248452685981306204517591371233605455363536354980942754446191074302322390931115640763332488467606273700385601463486962314844879498148599369928778499919394896603765032960053180539121227374598668422776385958231539487516184294599362785315569893634872021954621965034931870707379531186024360170289598599981678873613895333704654565486550938264267539979660445857067297948963911760107967923863592061500280468727670622220113684277878337850430345453405087010339108904818510535856093615268637862808641345731453023403138928994640616889981948409592097705693460579988028576391227100244049270757817972877962740392568941193514652103522130777321129313171847270564233786683041730418233270505968142240619413130121633036575457260979912713488578359872228579236404352972139045782603048806207924184623627046557125366794269665922963776815742204116124717382110688680772964921023247725782964834112270735161101393879765779325488000387127584197550898630552323568156042437442464730582752470731590026556557117234281807277477697281850316734395508184144471273327353695496798649281092437318086503263565485471298262023349583065815768688320486843431636254606438084901002677298764479982584966202226040516979442030475436420594330492770069157265426523852967717046703108261341869248385200169742146799039249351865776710654476557679703864303801106154659776925227192622225960964491730070235887846458518055067868858757303568280640225365328582958877548219684249654236776573820217360611919961876124190706427655783056248363862532447426994612580575155974227976780384140194272993292199121644420158749329979071512216383728776915440846975400660224566204231572270250408665576896300396643974459720700246568127354064139544895116502857798234955997590723529820457963796742340173907480105427930770925255088907753913741618722411431871357854696109786753041685072450529266367079668279777347509294782599547785519423599713758918986498455699391662537379930188633688970205963679965895038811674130152636679870332388814497382386889829026477722327114652066019563180709726657078488551102861203844610535028906686887857891790123237575924387962516298773590385326186165409351702802049608288610889621976267473065814482084936668768812760072113226472247569914253301376356716992508125447511248332556028650154921761646249146915107374117755074309257435782529058074655869831102980119072937401678640025549757375046681847489183716208283138123311208140250914487687251653086000679716567534196922591723825756739635210870761371926500435267927711770505837308829454766348749502655048289945415073234089310159577322901394847349645181046483471000764691687046866891489918486823455656203418863293036303534394167014714259109260007927530954823022797065022167769862282684822581618955567619588842395033327924030680177208213539771639867281298278936513981649554492119312997792804305789580290619392589635365072839674153274714248799905848137389658711106332875202853343679387301093148424437872885944757288158225415488222271383828659825032287780754085779456462918796944603587639527319557817315202136207274366309928967020457365157933987846882080034170514476011758061599768409534498173003597891874007323989703252368219422299642777693688378500864147651306006328980334133208577919486565661429316044100255281841978846661682058873018110491065319452522233063574563838075768791030694284648767595985930452950656091338899125556689420876014759608278221711802350228953234765405512646863120629052014943126807209559642860175011559493818733632737781373603133136578562528742028715004105775493667098554895779702408691107923289105280700178955065325806507792567757465387106804248028649623856516040303169675654702316855237092242828135529308029019481091318501297048311419084419024948218613446243959961036258504238021498014859906748762757323221388356473475700402635295539790312793745069946215826025387663633173432781052928631578291923338335649666333060724049374366612138618341822362591988257805775469125905710052403450673298636689497040374236090921871286316928137019747334166641655563980597536060722223517755502018285586406152705454130604202367353478974627423209381702703928075819054157672701444298577499597380483651886001988628250405749795751986633646190113754465351441619889760787811575844668233334255905670949048995326932587277609271163675159110497951222189793774923314590855656366194351417636898943035965240231592194435286854162158649159798611907537796514598785612077796415381629607113838480329755745073391617450862208108584219939846552143708161529748853894734259361445370320825513857022480851376309969273096204626650071068244937799063018469565102541697798543709860560630851651750310313143403561809946619912429799668057686207924377761158365881887633144552268714444666080669140724549718476074108707279258157203006329783317887840803107599228337654745026893494048894208681719330498657497514895486828249259584795070066267021672085246422274695910311992459825378153709053034589336339476529364922588890336728179491094014795007520601582582694103227481150953730407232520186770370593101471865095653973788285475041620337493784383510124766189496445829349771498381373940047122336692596808821662482750147102799317105172079963277413592222203735042484538306877243459647966913221048128375813742393616918518074240444595658909401444859144674690663451872998214025418125724562571998333117312226389571128889099778561231148103946962925609186758550512845539611357161303751532679949978553952910255567841785638140100441566471202545385080773236198515075768487935051286692032755574774832245359320399439403451691419169945702797475659327986432720818599359420034233941550386729803053162827392640635342041157730363098669274113809641750302699517672883577239049543079696710228316401918033262002906198632050076851356919416488582397621698140409687408698831799223424559154316659318985822567751004746320033714516934754675082872488544341973819249222452169618736286969371973502227256613223998444298569701504964856389792612322193972465102612630272455986763456418629137191149977239416428896369304029860570025799901819853421926922419128224899963206237371852090707404231153723615481762645327532601413991434746774634595321142503881898512396548331534490928445639777657098533229556236415407342711358818928222563757921437592855919258263789288596651329573640680334938359399376176461006717275994697973181096117933185178529603129977357133687303969731879365934282755173731921441017187980673721654125664609562938209846332963706089857722065526057966377127998341287137417097540276553407000260824864396225109481614674698747710045657094897924476027083600293773236826931024678299918932908466833168462685367460294733320932161534165531199257510178603584893959144485913587838358895966251745512153641980174015077484897203839925383707077759773288744285191546216371019417442891451933607780062164230479831866247571295204274506595727239214310578552258702273686664444452583896052117950437151763850836003756218367346479726469429415567574258384649653070275217153795664162662737571981211059483568637048210405535424208367524206730354571948751316682202920833694927884841944656053484454354715254007474430607338545475888447583961637132524115966819865607565131430348357651055442065966774342719678999589661962175687277812618119004128835213011084269684525686309965630633313345049841752578295801796961578588638198885947540185008517533477286080412818665856563608273327664314903739513058799721462377407050643505195015853455816838055808807596609763343842383737671832934498926936065029276957105618306880285495472780682464092558564630571634920891566583669953821196082328713409790904033523655484122881335162250248922055352001961337250056437702462895506892567971609280314447121020658399251232833019247811108551706435000774915321662187216453886359940217666703140462675249544964328162794346661116745902769357164239679910899979956913682836726300405379643941441961443942315543767005837309236439062218301090706367390282070234714107070061767723031063355294799993277284711949409540308510868205457343019459629305568074454165002732188310008221197253490479038659851198798762019962381204413243681060302116064539032742388781178591311341395665180704914178776709179287308081290777260920418416136549956644219052377254973246741127103563386747201234578693183093604201274990292283652576384999335810416770544627394374302776352641967477958641363148302596099519124733943851809368746190878677615185038480301292373164794677751765168502130118932711664594168588027302645676261815510858591546751816763605050409941963927903197132620625995321556950846258683997290739156392572056863876684228346472150490694779973959729181381081731316618668140294014944952290223080684966227705263910878450941474836426509753311398454941532265798612490607420407614980774435425701856130484428731682129279911209078827492117672243000821810773884927286402364429915192483847205727231118033913579558182759951989805233293302943024666506847569471297331207832386082155258164939744954925710760909769432563281594463443621286353085241455483691421294380089280231565348682349911395690671279025576184598574915024466440650869339112033361315372297217136092813547962887562728932913864914257869496850844216028491516977776607993020138674184109719861450347858506425095910173979309923081805581979862199682106823300585952135321275623270500954310019885066854840460989090062202906504885018896848001822151328109925559143984199435072902247697665375684941977923302183733846318973282461436844296959232436025793981587201106787924300333379294995563825683011537703073403390237770818378253860922731208146614082323503870160644515145613986692934459238308838715021660229670919836910972630175161758057117296799961722428263712641478533584584442718087516353260417200391272638476078925263589318587414594830819988715373411689143648943645804602648865569130540567312691218622585732766551104543543910981794794718780401691730812765177258213438852583337938710990471725283785144305512185526556663287556981070161996840808458321329678998390020884643833722560347846092815890874267511941743481260359950635364410000810830381450955365054762448866295745093766914320263063475930963046663565257493124175443192433491652790839498975458516155505749220190735574786123501567634648423388661660515353422791283265947598116129029818487183480550633307418735202975785219012378406172039847466161854824063734829694861146113638250846536275367762261798958604040467894143262626259360224780276304357613896366909054399481232380963984805927099406881844746689359240322799366913241895930165370376400782442583595698607557248037875860609584742611378301192583896811016230260282847489282279138045433623160714376959647743302538387870549668107273519326085785434859304995462898982320280501578229999392870335704050603978552744479841195850559847013379283412086851321524683988322997473565752677374388768615970731049113905053789005320571802279990917346571034906874395590475531680116898590211794938348600571408446581411749413689570514546495600749589230126110107968380167750869676043215874913187218397788329708552049802547639764178112435788554280446500233698864615214378918270290191372847941219758373244569970675859009946861895681310804913016729051236103989498847805161571874952837662947921112789029497139412324293933907423369320245852577938888284303197203411702716408159758186392624482118818190763590953287447396625100674896019857068539480616897517261700591633934027596781020109378374922133881019242763861335296643942466165512007413207561807721014739740059392560325879030410061574137266492076443235827672006675407090125792312745106999454830240581956056165742648328458030515087459016310236076369165404272730569011168547503798323962029211658730559312083954270121557890345216294966715758686982232398054132031388653576289411856924254512184684089360592356800137703152802684003206964453334711505578046081386653636074504634521813558122415812672007467221460271013544913277924543481076730129874463051145770535828557994769284948663444278561804117085800754581644284880584065262599053979435478870308411500725509808923610309109481834676455377833683360601665906706889255102414472829748440649785352643487961460200778246980692499330860009480909683675294608130250465360926756115243573868880793269368104712278138073259897806544308739601341850352932262290792631788519516943532542863256164656816588435535844191672941803687773884927977373088194421096317820144620181509974537494727564380719099498908180315548665736176159049600283073523688376756899298671828927109970640312555423291722328717941336797029425003424579881127806340599291764811273593267544232529655270160427779254039942668002859586518845163993869678548270891968641073882951875861374341313974488399769746011612951316394263087792621312720479808757482107242467333615265055157064669821188808331465553401865407309110132668233334730568910033793619897145142979667572858737214217592396164003529905081518285548071201159848615980711468198714466034717110606762575778240210444098912355901464931885547876364635508844533734042117945729708144689201750418544246407214510960779680344394312790515395234662443530581771061967127731823869654926741869912699338394026999489618046507191108970483793279445229226954450781633903057367655426116814004487356712024537743569130207407732676538620089549182031456495647999269224664072917955464526126261543881576356311631923768421827148556437568158883858501131538629350127194769413725622548701527166292008947552371881995295052715659117398182161897001331720996478213359971567413654749223115055477770842888298375306066790590199430015370676800855346547656449321887714390817377322482052372393058341882278542753040476733240432252785285352625680027726395839945039119398404218630951211849260422801082844268386707859035023520718130502690139151216424746339624273435849713760472550371080098706056258183707105957735511972385225211111277793064863953400202409588565512519407297700790498499328810584798983623446441129679922533395511126167373346806511940146010189696686144365091575342268154955629816037746132325615733123030537154442992149510277383271697066854240694309679685126039647886254946579035720346433860876024579704489127516392664988560246075873372901887444595832001282239924522919414271006781242509947130717289126528166506281190277605638886975293637553289657853865496526831622319486318683559578524308755996114949038100108561015055440232312435055080365270042070375614011731063577981687906744459117632015001364477407003362801353815141399671325575199897099310830128879808368514327854959193943174648847715565320559220946963955104795592198357294334183943003406698015192170882576882230780852679425950094216073786431587949119739275741623065931564023288136917750360187478755888468568887946818155339319698738486397119156423262067677824704333728588580608874711844204539020992363791541938446815059071258707815644869736483944743451542419682519757689965142961255671228974462738727080694259844919607137619168635702721515625617888683934614892822718537783212442704285519730102353341506877319344102014446571880755666951868703817215705619501096392553810193035594029648960398814417548530820033301017767312953149060073125408159201204885438329357783882734807864484474976151025742581987746706683673427799067670737133504527452632974410186476985329602901538207687438691723963038188634669575847995214824079446210516499706343431511614849174443572397656993662935239993463728744351149928112413059837849346599343360483747599995379921950230545797975053769975546031926884476821421618255113455873712877972793661419924106263133190807173948966787703127912112276007523752607269592725597596351294438520909743539064276337027589597344968648863336993642686319374358785979150621902405809119916354788357707230479721385294593228088252131386216374044597143597273532208341858105902575789783746448481475395216366066104617688067607965136246625605192197425395643490340491843704982317569184485977526246052075212853764034045488162837385370239579065129529530858239345711239737115323337196074663649252133562718991850491704593474703215849996540984204591037927440651821407068294091340808948232861170637896332711071313012518165637309876495965510861065665041860133015301375244349063162853712084125775615281153922673153168800048924669675121207833851584692329866905498163624748916393471626458227240892490585401834172939140669261885903919307397324599967287726458065326673575766884779970345602090709627125360654845126958256174099674444511395248794459023453667649646771945913412771813215379276953669480111389950230186578924512685475179270417987964242090846912740221864962916460767538435550899614405730240464867346377460009701561436137371947646079851856509965793286278396510607652072490298372228826814376657678131511421375295980856099021412490396285960309366865156281692273400387392024948179863918676306828761091782123897369852573855383164111237714863114578306463639566715174112124483445863948030037772151323738073756528257074202167081794230486330244511470104251792018530004796166035811553891720639376337558914056395941817932821558819281887608273407243612818503945964383155657339340884063148689324728825562128082656749289199722392296871368691184718704222958504701519976258218928112000992954492032461781506866949735951494287839052851680860034808292435882781192349256342198506484164889186822898203229149984099186526810399322276795907637283102363003753791139083602501725106004771671801701606126298667283409507087488729623441004286246897080965445686518502301204839030852189106579566875006028170754337878812675463198141055195864959097833509161632217904499588147548623432199416378856775752123882107690515315617738920186719355441967332363010171318479356615467224308322093237908727490993264972766556815852598839113406554398689391103782747149557795373849117483993660588466367221008336235862614677827113698031084530609432095366044785406019419081591348715211451082803040430714043822002942378292959270007944579556231541173912573479207798032283561480549906742174785768708248216158628231409254302396823383819434916689247004555380385159447377959202928865349779544735376706317536279466759834390074163528407944092990804516877746822632517129667407625317128409129067221917599565244069220708125642855987253435638959646485727973414404474869259638520135909120394479136747074980023521890554291907882459972598333917525910553988897572886819500901077718580677691555632738733275432954730639734813952936535149916645991583164734695483638933451487062614993198523971891012531741704387903182960880388534079348718513826787996019140562228758866766287662107346227525201871559141706994808048016468067594568983937216387124927677501024300637685211063971814369318919942050317615965064740375667612010583664157675587806714411647534753052230674432478579229851441706535372701722659331348260016996254462102886625936886487410350531406385134694205228919734067767808184980257809421316628714079104709678662063615510961230548336004824179964191113237613158851548064680488303226673254822634972659588309469056892026154625531136103222562878694231298965622650144305952210404932034764572257025401946990032804933911649102861138425939763457147099403095251498164752742776686163371586030096548071402351372400454915071725616730570664573976833086296244974346812342194830215953331865476068456609730668870490809270729062970379333868140951220871292300813649317920043154042894673564191879876978285604710654837630388825825784556443494673180935285286112500335576932860618372735928017595130208472822257032327924140958502034573293368234982928465651284466271189779914271597214036325109417228079076732062260318980260241660599644056705781252048052521881617818005474563160932689634088401436701031866480004473923110987935502991853899978032905434365390370110564477941729982291410447544743315218031213854491161919468112406452756086775494591661277739817973865730667440319896617117466154843755390935203426789583963629311212489453718637187335407790658213567531086266534785813714970960440477447829197671014509438505752493277345435782327595123740763779925743660312465440685925215533184369018277329270744665034919214234582383832511447778611638713254275949703409110686022448098321264119182638308863403080934712317602484454017482237969388618710998156015741198629554279740439942936179307742105389975964111231943676476946347439052463799807518538934997662783041985293525086185976184215365829493326135937135677314825846542993873729592911316996762716831820335071229024450539585663347908936706305440808696715366108897706156894478928094133544636956559069545125989720128897833600105013595018140854370238986075729563643722279254789512392364080254370291518283397049947915986026883262680070284121189894367621969750572817122969904055255025553403384168145975986913275069371184057437855838805331722120608419670732245981916900933475075732584143889473129099899433598869750426671516384821967914477942194407990204364780553664652043808719025149593488881280548484305811371988138429165256161796559685341779230417774835047176924234723805955917383607362971773364056797362960468331690684791489045358157574330533119163863521871693389155952457186897645981766570243477465294491208995009811520893241767328465668285013707957646611094835998610780093348395238293672905820065747459872617538463313731555284715964565538025405896789922743410424189610661974915895612979873626578563603856147944992827888304150990470261262576991334860305069969262662096906907599063908499524260869564103243566639378799998761477438620222654420309060979141746191170365223836811519292475660186414770629465317909415616099702071683968784501986100070048184314678256173404221707529136068009576521810056261045797427919443441727959299746131537851900657644226471850851586258965235856526566374142616166434632988607623368587672635760420096625386157064890601002524005265277333471981081419373992490467447447229033804868181604501484617983745207855817402842614247614909926757182902605403214822297140604891688029934893988840269876117233693490714966085067532582501710232402090596971675721027377081069468253884802274214546628926066259216054178771076914199674617930716352431895145101706440101411112553866987555578743271164381329380270841888858978293168932833188290452274538831547394698918284675165283427869429295523748973927144760502112771674593118818755987685130420565952203839150589786595970015423884711862458955879750997307107247170800874866298936738419825242331751500856875208143209779663496688170543235760494673445725889561456394967197911453976226211025374162948387726319660508038411910592678895189559377896359742856348261521852222921257449294138738337290310960132131089516757863586889183415568548061672213981295052062680572982887921381283463210700797696517757876076181451722499864842333901587387270305752512972440560447817787193995933812644833847996828454381661870398572667146023492561497079264979875554548449626513562106751715222246333991806550756849597694267646468284582362694818512169923548577382148083872457596546235211809351387283488753782434611638471991442102986142060795383108996912102397784987103805602644046160723187101800899543712127480218164651776014766190293969010454606354236544020162568776844735881243557169913006393604606476359750660038147448683920053213300937812639012330227807348722638345421147255238535275392268057675167505496057071543471523296678539961768576206213751973613620657818771084258159273867148855880557090022508577292475786926574748196056212732281329447368700262206575620692323535992472410358221117070133316844374233653152389037703695671723641746904278621257525566819020858931565743236306107142210012354212819530254418673041669021018031436221112892209649222134313442355397131361805507756252272905998423670395656947214471242972480569588050776566423771154645692633972815423462520390919543406820856312114396640156919209634402841148526690304683134201759883824142955888267507668069255299224775437139815139410456237823051821557014732836707089677755609989860232129105330778350809306192041877940702406305029581069336412558457018190440683058217591137270464386404066008277942165809194993445012738112325304424111121444030528640829554078433293700726437888859746062400726336693185069610927998642401599048768128483019716872405172742366702333027235689529262225394430280389948716219976266660523362913521759724963758488348561063862344031260705381010426269814723953534762058096919042403454487728324190915109538606756997416423550092894166173335045268625659870980470914434163630084041548845738160399041740877665243238388098679321484363303613179051872770432355211034038352984233805697178957680419990935517493580707432780441230424632829229716105041261594083452244993017506583870024332476723942239942275630968576224669066665048909559644342959549925429103815747664276051837088059701997477107440425021981051740905844053995746925171844037841823522441611867345433208379741347009406659919379208878761799827677548449306681397552694707427117631406144007450882969740049818323455858551317207197201589704858224388374914095841726938767482243085025897244690463595978336569707778625455613570273121541638995145894561079999213500076101248781500642979091198044736325729107144579768273776743716439557581557253878204647391176582851167312182026188795156620056856503340092247479478684738621107994804323593105039052556442336528920420940314

En effet on a payé et on voit que globalement les temps sont équivalent. La liste est longue a créer mais ensuite c'est rapide, le générateur prend du temps lorsqu'on parcours les éléments.

La différence principale est dans l'occupation de la mémoire puisque le générateur n'occupe quasiment pas de place mémoire.

yield pour les cas complexes

Si on désire construire un générateur plus compliqué ou plus malin que celui de l'exemple précédant, on peut le faire avec une fonction dont la mission est de retourner l'élément suivant (avec le mot clef yield).

Dans notre cas on utilise le fait qu'il est simple de calculer n! lorsqu'on connait (n-1)!. Cela va permettre un gain de temps très significatif.

def gen_factorials(n):
    ''' generate all factorials from 1 to n
    '''
    res = 1
    for i in range(1, n+1):
        res *= i
        yield res

Lorsque l'exécution de la fonction arrive à yield, le résultat est retourné et la fonction est mise en pause jusqu'à ce qu'on lui demande l'élément suivant avec la fonction next() (ou la méthode __next__()) ou en laissant la boucle faire l'appel ce qui est la bonne facon de faire.

g = gen_factorials(4)
type(g)

generator

for i in range(5):
    print(next(g))   # same than g.__next__()

1
2
6
24

---------------------------------------------------------------------------
StopIteration                             Traceback (most recent call last)
/tmp/ipykernel_139854/2935362037.py in <module>
      1 for i in range(5):
----> 2     print(next(g))   # same than g.__next__()

StopIteration: 

On voit que yield ne peut être appelé que n fois, ensuite on a une exception StopIteration.

Mais en pratique on utilise un générateur ainsi (et donc sans risque de débordement) :

%%timeit
sum = 0
for x in gen_factorials(10000):
    sum += x

33.5 ms ± 1.43 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

Le générateur malin avec 0,033 seconde est nettement plus rapide que le générateur de base ou l'utilsation de la liste (tous les deux à 7,7 secondes sur ma machine).

{{ PreviousNext("03 - Formatting.ipynb", "10 sys - under the hood.ipynb")}}