You might have noticed that up here on the right, I made a very simple chart
to try and explain how Fibonacci behaves to myself.
We're going to use this same sort of chart to make Fibonacci much faster
by voiding repeating a lot of work.
Our official plan for this is going to be called Memoization.
It's just like memorization, but missing an r.
Here I've tried to draw 2 memos: a corporate memo and those yellow sticky notes
you sometimes see, where you could write a little memo to yourself.
A memo in English is just a document, a small document, that's written down--
memorandom.
Why bother with this?
Well, it's going to turn out that our current implementation of Fibonacci is super slow.
Let me try to prove that to you.
So let's see how long it takes to do 100 trials of the 20th Fibonacci number--
about .3 seconds.
Let's up that a bit to the 24th Fibonacci number--
should take not that much longer, right?
Oh! Significantly longer, from .3 seconds to 1.75 seconds.
We went up a huge amount.
Let's go up to the 25th Fibonacci number--oh! We almost doubled.
We're now at about 2.8 seconds.
In fact, we have reason to believe based on human studies
that if a webpage takes longer than 6 seconds to get back to you,
you go somewhere else and buy something different online.
So we're already using up a huge fraction of that budjet just to compute
the 25th Fibonacci number.
And if you think about those trees I drew before, this is unsurprising.
If we increase the number by 1, we almost double the work at each step.
So this is untenable. We need something faster.
Our solution we'll be to write it down in a chart, or a little memo, to ourselves.
I'll just make a table mapping N to the value of Fibonacci of N.
1, 1, 2, 3, 5, 8.
And when I'm going to figure these out, I don't have to do a huge amount of work.
Let's say I'm trying to figure out this 6th Fibonacci number.
I can just look back in the table, and reuse my old work.
I don't need to recompute the 5th Fibonacci number. I already have it here.
Just additional those 2 chart cells together and get the answer.
This is going to be our trick for making Fibonacci so much faster.
It's called memoization.
So we can implement our chart as a Python dictionary,
just filling in the numbers as we compute them.
So I can make an empty dictionary, assign mappings to my dictionary,
and then check to see if something like 6 is recorded in my chart,
and if it is, print out the result.
This is going to be super necessary now and maybe it wasn't before.
One of the keys to memoization is looking to see if you've already done the work
and written it down.
If you have, great! You can just reuse it.
But if you haven't, you're going to have to go and compute it manually the first time.
画面右部分に簡単な表を作りました
フィボナッチ数列の計算を理解するためです
このように表を使いフィボナッチ数列を
より速く計算し
繰り返しの計算を省きましょう
このような方法は正式にはメモ化と呼ばれています
スペルはMemorizationからrを取ります
ビジネスで使われるメモと
黄色い付箋タイプのメモの2種類を描きました
自分のためにメモを書く時がありますよね
メモとは書きとめられた小さな文書という意味です
覚え書きとも言われます
なぜこれを使うのでしょう?
今のfibo関数の実装はとても遅いです
今からお見せしましょう
20番目のフィボナッチ数を
100回計算するのにかかる時間は
約0.3秒です
24番目の数はどうでしょう?
変わらないと思いますよね?
0.3秒から1.75秒と大きな違いが出ました
かなり差があります
25番目の場合は約2倍の時間がかかりました
2.8秒もかかってしまいました
ある研究によると
Webページを表示するのに6秒以上かかると
別のページに移ってしまうことが多いそうです
これでは限られた時間の大半をフィボナッチ数の
計算に費やしてしまっています
先ほど書いた図を思い出してほしいのですが
Nを1増やしただけで各段階の計算が
2倍に増えていましたね
これでは使えませんのでもっと速い処理が必要です
そのためには自分たちのために
表やメモを書くことが大事です
Nからfibo(N)の値への対応表を作ります
1、1、2、3、5、8
これがあれば数を知りたい時
いちいち計算せずに済みます
6番目のフィボナッチ数を知るには
この表を参照すればいいのです
あの何度も繰り返す計算をしなくても
5番目のフィボナッチ数はここに記載されています
この2つのセルから答えを出すことができます
これでフィボナッチ数の計算を速くできます
メモ化と呼ばれています
表はPythonの辞書で実装できます
計算する度に数で表を埋めていきます
空の辞書のなかにマッピングをしていきます
まずは6の数があるかどうかを調べ
その数がある場合は
すぐに結果を出力します
この技術はこれからとても重要になっていきます
メモ化の大事なポイントは
前に行った計算が記録されているか
調べるということです
記録があれば再利用できます
記録がなければ
自身で計算する必要があります
Você deve ter notado que aqui à direita eu fiz uma tabela,
para explicar como Fibonacci funciona.
Vamos usar esse mesmo tipo de tabela para tornar fiibo mais rápida,
evitando repetir um bocado de trabalho.
Nosso plano para isso é chamado `memoization'.
É como memorização, mas sem o r.
Aqui, eu tentei desenhar 2 `memos': um memorando corporativo e estas notinha amarelas,
que se usa algumas vezes para escrever algum lembrete para si mesmo.
Um memo, em Inglês, é simplesmente um documento, um pequeno documento,escrito --
-- um memorando.
Porque isso nos interessa?
Bem, acontece que nossa atual implementação de Fibonacci é super lenta.
Vou tentar provar isso para você.
Vejamos quanto tempo é gasto para 100 tentativas de calcular fibo(20) --
mais ou menos 0.3 seg.
Vamos aumentar um pouco, para fibo(24) --
deve gastar muito mais, né?
Oh! Muito muito mais -- de 0.3 seg para 1.75 seg.
cresceu um bocado!
Vamos ver para fibo(25) -- oh! quase dobrou:
temos agora 2.8 seg!
De fato, temos motivo para acreditar, com base em estudos do comportamento humano,
que se uma página web gasta mais que 6 seg para carregar,
você vai comprar seu produto em algum outro site.
Portanto, estamos usando uma grande fração deste tempo, apenas para computar
fibo(25).
E se você pensar nas árvores que eu desenhei antes, isso não será uma surpresa.
Se aumentamos n de 1, quase dobramos o trabalho em cada passo.
Isso é inadimissível -- precisamos de algo mais rápido.
Nossa solução é escrever, em uma tabela -- um pequeno memo -- para nos lembramos.
Vou construir uma tabela mapeando n a fibo(n) --
1,1,2,3,5,8 --
e quando eu estiver calculando isso, eu não tenho que fazer muito trabalho.
Suponha que eu queira calcular fibo(6).
Eu posso simplesmente olhar na tabela e reusar meu trabalho anterior.
Eu não tenho que recalcular fibo(5) -- já tenho isso aqui.
Apenas somo o valor dessas 2 células e obtenho a resposta.
Essa é a nossa idéia para tornar fibo muito mais rápida.
É chamada de `memoization' (memorização).
Podemos implementar nossa tabela, em Python, como um dicionário,
apenas preenchendo os números, à medida que os calculamos.
Portanto, eu começo com um dicionário vazio, atribuo valores às entradas do dicionário,
e verifico se algo, como no caso de 6, já está calculado.
E se estiver, eu imprimo o resultado.
Isso será super necessário agora, e talvez não tenha sido antes.
Uma das idéias chave de memorização é verificar se o trabalho já foi feito,
e anotá-lo.
Se já foi feito, ótimo! Você pode simplesmente reutilizá-lo.
Se não, você tem que fazer o cálculo uma primeira vez.