Return to Video

18-18 Making Lookup Faster

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

18-18 Making Lookup Faster

more » « less
Video Language:
English
Team:
Udacity
Project:
CS101 - Intro to Computer Science
Duration:
04:59

Japanese subtitles

Revisions