So what do we need to do to make lookup faster?
Well let's think about why it was so slow, right? The reason
it was so slow is that we were doing this for loop,
we were going through all the elements in order, and we're checking
if they match the keyword, right? And we had to do this
for the entire index, for an entry, for a keyword that's not
in the index, To determine that it's not there, we had to
go through the whole index. This is not how we use indexes
in real life, right? If you're looking for a word in the
index of a book, you don't have to look through every single entry
to see if that word exists. You can jump around, and the
reason that you can jump around is because the entries in the index,
are sorted, they're sorted in alphabetical order, so you know where that
entry would belong. You just need to find the right place and see
if it's there. So we can do that with our index instead
of having our index kept in arbitrary order. If we kept our index
in assorted order, then we could find the place where
that entry belongs and look for it. Sorting is a very
interesting problem. It's something we're not actually going to talk about more
in this class. We're going to do a different way of doing
that. What we're going to do is find a way to
find where the entry should be that doesn't require actually keeping
all the entries sorted. What we want is something that will
allow us, given a keyword, we're going to have some function that
tells us where it belongs. We're going to call that
a hash function. That tells us where in the entry
to look. And so instead of having to look through
the whole index, the hash function will tell us where
that entry belongs. So what we need for this is
some function that's going to take a key word, map
it to a number And that number is the position
in the index where that number belongs. We could do this
lots of different ways. One simple thing would be to
think, well we know alphabet. This is more like the way
an index for a book would work, and we're going to
have for each entry and index, we'll have based on the
first letter, we'll put all the entries that start with
tha tfirst letter in the same place. So, if we're looking
for a key word that starts with u, that prefer hash
would tell us to look in the place where all the
words that start with u are. And then we'd only have to
look through the words that start with u. So this would allow
us to do a look up much more quickly than looking through
the whole index. This isn't quite the best way to do things. If
we made our places based on the letter, well, then we have
a problem if we have two words with the same first letter. You
generally expect to have more than one word that starts with the
same letter. So instead of having just an element here for each position,
we're going to have a list of elements that would be all
the words that start with u So when we look up the
word udacity, we look in the entry for u, and if the
word that's there doesn't match then we know udacity isn't in the
index. There are lots of problems with this. The first problem is
well, there might be more than one word that starts with u.
So we can't just have one entry here. What we need to
have is a list of entries We often call this a bucket.
So we need a bucket of all the entries that
start with u that would be in this position. So, instead
of just having one entry like the old structure of our
index, now we're going to have a list of entries, and
each element of the index will now be a bucket, which
is a list of entries that are in the right position.
This is going to be our bucket of our, all the entries
that start with u, and that would have all the different
entries that start with the letter u in that bucket. So this
is getting better. Now, for each look up, instead of having to
look through all of the words in index, we just need to
find the position that starts with the right letter. That's got a
bucket of all the words that start with that letter, and then
we just need to look through that bucket. This works okay, but
this doesn't really scale very well. At best, if we have you
know, ten million words well now instead of having ten million entries
to go through, we need to go through ten million divided
by say 26, if we have 26 letters. It's not making
things much faster. It's making things maybe at best, 26 times
letter. That assumes that all of the buckets are the same size.
Certainly if we make the buckets based on the first letter,
that's not going to be the same size. If the words
are a typical English words. We're going to have many more
words that start with s or t, say than start with u.
So, we want to fix those two problems. We want to
be able to have more buckets. So we're not going to just
use the first letter, we're going to use some function on the
whole word that tells us where it belongs. And we're going to try
to make that function distribute the words fairly well. So the
structure that I've described is what's called a hash table. This
is a very useful data structure. It's so useful that it's
built into Python. There's the Python type called a dictionary. Which provides
this functionality. At the end of today's unit, I'll explain
how the Python dictionary works, and how to use it,
and we'll modify the search engine code to use dictionary
instead of the lookup table that we built, but before
we do that, we are going to implement it ourselves. We
are going to make sure that we understand how the hash
table works by writing all the code to do it
ourselves and then we'll switch to using the built-in Python [INAUDIBLE]
lookupを速くするためには
まず遅い理由を考えてみましょう
遅い理由はこれでループを行っていたからです
すべての要素を順番に1つずつ調べていました
キーワードと一致するかどうかです
これをすべてのエントリに行っていました
そこにあるかどうか判断するために
すべてのインデックスを調べていました
実生活ではこのようにインデックスを
使用しませんよね?
本のインデックスで言葉を探す場合
言葉があるかどうか確認するためにすべてのエントリを
1つずつ調べる必要はありません
飛ばして先に進めます
先に進めるのはインデックスのエントリが
分類されているからです
アルファベット順に分類されているので
そのエントリがどこに属しているか分かります
正しい場所を見つけそこにあるかどうか
確認するだけで済みます
ですから任意の順序でインデックスするのではなく
インデックスを分類します
分類してインデックスを保存できれば
エントリが属している場所を探し
見つけることができます
分類は興味深い問題ですが
このコースで詳しく取り組みません
これから別の方法を行います
すべてのエントリを実際に分類する
必要のない場合を見つけます
必要なものはキーワードが分かるものです
キーワードがどこに属しているのか
分かる関数を置きます
ハッシュ関数と呼びます
これにより探すエントリが分かります
すべてのインデックスを探す必要なく
ハッシュ関数によってエントリがどこに属しているか
知ることができます
ここに必要なものはキーワードを用い
数値に変換する関数です
この数値は数値が属している
インデックスの場所になります
これを様々な方法で行うことができます
簡単なものはアルファベットです
これは本のインデックスで
各エントリとインデックスの最初の文字を基にします
最初の文字が同じ場所で開始する
すべてのエントリを一緒にします
もしuで始まるキーワードを探しているとしたら
ハッシュ関数がuから始まるすべてのエントリが
ある場所を見るように教えます
私たちはuから始まる言葉だけを見ます
これでインデックス1つ1つを探すより
はるかに速くlookupを行えます
これが最適な方法という訳ではありません
文字を基にして場所を作成すれば
同じ文字から始まる2つの言葉がある場合に
問題が生じます
同じ文字から始まる1つ以上の言葉を得られると
想定しているからです
ですから各場所に要素をただ置くのではなく
uから始まる言葉すべての要素をリストにします
udacityという言葉をlookupする時は
uのエントリを探します そこで言葉が一致しなければ
インデックスにudacityがないと分かります
これにはたくさんの問題があります 1つ目の問題は
uから始まる文字が
複数あるかもしれないということです
なのでここにただ1つのエントリだけを
置くことができません
置く必要のあるものはエントリのリストです
これはバケットと呼ばれます
なのでこの位置にくるuから始まる
すべてのエントリのバケットが必要です
古い構造のインデックスのように1つのエントリを
ただ置くのではなくエントリのリストを置きます
インデックスの各要素がバケットになります
つまり適切な位置に置かれたエントリのリストです
これがuから始まるすべてのエントリの
バケットになります
バケット内には文字uから始まる
様々なエントリがあります これでよくなりました
これでlookupではインデックス内の
すべての言葉を1つ1つ
探す必要がなくなり ある文字から始まる位置を
探し出すだけになりました
ある文字から始まる言葉すべてがバケットになりました
必要なのはそのバケット内を探すことだけです
これは有効ですがあまりうまく拡張できません
よくても1,000万語です
ここでは1,000万エントリを調べる代わりに
26割る1,000万を調べる必要があります
26文字ある場合はこれ以上
処理を速くすることはできません
よくても26文字が限界です
これはすべてのバケットが同じサイズだと仮定します
もちろん1つ目の文字を基にして
バケットを作成する場合
同じサイズにはなりません
もし言葉が英語ならuから始まる言葉よりも
sやtから始まる言葉の方が多くなるはずです
ですからこの2つの問題を修正する必要があります
さらにバケットを作ることにします
1つ目の文字をただ使用するのではありません
どこに属しているのか分かるように
言葉全体に関数を使用します
言葉をうまく分配する関数を作成します
記述した構造はハッシュテーブルと呼ばれるものです
これはとても便利なデータ構造です
これをPythonに組み込むと効果的です
ディクショナリと呼ばれる機能性の高い
Pythonの型もあります
今回のレッスンの最後でPythonディクショナリが
どう機能するのか説明します
そして作成したlookup tableの代わりに
ディクショナリを使用するため
検索エンジンコードを修正します
ですがそれらを行う前にこれを実装します
自分で実装するために
すべてのコードを書き
ハッシュテーブルが機能することを確認します
そして組み込みPythonの使用に切り替えます