Python-сообщество
Форум сайта python.su
- Вы не вошли.
Уведомления
Группа в Telegram: @pythonsu
- Начало
- » Python для новичков
- » Рекурсивный алгоритм Фибоначчи с использованием кэша
![[RSS Feed]](/static/djangobb_forum/img/feed-icon-small.png "[RSS Feed]")
#1 Март 31, 2020 14:38:20
- ElmarB
-
-
- Зарегистрирован: 2020-02-24
- Сообщения: 19
- Репутация:
0 
- Профиль Отправить e-mail
Рекурсивный алгоритм Фибоначчи с использованием кэша
Здравствуйте!
Написал код рекурсивного алгоритма Фибоначчи с использованием кэша
И теперь хотелось бы узнать можно ли написать его покороче или усовершенствовать?
Спасибо!
def fib(n): if cache[n] == 0: if n == 1 or n == 2: cache[n] = 1 else: cache[n] = fib(n-1)+fib(n-2) return cache[n] cache = [0]*100 cache[0] = 0 cache[1] = 1 cache[2] = cache[0]+cache[1] cache[0] = cache[1] cache[1] = cache[2] print(fib(99))
Офлайн
#2 Апрель 1, 2020 15:09:26
- Striver
-
-
- От:
- Зарегистрирован: 2006-10-26
- Сообщения: 247
- Репутация:
22
- Профиль Отправить e-mail
Рекурсивный алгоритм Фибоначчи с использованием кэша
можно ли написать его покороче или усовершенствовать?Ну, разве что использовать кеширование из стандартной библиотеки:
from cachetools.func import lfu_cache @lfu_cache(maxsize=1000) def fib(n): if n in (1,2): return 1 else: return fib(n-1) +fib(n-2)
Офлайн
#3 Апрель 1, 2020 22:19:54
- Rodegast
-
-
- От: Пятигорск
- Зарегистрирован: 2007-12-28
- Сообщения: 2679
- Репутация:
182
- Профиль Отправить e-mail
Рекурсивный алгоритм Фибоначчи с использованием кэша
ИХМО я бы всё таки предпочёл вариант с хвостовой рекурсией…
def fib(n): def helper(curr, prev, n): if n == 0: return curr return helper(curr+prev, curr, n-1) return helper(0, 1, n)
С дураками и сектантами не спорю, истину не ищу.
Ели кому-то правда не нравится, то заранее извиняюсь.
Ели кому-то правда не нравится, то заранее извиняюсь.
Офлайн
#4 Апрель 1, 2020 23:07:52
- py.user.next
-
-
- От:
- Зарегистрирован: 2010-04-29
- Сообщения: 9726
- Репутация:
843
- Профиль Отправить e-mail
Рекурсивный алгоритм Фибоначчи с использованием кэша
RodegastЭто разные вещи. С кэшированием результат будет выдаваться за O(1) для многих чисел. При повторных запросах код будет работать мнгновенно. А если мы пройдём все числа для n = 1000000 один раз (закэшируем все числа до 1000000-ого), то все числа до 1000000-ого при следующих запросах будут вычисляться за O(1).
я бы всё таки предпочёл вариант с хвостовой рекурсией
Отредактировано py.user.next (Апрель 1, 2020 23:10:05)
Офлайн
#5 Апрель 1, 2020 23:28:00
- Rodegast
-
-
- От: Пятигорск
- Зарегистрирован: 2007-12-28
- Сообщения: 2679
- Репутация:
182
- Профиль Отправить e-mail
Рекурсивный алгоритм Фибоначчи с использованием кэша
> Это разные вещи.
Конечно разные, тем более хвостовая рекурсия на python-е работает так себе…
> А если мы пройдём все числа для n = 1000000 один раз (закэшируем все числа до 1000000-ого), то все числа до 1000000-ого при следующих запросах будут вычисляться за O(1).
А ты представляешь сколько памяти на это уйдёт?
С дураками и сектантами не спорю, истину не ищу.
Ели кому-то правда не нравится, то заранее извиняюсь.
Ели кому-то правда не нравится, то заранее извиняюсь.
Отредактировано Rodegast (Апрель 1, 2020 23:29:31)
Офлайн
#6 Апрель 2, 2020 00:12:42
- py.user.next
-
-
- От:
- Зарегистрирован: 2010-04-29
- Сообщения: 9726
- Репутация:
843
- Профиль Отправить e-mail
Рекурсивный алгоритм Фибоначчи с использованием кэша
RodegastДа и вообще глубина рекурсии ограничена, даже без учёта того, что в питоне хвостовая рекурсия не оптимизируется, как в функциональных языках.
тем более хвостовая рекурсия на python-е работает так себе
Твой код
>>> def fib(n): ... def helper(curr, prev, n): ... if n == 0: ... return curr ... return helper(curr+prev, curr, n-1) ... return helper(0, 1, n) ... >>> fib(1000) Traceback (most recent call last): File "<stdin>", line 1, in <module> File "<stdin>", line 6, in fib File "<stdin>", line 5, in helper File "<stdin>", line 5, in helper File "<stdin>", line 5, in helper [Previous line repeated 993 more times] File "<stdin>", line 3, in helper RecursionError: maximum recursion depth exceeded in comparison >>>
RodegastНемного. 1000000 * 4 байта = 4000000 байт. В 10Mb оперативки поместится всё. Даже если там длинные числа пойдут, в питоне они оптимизируются по мере роста - то есть он не жрёт заранее, а выделяет/запрашивает дополнительную память по необходимости.
А ты представляешь сколько памяти на это уйдёт?
Отредактировано py.user.next (Апрель 2, 2020 00:13:26)
Офлайн
#7 Апрель 2, 2020 00:31:41
- Rodegast
-
-
- От: Пятигорск
- Зарегистрирован: 2007-12-28
- Сообщения: 2679
- Репутация:
182
- Профиль Отправить e-mail
Рекурсивный алгоритм Фибоначчи с использованием кэша
> Да и вообще глубина рекурсии ограничена
Топикстартер пытался решить классическую задачу на оптимизацию древовидной рекурсии. Это в основном теоретический вопрос по этому особенностями реализации я пренебрёг.
> В 10Mb оперативки поместится всё.
Это ты только ключи посчитал, но ряд Фибоначчи быстрорастущий. Посмотри чему равен сто тысячный член этого ряда и посчитай сколько под него памяти уйдёт. Это только одно число лежащее на 1/10 части пути к твоей цели.
Prelude> fib = 1: 1: zipWith (+) fib (tail fib) Prelude> fib !! 100000 42026927029951543863190051012939151317739157026322345033047160871983357314572762 26633938477267013660962533661702858329186641162298822215333733574147268614522205 17796036021657629209679553065650253799831449502633050062071908889898464361959992 64762361083185050237498647038594910246866212417306827361157235516477242575475023 52412468746074851053353923438703547870019701586274514903943581778012410826464461 82327292482674936228295400423592366266785816674032376953223354081043426666167973 88659593046520172457610944955660711670543016908957146048840136794913945664938446 46298912078940644595782507997928878739392985610180101343882600283820398139200927 16351212296992483983946353362236959988059362454831495591998273144066460686038967 47678466307142387985200612209483601958428286948941149568879944075331886216247060 43127847588617179645038305434988777154546903665027721615391983839969917881343981 41944368809250111481819798402261166104607318032292355376603758649849997454020469 37917930479632224861390601474136372303392534432566084857015647848910533979262896 64177821919706286664135844377802876352562122389353466102826235289263234488363199 40415928656082972859882120514749356839216074406481815370670988971910860608364879 55340049728172954655841960826021563040719014933250487378970396127053999994584598 84586324576356850465902800682163360223018811383011208727253121314804106183630746 33391723478815558419942200436973479456746429373159029901632147691027604795314573 71335306209333700132749628766660240923781444622479118612427736288472117262538601 03658427961076487163331347200528488644744897867222184279861410512996912357518380 42022652299635148999201592961336958599228492147284059675182485820608337037517587 06963474517424844808950896189553107994754733303323880745512298961051117039180748 19309463129676526583523254006198015481044159254418528609134434118408385912583154 97972011173508254288351994205020708970629131932370593611869970876740521536649684 57182466406036383021770532848514425324974546309994975775831045210121951158146067 85903295807850171689359081326188293931649613908497264994236206250488864434829436 29519523285183855092352888948498775138102232008825516003364164591409282318882848 54537807547517930489076000255121414706370664025018725479522771414250506214317261 33512376491993264368219026824677798278050012296677681338164667973991346578705512 74534394694404597077719187995407395427605915813079285212741656832828295621599317 46905895821846222133111237435283709695276973766592642097014304602626280895117497 84920754475292453555824485037081169662961361437456685569229108353804447871639780 20232084023609370922254140477009691282049160576777366973036653649883492364824728 35676387541329435959180975529726337169707457248356090428023225272687222700646793 84555006784008088065427716480324882491803961614497071569285030997191355977454006 78466656398246586364144439671724823401802624396178170648336037171760595399177104 54961305646287727491308779554338932431913693952814138123950135908078982276584882 63250802618524850762756185439484575939335126157545942937679620715509540065149312 86556444370865543977167354218105455845369761896615555180417133010674271473743311 86161116668001347423577154956442088220552625312076302475402749012976651613308330 84658587180009012735858860387323290477368590430709381480698925172403629520614399 57593715175787053504534026486718715408551576929967042586501209349749945808407148 38200915888065735389239137040243506196571510983480529860982551109754928853361155 45257393042442696791158576341900753200960006019671663122779964553274124613827002 84220765144312721590741133408003489040762584919284658858041286916386515479642977 63251242652433570903732799940906080289143242002162784031375696887933193271792815 13651857484816495100553151506872893457040698364864908926339042055054701374510871 32493449799940863749770127971602810605646534257761336751184475785823961876512808 94724868512789750831935081098377719941036701024841296638857887680535961230332515 79123980971589651437698106274532939294318318049638382537268302829198532880152940 71433723208632110406164435835438266486491721843821029351742455374550575809075335 58820252056024537843175435538531994250810021714312797654628419286910387394477602 77789370517385306279744047722489086714748028855582994177874607142469064610509456 25202212825832995025564260229990592904684159579116792151285886032829684995127155 34465088782963276118039067356332662241230936875737466342521351706796949812896179 44100773168818654945023743438512318640838968116604957523873700674044602618648483 42534348017257039340592723838919220589031998906185198421038308216416528610206873 86947447622822706715620808975672807761093212837007765365923625213701756104920104 90647926435022313362357037672820456385127428485063107497131400081807697966418670 92086270751758290904938302420460333404925465658358444295296337088776545265587606 60624469378326102878234267050061871258419093201617639875665134869271540100850836 47269535513915816758710288791204561224527095476616464634423436358506846144301437 37965771779082950287449625309471674027094862405581741465010467062797651780375495 58990882669374665017899340941580175877931297764268912428095816679869262328136255 76760050205090619888399123409239688442164270550778132287725184933490420599495679 26460565911025776082501419307787196588096224965245820155681523746669946396754909 27159042795674347394047138884034570033397714655556949471950710357752508118665325 75065892797554153301608090613307672021657715401873436452152566925919864525536834 56823553070598162130085504904574946212500558610031219155224527412244517230546007 64895687440378116371204889424814424573838812216469939212301308229376562195148119 87478059283006119165854697271444230766548407257874820601218362249866393721509747 52653753967735395851984476957732214244609798081017294862506075465564785057434857 46737609236566345826554956945008049466256006830033039697919727289785487728986917 00233344838111143624421997248348373393817914540838366741137930672543630607318584 21388931047329746129464330913406615122087253374620231774863799904011403703504128 61126902647363933972738179243157455031071860290464651684896649914849558362752102 78398095989067353453771747035442365355445747127447923214040603969451728451202645 05187739366087820740427979492937157133826232579378916797946108593141509568348629 61624018757558941301204073786717124377291884875201219129108103267491540960406487 54248927534521962074102425291913766944369032132103550933382245399558387757904745 51175896508802785493729953647184656663763691900135139867974638850946840528454914 07564794860564579206494296178297419619461097036293045309134667162384421488201894 49581503029766353579703388699920365905324047373120549655643341862622777074389646 42317957967457795634132283078491602681354845462336294905591488533788039843697491 80713360895800201231109916145561278971286295284582090679521943269768969977521270 42336429246818734853834742889330980560103357922288676566480206614652444443461774 01172126439820562310243124840816832768854775304579417636166590305855258136611924 90196991628024964540860533212750628406233981730540193987593512157119873066361784 10283089779146732418239902330676994111916249584184821290161741884890744574259103 28510676894545629386475573889945635494325985390253311832043111393820576601242222 31752954406599632778548648529847420831796113142908575604057107282129589064023059 31907418946110255773607562277250486349227222087557966804673075308805002278223894 68361402870663902607934434443468629455639610312381813698122879437078536838850659 91350269806133309340949617935630946271998532016131931538651084527217868141405865 72232010017459153962501788701203805098164119780148853692024087086122573636233064 50225196123397499236664073545189104486279946218881558204238658003080110689009723 86870554525521108299650591612453434151610083544316269170638441165491024969938807 62448490819042269804160074405392450174036209847483710949092804116773547479425117 69672357617318954766059698481314304490693914473657202511253091340235031657959272 71071402047457921813126432679801662762135397873186867845166464090437394613410583 41866130194515206728071388017201750465345177683567166246451096874716792230890148 54973165171542671913470177900964650371385571369061497989488994188845729728287595 44639035990951487082060585723385141586276742411497951540241559999383864723301215 96245377182900950030617269384713599791193454044355416529598060101173170994161856 36155026578712336935553259632328638430930540914525165204987654129894537133171429 73795506682394318732826782930749552668645632087437685400955163673119855585200028 73697087726788222240830142818294228089082545681401285437906803150262330031355435 70841106156839051943858493032597840600258361327454785141649585558622625225336032 16747669816204218273393852065937390968852527871454061426726582621775736550483282 67368597269217457845651924361951505134294767813855422501312640796469744649758696 32268016274093312319995315408701199104881239311172712335296437902042142058375699 48496127668188943766970732405110648037171462582288856768332108587026035298465103 70844972539194851074168242379857338076991793231848897846533495471513960873594311 48393232317497136900767515061983191875262963294069878067300582894318636140853643 35451825136217333664699343258603359016092928350443561955601519525359038386696329 31421195319086416029491768186604338108617856893658652762599159576463089057484057 01242187456118336915674440027198999385943524260688231230651990539334501570243909 32025557083058294784881683034322962702271781103413203729868628557061538361925527 48513974514717282608166467373122237687789655395096239211535388318181125900905930 70376552101723383095658510347162234372147094523951238317789818036805766053708172 39599449395445110073949600866063140073697268098603531480280356391792592955140355 56750901346225565651200500040388964695765286839375894326641359638758981952190977 23309263619292928688427150600953821721493379274424742114989752222918515704297822 77193409751093199688272829280004463814753806133897251199573509599044511222734399 71539673040298002820751768235827912095052102735663217352194962362184727464644960 22614998175190835220330634202159205072059879503523922819586916515854244992947454 81066050501176252069723509637020197526019852606773842218965246052998549299953387 55313295340940138314907468467139499677720572636120372107374342868057717426582051 29408096995956353191128273999009796053960798443752311650773471977780957043388364 52702396442943094663156239040132517321657829215338301025580139371525988563293477 55255719232808344589151922043864806081186297548489573356845798244178775602686253 78421607331592631511700654666479296482728874240118029558447112869542529777925384 16064059274273135088608366963956793552430262618868857520064817604977259611300739 22590764478449738830065772275665777414636443696093953753681025203011970464541713 41193397573510378873839276937556550684521053667831828394540040197553472129245038 33360038173856789212817138027497902255432743261724438443835191659279500017136825 36758546723469033733698464059513247716076530428565235979898018682260049948150428 79710747667645929446038640988204665343974190422108476050665162566607895047007370 03648782684878109437041237808208672032110279836373360905865438186029749287811554 84266146415144583159391700957591524192858746462325799289808212663991897979203096 51377003004333255996575709580488051628031829131789228353961180609648076058832439 88338519278712663084374366551964511408009362478522630426303332530214226362339535 58646545567952000386740056413841503316500443196882791862089512040487190834318318 72080561388048272209950449676983025946244664338734008755934808078312171484872268 53377022052608080382561296537121309281428683267320245473419184095432657707518460 27970701058154304742603541295214529990635988000113171975043316669542398374118000 58621274994165791632889639236400118340323406940428738845184765282641012203360562 43231216355689759863697496475965028711885857843551016875046246365393245524901540 32140569865547304245954636331164655521637183906414415309758712816906121425865963 51957297792242219399863533387281631677532938288828538833763223323803664508949987 47380600574088983607539281237219292218879353578281400690656347782028875078818132 40782624394992260288324899145727374030782190991736334686587324734925180822573968 05457081246116499538396552745369148734095263017756736493650310504001208373332350 76971527125231473234337159823811549829020925243269810853721487178387223628469680 85831693638384498765389697888945985515666277324765372113023407091352370001332816 56929327690078147107864309790657844779317896054314320502445959789408721143382595 72590506761140837775776669498790344984236168335654576420399106184536189357501017 10017725620355769563378953758665795785319349166712506777600201116719824482067962 13821363747999607838894747697685437117948202138934986118174082899084739771156621 95757301667695316163900286164377443339879504659246496242213615825569797905454982 20365919158604912020715635631040315538986628041330966376721410914045182032024057 16711882043446479392874980381935293814505434327576436725219530094774825624593141 79226051370176894023642476014898319812498818156593637676255006576938058747631406 15448155779212535276526235730433689192685254054526262411911016156357795666960065 90853227700270327518712187717125280345612683023510166754512475487713377371667955 14204267034673510427911733846292378010277610416833716861842537265620375137328435 33633565163220145118782869823125951421106201364541930300041723532889519178318955 85653089961841403637276624261346298183236671851622761292906447484264267072022835 16846142659205167622312078308287364956747531477318280956792509574551832086407200 34073280476977250429065166775862662137940822216639672500136596904942830895605490 95125596898792210177465881794877434523159035852603218330966709911258339348544848 72478489899865551061633892866899967002254557252011924689633992453419305686282872 66154554977591171677234870273109994284553066290629230944606505961324859550418277 93867266851956463510407861783979941387203353282784319564570900789300894702792354 81051844018217279975760679807456846030015081389234525021050449348741464717225649 95367164821236866037139904194334377622398866638519217567726283183853832672567439 80731998946648066449320332566724813016944238626026093859526218547382982965566416 72390560973523741831071952650956837956707426467406838497344751696859357892196424 16124979114398039590666990374976005078576331036100207225998255550662603112543323 69339553635821828983112217091453159478031106795275744064049680687878041449978932 31124540042356279079504960535323207987979466036248168633614842978382950383300964 30888224575734937428832687311310335645328966004829358961398637161232521561088632 56469920665387383737829382390201767226240379323264372364963657655017444240199111 26611218540395116166122909793543509424966821481768867615199335393023759742682952 07970549690201597108189357323757477303432824688714733897849865805712867879245604 61867732757210410139280459460173494645119897670695402692632597708541191901569104 59955522073512931381871614054990849095548454194349319173444305223764693922634033 92646510051744603644570754463847534733966705557908398431759668907930084657438598 56191266312471770395539000662450582533036177906455933427415574329754738243585168 75582912889347240535707134454582229719337307582058971444728890897813407541481107 31186122936859973310507122731462503393873897738479354688284953678332216656064611 03660656659313231195501369485113843929121156157449854781600361895540962234461692 79799494846566361483306991738295501446560634290373595759154695585272538607318024 99652816768425443425889739073884352974610591022393415807247569583300801154557691 63437623074819008751508360426714659037680679317715318450944455507821880437147901 72540487375906234143811810917779958944528511109543124510076618842367399621924560 77969511122779364407990415119514440661546965008576217977093190909583132987787434 52216525503444540470276316971436876246962004325852200335643684869288291617928781 91424334756547562872261243516643436919624897569681514147278887655349776980064808 71154761766945959111922927429454384882497333914219571616022292224906364296597972 09954719580002503674675489465028006455603137064421741963422783187804694280404749 97992506784403449261707810186526891856005592894784356202305065620907983327840544 09933754325466268996342381853087817159138132409688240004900823384875229448700461 03538188341821701517877946850334629894168308089935790820340259698157101915212432 25991422979939610174887978878302811921912387279223536232950340970470263845769505 18160676657044486620981891268715888390683926816266566045504069411325517726301593 00546811862531404117654625414748495420965521832926255083589672181163544183138871 06850401706146847688741355892485349512361859014754597989781338167841349892570213 73591925918938505117120958353354468195902418584460471378852709468342796348047587 15657341569089644452539579525183759731421602968163841208815303609996699618863979 50418069721702975326127703724221774423997578607522442757679906248991213404964748 89285918528422833247118694861120447658840271122911279114792252504327153033684366 57815017282187860553032029987958807921737926332546835292644208515314637982132209 31207970351120946260710073027789120725667430842849492024054503917506431210785770 65441187219944044713259661653295743027549410956701543326099389775148130009541828 40265129893522776019998300410614171832108019578950379045932608127678813899473832 42275125648493412865310710528686896486440352946198326392195175992621585678533081 80854622517432057724041779265437756658172231185312218755767693801703046218276691 46776225014475875461514451431825592306694306260373264656836355532616033171543753 53243493742242509676699722095691829203992217797492440679265480059106156747895005 42998017635444037775787063172034013555643683051468017023738859881563516237835944 67435566276013514967430144042041517192887237464786738278197182703598388603661618 73572627004933423492861172405062282751212754815542642284715217354971458024738147 76450360970418983518376319628772221549149786891339743058279126510663209664415284 38054008727568992633244723009447752915292844413484286782907212369432924242088360 43639506055067587721243141027286052838756138481024065262572477129997756946435000 56233401552208865282718695548243000376564479084893901000536841057522363280370838 89749667549341111989628841343764816576275551624938581979987619059341059658877295 37505921354802824063847997251499460206485037420745024330993731647827119117031718 78502492156281762509092095744129027049665089185824440951849086836244861302746209 63475379322631881671526110781260732811062011534497765815730498778677382754501731 65896627327221710231020444689102004159483035267539082000099323700359160202697273 58967287596800092431351089975959771739670737705545635339787762830709652643567870 59183966640117154025620422828106006794410917965394168536500527272432453699734511 55161758421415997019097554830734246349425709110977253628963700518310446086702859 04915489785451861640485967121832187912603224446865674572002909630090732796419381 08736830057700848854987632642420122577561135179211206970609858480637530014330320 62979008560113174534602168985499355344812429007061967707035833467717189296096500 46081906453813744649270388930650195618060462577300950622064469234834931163196871 83946068823139940561499289688955368854442601597891759488522130483332037888265615 58879638240876906542931930466777690810720489086401931338095243898717372372530055 21747524415947922113766652805888438396054147567486987337167355166104543042899131 99343082099165015964765620845632436308178171260221701634777556411144180359219308 84712892557953936428778244536540481659503232237881780602859055827000867386848837 50337714980917164444693060308390225962379946272713289768929936724536553233482465 79421273402707056538851193621576265629886468443537082357184808424713839752577831 01287855534457080267659017382060818735190509984996309659107934323668138539702028 21394949406134489952453908830903545787795663963353463066176422602202105775621923 78195749462971643681534921085707270631642732845357749851399463715941895372082676 71471332050925700993356729526111636280008058244097546017085175764114440793957202 15248444116421555957828748745424226011844865906715664110802868290518210612860404 45475051143892254443914386819488133792825449371700396553390063464483310103727144 67523577242603511656995157739676429135726375358735016704706133125274508475052133 59793783861950188821929180325547521785176580032177426333023524832481849348447808 43978821871354242752913348569007762571896695622806296616834700668021294259786170 53012186479789473981352503000050801790270455187977935052946992108027883296491603 85012184940049568696199707027524548531041667993720684674742262714439058761479088 89584182416037374890870011281786063162415194429057278667097563530351860359404758 76975995200481698513044618610349811851333859033663164211875013087748158706762287 49311300865732973446153743975659991079304994892588234011350360387511421993302025 04777680857549981006888716078773295305011124146554797633463693155111583435711003 8285979669707537501
С дураками и сектантами не спорю, истину не ищу.
Ели кому-то правда не нравится, то заранее извиняюсь.
Ели кому-то правда не нравится, то заранее извиняюсь.
Отредактировано Rodegast (Апрель 2, 2020 00:54:27)
Офлайн
#8 Апрель 2, 2020 01:09:43
- py.user.next
-
-
- От:
- Зарегистрирован: 2010-04-29
- Сообщения: 9726
- Репутация:
843
- Профиль Отправить e-mail
Рекурсивный алгоритм Фибоначчи с использованием кэша
>>> import sys >>> >>> n = 4202692702995154386319005101293915131773915702632234503304716087198335731457276226633938477267013660962533661702858329186641162298822215333733574147268614522205177960360216576292096795530656502537998314495026330500620719088898984643619599926476236108318505023749864703859491024686621241730682736115723551647724257547502352412468746074851053353923438703547870019701586274514903943581778012410826464461823272924826749362282954004235923662667858166740323769532233540810434266661679738865959304652017245761094495566071167054301690895714604884013679491394566493844646298912078940644595782507997928878739392985610180101343882600283820398139200927163512122969924839839463533622369599880593624548314955919982731440664606860389674767846630714238798520061220948360195842828694894114956887994407533188621624706043127847588617179645038305434988777154546903665027721615391983839969917881343981419443688092501114818197984022611661046073180322923553766037586498499974540204693791793047963222486139060147413637230339253443256608485701564784891053397926289664177821919706286664135844377802876352562122389353466102826235289263234488363199404159286560829728598821205147493568392160744064818153706709889719108606083648795534004972817295465584196082602156304071901493325048737897039612705399999458459884586324576356850465902800682163360223018811383011208727253121314804106183630746333917234788155584199422004369734794567464293731590299016321476910276047953145737133530620933370013274962876666024092378144462247911861242773628847211726253860103658427961076487163331347200528488644744897867222184279861410512996912357518380420226522996351489992015929613369585992284921472840596751824858206083370375175870696347451742484480895089618955310799475473330332388074551229896105111703918074819309463129676526583523254006198015481044159254418528609134434118408385912583154979720111735082542883519942050207089706291319323705936118699708767405215366496845718246640603638302177053284851442532497454630999497577583104521012195115814606785903295807850171689359081326188293931649613908497264994236206250488864434829436295195232851838550923528889484987751381022320088255160033641645914092823188828485453780754751793048907600025512141470637066402501872547952277141425050621431726133512376491993264368219026824677798278050012296677681338164667973991346578705512745343946944045970777191879954073954276059158130792852127416568328282956215993174690589582184622213311123743528370969527697376659264209701430460262628089511749784920754475292453555824485037081169662961361437456685569229108353804447871639780202320840236093709222541404770096912820491605767773669730366536498834923648247283567638754132943595918097552972633716970745724835609042802322527268722270064679384555006784008088065427716480324882491803961614497071569285030997191355977454006784666563982465863641444396717248234018026243961781706483360371717605953991771045496130564628772749130877955433893243191369395281413812395013590807898227658488263250802618524850762756185439484575939335126157545942937679620715509540065149312865564443708655439771673542181054558453697618966155551804171330106742714737433118616111666800134742357715495644208822055262531207630247540274901297665161330833084658587180009012735858860387323290477368590430709381480698925172403629520614399575937151757870535045340264867187154085515769299670425865012093497499458084071483820091588806573538923913704024350619657151098348052986098255110975492885336115545257393042442696791158576341900753200960006019671663122779964553274124613827002842207651443127215907411334080034890407625849192846588580412869163865154796429776325124265243357090373279994090608028914324200216278403137569688793319327179281513651857484816495100553151506872893457040698364864908926339042055054701374510871324934497999408637497701279716028106056465342577613367511844757858239618765128089472486851278975083193508109837771994103670102484129663885788768053596123033251579123980971589651437698106274532939294318318049638382537268302829198532880152940714337232086321104061644358354382664864917218438210293517424553745505758090753355882025205602453784317543553853199425081002171431279765462841928691038739447760277789370517385306279744047722489086714748028855582994177874607142469064610509456252022128258329950255642602299905929046841595791167921512858860328296849951271553446508878296327611803906735633266224123093687573746634252135170679694981289617944100773168818654945023743438512318640838968116604957523873700674044602618648483425343480172570393405927238389192205890319989061851984210383082164165286102068738694744762282270671562080897567280776109321283700776536592362521370175610492010490647926435022313362357037672820456385127428485063107497131400081807697966418670920862707517582909049383024204603334049254656583584442952963370887765452655876066062446937832610287823426705006187125841909320161763987566513486927154010085083647269535513915816758710288791204561224527095476616464634423436358506846144301437379657717790829502874496253094716740270948624055817414650104670627976517803754955899088266937466501789934094158017587793129776426891242809581667986926232813625576760050205090619888399123409239688442164270550778132287725184933490420599495679264605659110257760825014193077871965880962249652458201556815237466699463967549092715904279567434739404713888403457003339771465555694947195071035775250811866532575065892797554153301608090613307672021657715401873436452152566925919864525536834568235530705981621300855049045749462125005586100312191552245274122445172305460076489568744037811637120488942481442457383881221646993921230130822937656219514811987478059283006119165854697271444230766548407257874820601218362249866393721509747526537539677353958519844769577322142446097980810172948625060754655647850574348574673760923656634582655495694500804946625600683003303969791972728978548772898691700233344838111143624421997248348373393817914540838366741137930672543630607318584213889310473297461294643309134066151220872533746202317748637999040114037035041286112690264736393397273817924315745503107186029046465168489664991484955836275210278398095989067353453771747035442365355445747127447923214040603969451728451202645051877393660878207404279794929371571338262325793789167979461085931415095683486296162401875755894130120407378671712437729188487520121912910810326749154096040648754248927534521962074102425291913766944369032132103550933382245399558387757904745511758965088027854937299536471846566637636919001351398679746388509468405284549140756479486056457920649429617829741961946109703629304530913466716238442148820189449581503029766353579703388699920365905324047373120549655643341862622777074389646423179579674577956341322830784916026813548454623362949055914885337880398436974918071336089580020123110991614556127897128629528458209067952194326976896997752127042336429246818734853834742889330980560103357922288676566480206614652444443461774011721264398205623102431248408168327688547753045794176361665903058552581366119249019699162802496454086053321275062840623398173054019398759351215711987306636178410283089779146732418239902330676994111916249584184821290161741884890744574259103285106768945456293864755738899456354943259853902533118320431113938205766012422223175295440659963277854864852984742083179611314290857560405710728212958906402305931907418946110255773607562277250486349227222087557966804673075308805002278223894683614028706639026079344344434686294556396103123818136981228794370785368388506599135026980613330934094961793563094627199853201613193153865108452721786814140586572232010017459153962501788701203805098164119780148853692024087086122573636233064502251961233974992366640735451891044862799462188815582042386580030801106890097238687055452552110829965059161245343415161008354431626917063844116549102496993880762448490819042269804160074405392450174036209847483710949092804116773547479425117696723576173189547660596984813143044906939144736572025112530913402350316579592727107140204745792181312643267980166276213539787318686784516646409043739461341058341866130194515206728071388017201750465345177683567166246451096874716792230890148549731651715426719134701779009646503713855713690614979894889941888457297282875954463903599095148708206058572338514158627674241149795154024155999938386472330121596245377182900950030617269384713599791193454044355416529598060101173170994161856361550265787123369355532596323286384309305409145251652049876541298945371331714297379550668239431873282678293074955266864563208743768540095516367311985558520002873697087726788222240830142818294228089082545681401285437906803150262330031355435708411061568390519438584930325978406002583613274547851416495855586226252253360321674766981620421827339385206593739096885252787145406142672658262177573655048328267368597269217457845651924361951505134294767813855422501312640796469744649758696322680162740933123199953154087011991048812393111727123352964379020421420583756994849612766818894376697073240511064803717146258228885676833210858702603529846510370844972539194851074168242379857338076991793231848897846533495471513960873594311483932323174971369007675150619831918752629632940698780673005828943186361408536433545182513621733366469934325860335901609292835044356195560151952535903838669632931421195319086416029491768186604338108617856893658652762599159576463089057484057012421874561183369156744400271989993859435242606882312306519905393345015702439093202555708305829478488168303432296270227178110341320372986862855706153836192552748513974514717282608166467373122237687789655395096239211535388318181125900905930703765521017233830956585103471622343721470945239512383177898180368057660537081723959944939544511007394960086606314007369726809860353148028035639179259295514035556750901346225565651200500040388964695765286839375894326641359638758981952190977233092636192929286884271506009538217214933792744247421149897522229185157042978227719340975109319968827282928000446381475380613389725119957350959904451122273439971539673040298002820751768235827912095052102735663217352194962362184727464644960226149981751908352203306342021592050720598795035239228195869165158542449929474548106605050117625206972350963702019752601985260677384221896524605299854929995338755313295340940138314907468467139499677720572636120372107374342868057717426582051294080969959563531911282739990097960539607984437523116507734719777809570433883645270239644294309466315623904013251732165782921533830102558013937152598856329347755255719232808344589151922043864806081186297548489573356845798244178775602686253784216073315926315117006546664792964827288742401180295584471128695425297779253841606405927427313508860836696395679355243026261886885752006481760497725961130073922590764478449738830065772275665777414636443696093953753681025203011970464541713411933975735103788738392769375565506845210536678318283945400401975534721292450383336003817385678921281713802749790225543274326172443844383519165927950001713682536758546723469033733698464059513247716076530428565235979898018682260049948150428797107476676459294460386409882046653439741904221084760506651625666078950470073700364878268487810943704123780820867203211027983637336090586543818602974928781155484266146415144583159391700957591524192858746462325799289808212663991897979203096513770030043332559965757095804880516280318291317892283539611806096480760588324398833851927871266308437436655196451140800936247852263042630333253021422636233953558646545567952000386740056413841503316500443196882791862089512040487190834318318720805613880482722099504496769830259462446643387340087559348080783121714848722685337702205260808038256129653712130928142868326732024547341918409543265770751846027970701058154304742603541295214529990635988000113171975043316669542398374118000586212749941657916328896392364001183403234069404287388451847652826410122033605624323121635568975986369749647596502871188585784355101687504624636539324552490154032140569865547304245954636331164655521637183906414415309758712816906121425865963519572977922422193998635333872816316775329382888285388337632233238036645089499874738060057408898360753928123721929221887935357828140069065634778202887507881813240782624394992260288324899145727374030782190991736334686587324734925180822573968054570812461164995383965527453691487340952630177567364936503105040012083733323507697152712523147323433715982381154982902092524326981085372148717838722362846968085831693638384498765389697888945985515666277324765372113023407091352370001332816569293276900781471078643097906578447793178960543143205024459597894087211433825957259050676114083777577666949879034498423616833565457642039910618453618935750101710017725620355769563378953758665795785319349166712506777600201116719824482067962138213637479996078388947476976854371179482021389349861181740828990847397711566219575730166769531616390028616437744333987950465924649624221361582556979790545498220365919158604912020715635631040315538986628041330966376721410914045182032024057167118820434464793928749803819352938145054343275764367252195300947748256245931417922605137017689402364247601489831981249881815659363767625500657693805874763140615448155779212535276526235730433689192685254054526262411911016156357795666960065908532277002703275187121877171252803456126830235101667545124754877133773716679551420426703467351042791173384629237801027761041683371686184253726562037513732843533633565163220145118782869823125951421106201364541930300041723532889519178318955856530899618414036372766242613462981832366718516227612929064474842642670720228351684614265920516762231207830828736495674753147731828095679250957455183208640720034073280476977250429065166775862662137940822216639672500136596904942830895605490951255968987922101774658817948774345231590358526032183309667099112583393485448487247848989986555106163389286689996700225455725201192468963399245341930568628287266154554977591171677234870273109994284553066290629230944606505961324859550418277938672668519564635104078617839799413872033532827843195645709007893008947027923548105184401821727997576067980745684603001508138923452502105044934874146471722564995367164821236866037139904194334377622398866638519217567726283183853832672567439807319989466480664493203325667248130169442386260260938595262185473829829655664167239056097352374183107195265095683795670742646740683849734475169685935789219642416124979114398039590666990374976005078576331036100207225998255550662603112543323693395536358218289831122170914531594780311067952757440640496806878780414499789323112454004235627907950496053532320798797946603624816863361484297838295038330096430888224575734937428832687311310335645328966004829358961398637161232521561088632564699206653873837378293823902017672262403793232643723649636576550174442401991112661121854039511616612290979354350942496682148176886761519933539302375974268295207970549690201597108189357323757477303432824688714733897849865805712867879245604618677327572104101392804594601734946451198976706954026926325977085411919015691045995552207351293138187161405499084909554845419434931917344430522376469392263403392646510051744603644570754463847534733966705557908398431759668907930084657438598561912663124717703955390006624505825330361779064559334274155743297547382435851687558291288934724053570713445458222971933730758205897144472889089781340754148110731186122936859973310507122731462503393873897738479354688284953678332216656064611036606566593132311955013694851138439291211561574498547816003618955409622344616927979949484656636148330699173829550144656063429037359575915469558527253860731802499652816768425443425889739073884352974610591022393415807247569583300801154557691634376230748190087515083604267146590376806793177153184509444555078218804371479017254048737590623414381181091777995894452851110954312451007661884236739962192456077969511122779364407990415119514440661546965008576217977093190909583132987787434522165255034445404702763169714368762469620043258522003356436848692882916179287819142433475654756287226124351664343691962489756968151414727888765534977698006480871154761766945959111922927429454384882497333914219571616022292224906364296597972099547195800025036746754894650280064556031370644217419634227831878046942804047499799250678440344926170781018652689185600559289478435620230506562090798332784054409933754325466268996342381853087817159138132409688240004900823384875229448700461035381883418217015178779468503346298941683080899357908203402596981571019152124322599142297993961017488797887830281192191238727922353623295034097047026384576950518160676657044486620981891268715888390683926816266566045504069411325517726301593005468118625314041176546254147484954209655218329262550835896721811635441831388710685040170614684768874135589248534951236185901475459798978133816784134989257021373591925918938505117120958353354468195902418584460471378852709468342796348047587156573415690896444525395795251837597314216029681638412088153036099966996188639795041806972170297532612770372422177442399757860752244275767990624899121340496474889285918528422833247118694861120447658840271122911279114792252504327153033684366578150172821878605530320299879588079217379263325468352926442085153146379821322093120797035112094626071007302778912072566743084284949202405450391750643121078577065441187219944044713259661653295743027549410956701543326099389775148130009541828402651298935227760199983004106141718321080195789503790459326081276788138994738324227512564849341286531071052868689648644035294619832639219517599262158567853308180854622517432057724041779265437756658172231185312218755767693801703046218276691467762250144758754615144514318255923066943062603732646568363555326160331715437535324349374224250967669972209569182920399221779749244067926548005910615674789500542998017635444037775787063172034013555643683051468017023738859881563516237835944674355662760135149674301440420415171928872374647867382781971827035983886036616187357262700493342349286117240506228275121275481554264228471521735497145802473814776450360970418983518376319628772221549149786891339743058279126510663209664415284380540087275689926332447230094477529152928444134842867829072123694329242420883604363950605506758772124314102728605283875613848102406526257247712999775694643500056233401552208865282718695548243000376564479084893901000536841057522363280370838897496675493411119896288413437648165762755516249385819799876190593410596588772953750592135480282406384799725149946020648503742074502433099373164782711911703171878502492156281762509092095744129027049665089185824440951849086836244861302746209634753793226318816715261107812607328110620115344977658157304987786773827545017316589662732722171023102044468910200415948303526753908200009932370035916020269727358967287596800092431351089975959771739670737705545635339787762830709652643567870591839666401171540256204228281060067944109179653941685365005272724324536997345115516175842141599701909755483073424634942570911097725362896370051831044608670285904915489785451861640485967121832187912603224446865674572002909630090732796419381087368300577008488549876326424201225775611351792112069706098584806375300143303206297900856011317453460216898549935534481242900706196770703583346771718929609650046081906453813744649270388930650195618060462577300950622064469234834931163196871839460688231399405614992896889553688544426015978917594885221304833320378882656155887963824087690654293193046677769081072048908640193133809524389871737237253005521747524415947922113766652805888438396054147567486987337167355166104543042899131993430820991650159647656208456324363081781712602217016347775564111441803592193088471289255795393642877824453654048165950323223788178060285905582700086738684883750337714980917164444693060308390225962379946272713289768929936724536553233482465794212734027070565388511936215762656298864684435370823571848084247138397525778310128785553445708026765901738206081873519050998499630965910793432366813853970202821394949406134489952453908830903545787795663963353463066176422602202105775621923781957494629716436815349210857072706316427328453577498513994637159418953720826767147133205092570099335672952611163628000805824409754601708517576411444079395720215248444116421555957828748745424226011844865906715664110802868290518210612860404454750511438922544439143868194881337928254493717003965533900634644833101037271446752357724260351165699515773967642913572637535873501670470613312527450847505213359793783861950188821929180325547521785176580032177426333023524832481849348447808439788218713542427529133485690077625718966956228062966168347006680212942597861705301218647978947398135250300005080179027045518797793505294699210802788329649160385012184940049568696199707027524548531041667993720684674742262714439058761479088895841824160373748908700112817860631624151944290572786670975635303518603594047587697599520048169851304461861034981185133385903366316421187501308774815870676228749311300865732973446153743975659991079304994892588234011350360387511421993302025047776808575499810068887160787732953050111241465547976334636931551115834357110038285979669707537501 >>> >>> sys.getsizeof(1) 28 >>> sys.getsizeof(n) 9284 >>>
Умножаем число на 10000 байт на миллион
>>> 10000 * 1000000 10000000000 >>> 10000000000 / 1048576 9536.7431640625 >>>
Отредактировано py.user.next (Апрель 2, 2020 01:13:45)
Офлайн
#9 Апрель 2, 2020 01:36:05
- Rodegast
-
-
- От: Пятигорск
- Зарегистрирован: 2007-12-28
- Сообщения: 2679
- Репутация:
182
- Профиль Отправить e-mail
Рекурсивный алгоритм Фибоначчи с использованием кэша
> Умножаем число на 10000 байт на миллион
Не всё так хорошо. Ряд постоянно растёт и например его 200000 член будет примерно в двое длиннее 100000-ого. По этому 10 ГиБ тебе точно не хватит 
С дураками и сектантами не спорю, истину не ищу.
Ели кому-то правда не нравится, то заранее извиняюсь.
Ели кому-то правда не нравится, то заранее извиняюсь.
Отредактировано Rodegast (Апрель 2, 2020 01:36:52)
Офлайн
- Начало
- » Python для новичков
-
» Рекурсивный алгоритм Фибоначчи с использованием кэша