YouTube

Got a YouTube account?

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

Japanese subtitles

← 18-18 Making Lookup Faster

18-18 Making Lookup Faster

Get Embed Code
2 Languages

Showing Revision 1 created 07/21/2014 by osawakjvta.

  1. lookupを速くするためには
    まず遅い理由を考えてみましょう
  2. 遅い理由はこれでループを行っていたからです
  3. すべての要素を順番に1つずつ調べていました
  4. キーワードと一致するかどうかです
    これをすべてのエントリに行っていました
  5. そこにあるかどうか判断するために
    すべてのインデックスを調べていました
  6. 実生活ではこのようにインデックスを
    使用しませんよね?
  7. 本のインデックスで言葉を探す場合
  8. 言葉があるかどうか確認するためにすべてのエントリを
  9. 1つずつ調べる必要はありません
    飛ばして先に進めます
  10. 先に進めるのはインデックスのエントリが
    分類されているからです
  11. アルファベット順に分類されているので
    そのエントリがどこに属しているか分かります
  12. 正しい場所を見つけそこにあるかどうか
    確認するだけで済みます
  13. ですから任意の順序でインデックスするのではなく
  14. インデックスを分類します
    分類してインデックスを保存できれば
  15. エントリが属している場所を探し
    見つけることができます
  16. 分類は興味深い問題ですが
    このコースで詳しく取り組みません
  17. これから別の方法を行います
  18. すべてのエントリを実際に分類する
    必要のない場合を見つけます
  19. 必要なものはキーワードが分かるものです
  20. キーワードがどこに属しているのか
    分かる関数を置きます
  21. ハッシュ関数と呼びます
  22. これにより探すエントリが分かります
  23. すべてのインデックスを探す必要なく
  24. ハッシュ関数によってエントリがどこに属しているか
    知ることができます
  25. ここに必要なものはキーワードを用い
    数値に変換する関数です
  26. この数値は数値が属している
    インデックスの場所になります
  27. これを様々な方法で行うことができます
  28. 簡単なものはアルファベットです
    これは本のインデックスで
  29. 各エントリとインデックスの最初の文字を基にします
  30. 最初の文字が同じ場所で開始する
    すべてのエントリを一緒にします
  31. もしuで始まるキーワードを探しているとしたら
  32. ハッシュ関数がuから始まるすべてのエントリが
    ある場所を見るように教えます
  33. 私たちはuから始まる言葉だけを見ます
  34. これでインデックス1つ1つを探すより
    はるかに速くlookupを行えます
  35. これが最適な方法という訳ではありません
  36. 文字を基にして場所を作成すれば
  37. 同じ文字から始まる2つの言葉がある場合に
    問題が生じます
  38. 同じ文字から始まる1つ以上の言葉を得られると
    想定しているからです
  39. ですから各場所に要素をただ置くのではなく
  40. uから始まる言葉すべての要素をリストにします
  41. udacityという言葉をlookupする時は
  42. uのエントリを探します そこで言葉が一致しなければ
  43. インデックスにudacityがないと分かります
  44. これにはたくさんの問題があります 1つ目の問題は
  45. uから始まる文字が
    複数あるかもしれないということです
  46. なのでここにただ1つのエントリだけを
    置くことができません
  47. 置く必要のあるものはエントリのリストです
    これはバケットと呼ばれます
  48. なのでこの位置にくるuから始まる
    すべてのエントリのバケットが必要です
  49. 古い構造のインデックスのように1つのエントリを
  50. ただ置くのではなくエントリのリストを置きます
  51. インデックスの各要素がバケットになります
  52. つまり適切な位置に置かれたエントリのリストです
  53. これがuから始まるすべてのエントリの
    バケットになります
  54. バケット内には文字uから始まる
  55. 様々なエントリがあります これでよくなりました
  56. これでlookupではインデックス内の
    すべての言葉を1つ1つ
  57. 探す必要がなくなり ある文字から始まる位置を
  58. 探し出すだけになりました
  59. ある文字から始まる言葉すべてがバケットになりました
  60. 必要なのはそのバケット内を探すことだけです
  61. これは有効ですがあまりうまく拡張できません
  62. よくても1,000万語です
    ここでは1,000万エントリを調べる代わりに
  63. 26割る1,000万を調べる必要があります
  64. 26文字ある場合はこれ以上
    処理を速くすることはできません
  65. よくても26文字が限界です
  66. これはすべてのバケットが同じサイズだと仮定します
  67. もちろん1つ目の文字を基にして
    バケットを作成する場合
  68. 同じサイズにはなりません
    もし言葉が英語ならuから始まる言葉よりも
  69. sやtから始まる言葉の方が多くなるはずです
  70. ですからこの2つの問題を修正する必要があります
  71. さらにバケットを作ることにします
  72. 1つ目の文字をただ使用するのではありません
  73. どこに属しているのか分かるように
    言葉全体に関数を使用します
  74. 言葉をうまく分配する関数を作成します
  75. 記述した構造はハッシュテーブルと呼ばれるものです
  76. これはとても便利なデータ構造です
    これをPythonに組み込むと効果的です
  77. ディクショナリと呼ばれる機能性の高い
    Pythonの型もあります
  78. 今回のレッスンの最後でPythonディクショナリが
    どう機能するのか説明します
  79. そして作成したlookup tableの代わりに
    ディクショナリを使用するため
  80. 検索エンジンコードを修正します
  81. ですがそれらを行う前にこれを実装します
    自分で実装するために
  82. すべてのコードを書き
    ハッシュテーブルが機能することを確認します
  83. そして組み込みPythonの使用に切り替えます