So here's one way to define make_hashtable. We're going to start by
initializing a variable i = 0. So we're going to start by creating
an empty table and what we want to do is add
n buckets, number of buckets to the table. So we're going to use
a while loop and we're going to loop while i is less
than number of buckets. So each time that I want to go
through the loop what we want to do is add on empty
bucket to our hash table. So we can do that using Append.
That adds a new empty bucket and we need to
remember to increase I to make sure that we don't
keep looping forever. So we're going to go through this
loop nbuckets number of times each time adding an empty bucket
to the table and then we need to return the
table at the end. So let's try that in the Python
interpreter. So here's the code just like we read out
and we'll print out the result of making a hash table.
We'll keep the number of buckets small for printing. For a real
use were going to want to have many more than three buckets. And let's
run that. And we see what we got is a list with
three empty lists as it's elements. So this works okay. It seems like
a lot more code than we need. And it is more code
than we need. There's a better way to write this, which is to
use a four loop. So, the general structure we've seen for four
loops. Alright. We've seen a loop that has, has a structure like this,
where the collection could be a list. It could be
a string. [SOUND] To have a four loop, we need some
set of objects that we're looping through. In this case, what
we want to do is loop through the numbers from 0 to
n buckets minus 1. So we want to create a list
that contains those values. So we, what we would like in
order to be able to define a procedure like make hash
table, is to have a list, which is the numbers from
0 to n buckets minus 1. Python provides an easy
way to do that, its called range. So range takes
two numbers, as inputs. The start and the stop number.
And what it outputs is a list of all the
numbers from start up to stop minus 1. So this
is what ranges outputs, a list of numbers, starting from
start. Increasing by 1, until we get to stop minus
1. We'll note that it doesn't include the value passed
in is the second parameter in the list. This turns
out to be useful because oftentimes when we look through
elements, we don't want to include the last element. So
that means if we evaluated something like range 0,10, the
result would be the list 0,1,2, up to 9. So
now that we know about range. We could change our loop
here. Instead of having this while loop, we could do
the for loop. And we prefer this for two reasons. The
first is it's going to make our code shorter. Anytime we
can make code shorter, that's usually a good thing. The second
is, it saves us from the danger of forgetting to increment
the variable. This is a common mistake, and when we forget
to increment the variable, the loop's just going to run forever. So
if we can write our while loops as for loops, that's usually
a good idea. So a better way to define the catch table
is to use the for loop. We're no longer going to need the
variable i. We still need table and now instead of using a
y loop we're going to use a for loop. We're going to leave the
variable name blank for a second, we'll figure out what to put
there later, and what we're looping through. Is from the range from
0 up to nbuckets. So we want to look through the
elements of the list range to nbuckets. That's going to be the
list of numbers from zero to nbuckets, minus 1. And for
each one of those we want to append, one new bucket to
the table, just like we did before. We don't need
to increment i, there's not i variable now. And at the
end of the loop, we return the table just as before.
For this loop, we didn't actually need a variable here, right?
We never used the variable inside. For this index of the
four loop, well, we still need something here, so I'm just
going to call the variable unused. To make it clear that we
have a name there. We don't actually use it in the body
of the formula. So this makes the code a lot smaller.
It will work the same way as what we had before.
So here's the new code. Several lines shorter than what we
had before. Does exactly the same thing. If you were really clever,
you might have thought of an even shorter way.
To define make hash table, that unfortunately doesn't quite
work. So the shorter way would be to guess,
that the times operator works on list, the same
way it worked on strings. So we could do
this by creating empty list, times nbuckets. This seems
great, it's only one line, really clear and easy
to understand, and it looks like it almost works.
So let's try that in the Python interpreter. And it looks like
it worked, we've got a hash table, a list with three empty
buckets. There's one big problem with this approach, and I'll show you
a hint why it is, and then we'll have a quiz to see
if you can figure out why. So now instead of just printing
out the result. We're going to assign it to a variable called table, and
now we're going to mimic what would happen when we add something to
the hashtable. That means we're going to add something to one of the buckets.
Let's pick bucket one, and let's assume
we're going to add the entry for udacity with
one url. And now we can print out
what's in that bucket. Looks like everything is
okay. What about what's in bucket zero? Now
we get the same result. So, think about
what went wrong. I'm going to ask a quiz to see if you can understand why this
simpler definition of make hash table doesn't actually work correctly.
これがmake_hashtableを定義する1つの方法です
まず変数i=0に設定します
バケット数をカウントする必要があります
空のtableを作成することから始めます
nbucketsつまりバケット数を
tableに追加したいので
whileループを使用して
iがバケット数より少ない間ループを行います
ループを行う必要があるたびに空のバケットを
ハッシュテーブルに追加する必要があります
appendを使用して行います
それにより新たな空のバケットを追加します
延々とループを継続しないように
iを増やすことを忘れてはいけません
このループをnbucketsの回数行い
そのつど空のバケットをtableに追加します
そして最後にtableを返す必要があります
これをPythonインタプリタで試してみましょう
これがちょうど読み出したコードです
make_hashtableの結果を表示させます
表示のためにバケット数を少なくします
実際には3バケットより
はるかに多いバケットを持つ必要があります
実行します
要素として3つの空のリストがあるリストを
取得しました
機能していますが
必要以上に多くのコードがあるように見えます
確かに不要なコードがあります
これをよくする方法があります
forループを使用することです
forループの一般的な構造は学習しました
コレクションがリストになる構造を持ったループを
学習しました 文字列にもなります
forループを実装するために
ループするオブジェクトがいくつか必要です
ここで行いたいことは
ゼロからnbucketsマイナス1の数値の間で
ループすることです
この値を含むリストを作成する必要があります
make_hashtableのような関数が
定義できるようにリストを持つことです
これはゼロからnbucketsマイナス1の数値になります
Pythonにはこれを簡単に行う方法があります
rangeと呼ばれるものです
rangeは入力として2つの数値を使います
開始と停止の数値です
出力するものは開始から停止マイナス1までの
すべての数値のリストです
これがrangeが出力するものです
開始から始まる数値のリストで
停止マイナス1に達するまで1を増やします
リストの2つ目のパラメータである渡した値が
含まれていないことに注意してください
要素を1つ1つ調べる際
たいてい最後の要素を含む必要がないので便利です
つまり何かを評価する場合
例えばrange(0,10)としましょう
結果はリストゼロから9までとなります
これでrangeが分かりました
このループを変更します
whileループを置く代わりにforループを行います
forループを使うのは2つの理由があります
1つはコードを短くできるからです
一般的にコードを短くすることはよいことです
2つ目は変数を増やすことを忘れる
危険性がなくなることです
これはよくやる間違いで
変数を増やすことを忘れると永遠にループし続けます
ですからforループでwhileループを書くのは
一般的によい考えです
make_hashtableを定義するよい方法は
forループを使用することです
変数iはもう必要ありませんがtableはまだ必要です
whileループを使用する代わりに
forループを使用します
変数名を空白にしておきあとで何を置くか考えます
ループするのはゼロからnbucketsまでの範囲です
nbucketsまでの範囲とリストの要素を
1つずつ調べる必要があります
ゼロからnbucketsマイナス1までの
数値のリストになります
その数値の1つ1つで以前行ったように
新しいバケットをテーブルにappendします
iを増やす必要はありません 変数iは現在ありません
そしてループの終わりで前回のように
テーブルを返します
このループではここに変数は必要ありませんね
内部に変数は使いません
forループのこのインデックスにはまだ何か必要です
変数unusedを呼び出します
分かりやすいように名前をつけています
本体には使用しません
これでコードをとても小さくできます
以前のものと同じように機能するでしょう
これが新しいコードです
以前のものより数行短くなっていますが
まったく同じことを行います
もっと短くする方法を考えついたかもしれませんが
make_hashtableの定義にはうまくいきません
短くする方法で時間演算子が
リストに作用することが推測できます
同じように文字列にも作用します
空のリストを作成しそれにnbucketsをかけます
すばらしいですね たった1行で済みました
とても明確で理解しやすいです
ほぼ機能しているように見えます
これをPythonインタプリタで試します
機能しているようです
ハッシュテーブルと
3つの空のバケットのリストが得られました
この手法には大きな問題が1つあります
それが何かヒントを与えます
理由を解明できるか小テストを行います
ですから結果をただ表示するのではなく
それにtableと呼ぶ変数を代入します
何かをハッシュテーブルに加えると
何が起きるのか模倣してみます
バケットの1つに何か追加します
バケット1を選びましょう
そして1つのURLとudacityのエントリを追加します
そのバケットに何があるのか表示します
すべて順調なように見えます
バケットゼロには何があるのでしょう
同じ結果になりました
何が誤りだったのか考えてください
make_hashtableにシンプルな定義が
なぜ機能しないのか
その理由を小テストで確認します