YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

Japanese subtitles

← 04-07 Memoization

dummy description

Get Embed Code
3 Languages

Showing Revision 1 created 10/23/2014 by Udacity.

  1. 画面右部分に簡単な表を作りました
  2. フィボナッチ数列の計算を理解するためです
  3. このように表を使いフィボナッチ数列を
    より速く計算し
  4. 繰り返しの計算を省きましょう
  5. このような方法は正式にはメモ化と呼ばれています
  6. スペルはMemorizationからrを取ります
  7. ビジネスで使われるメモと
    黄色い付箋タイプのメモの2種類を描きました
  8. 自分のためにメモを書く時がありますよね
  9. メモとは書きとめられた小さな文書という意味です
  10. 覚え書きとも言われます
  11. なぜこれを使うのでしょう?
  12. 今のfibo関数の実装はとても遅いです
  13. 今からお見せしましょう
  14. 20番目のフィボナッチ数を
    100回計算するのにかかる時間は
  15. 約0.3秒です
  16. 24番目の数はどうでしょう?
  17. 変わらないと思いますよね?
  18. 0.3秒から1.75秒と大きな違いが出ました
  19. かなり差があります
  20. 25番目の場合は約2倍の時間がかかりました
  21. 2.8秒もかかってしまいました
  22. ある研究によると
  23. Webページを表示するのに6秒以上かかると
  24. 別のページに移ってしまうことが多いそうです
  25. これでは限られた時間の大半をフィボナッチ数の
  26. 計算に費やしてしまっています
  27. 先ほど書いた図を思い出してほしいのですが
  28. Nを1増やしただけで各段階の計算が
    2倍に増えていましたね
  29. これでは使えませんのでもっと速い処理が必要です
  30. そのためには自分たちのために
    表やメモを書くことが大事です
  31. Nからfibo(N)の値への対応表を作ります
  32. 1、1、2、3、5、8
  33. これがあれば数を知りたい時
    いちいち計算せずに済みます
  34. 6番目のフィボナッチ数を知るには
  35. この表を参照すればいいのです
  36. あの何度も繰り返す計算をしなくても
    5番目のフィボナッチ数はここに記載されています
  37. この2つのセルから答えを出すことができます
  38. これでフィボナッチ数の計算を速くできます
  39. メモ化と呼ばれています
  40. 表はPythonの辞書で実装できます
  41. 計算する度に数で表を埋めていきます
  42. 空の辞書のなかにマッピングをしていきます
  43. まずは6の数があるかどうかを調べ
    その数がある場合は
  44. すぐに結果を出力します
  45. この技術はこれからとても重要になっていきます
  46. メモ化の大事なポイントは
    前に行った計算が記録されているか
  47. 調べるということです
  48. 記録があれば再利用できます
  49. 記録がなければ
    自身で計算する必要があります