So the answers is, we need to change the three of these procedures.
We need to change crawl web, we need to change add to
index, and we need to change lookup. We don't need to change get
all links at all, that we can keep exactly the same as it
was. It just returns the list of links, it doesn't depend on the
index. We don't need to change add page to index. This is
a little more surprising since it depends on index, but because of the
way we wrote add page to index, it calls add to index. So
it doesn't depend how we actually represent the index. It's going to go through
all the words add them to index by calling add to
index. So we don't actually have to change that code. We
do need to change the other two, so let's start with
crawl web and figure out what we need to do to
change this, to use a dictionary. And the change is actually
going to be really small, right? The index is here, in the
old version we initialize index to a list, to the empty
list And all we do with index is pass it in
to add page to index. So to change that to use
a dictionary, all we need to do is change the square brackets
to be curly brackets. So now, instead of starting with an empty
list, we're going to start with an empty dictionary. So that's the only
change we need to make to crawl_web. The change to add index
is going to be a little more complicated. And we can see from
the code to crawl_web, what happens with each page was that we
call add to index, passing in index, which is now a dictionary.
Let's look at add_page_to_index. I claimed that we didn't need to
change that. Here's the code to add_page_to_index. And it takes the index.
It goes through the words. It adds each word to the index.
We can do this just the same whether index was a list
or a dictionary. We don't need to change add page to
index, we are going to need to change add to index. So
we are going to need to change the code to add to
index and lets try to figure out how. So before we had
add to index, that takes an index, a keyword and a URL. We'll
still take the same parameters but what we had to do when it
was a list was go through all the entries in the index, check
for each one, if it matches the keyword we're looking for. If we
find that it does, then we add the URL. If we get to
the end without finding it, then we append a new entry, which is
the keyword with a list of URLs containing just the first URL. So
let's figure out how to change this to work with the hash table index.
So, the great thing about the hash table is we don't
need to loop through anything now. We know exactly where it is
from the hash table. With the dictionary, the built in in-operation
gives us that. So instead of looping, now we can check right
away if the keyword is in the index. So what's going to
happen if we found the keyword in the index, that means that
we can look it up. This will look up in the dictionary
the entry that corresponds to the index. That's going to be the list
of URLs that we have. And so all we need to do now is append to that entry the
new URL. If it's not in the index already, well
we need to do something different. What we did before
was we added a new element to the index list
using append. We don't want to do that now. We
want to add a new key value paired to the
dictionary. So we're going to do that by using the assignment.
And the entry that we're adding is the list containing
just this URL. So you can delete everything else here.
Add the new entry to the keyword. So this is a
lot simpler. We have less code. And it's going to run a lot
faster. We don't have to loop through anything. Because of the hash
table, we can right away look up whether the keyword is in
the index, we can find if it is, what the value
is, by using the dictionary lookup, and we can append the newer
URL to the list of the URLs associated with that keyword. If
it's not found, we can create a new entry, using the dictionary
syntax, like this, that contains just that URL. So,
now we've got a much simpler way to add
to index. I hope you understand this. If you
do, you should be able to define lookup yourself.
答えは
“これらの関数の内3つを変更する必要がある”です
まず1つ目はcrawl_web
2つ目はadd_to_index
そして3つ目はlookupです
get_all_linksはまったく変更せず
以前と同じように保持できます
単にリンクのリストを返し
インデックスには左右されません
add_page_to_indexも変更させる必要はありません
これはインデックスに左右されるのでやや驚きますが
add_page_to_indexの書き方のせいで
add_to_indexを呼び出すのです
ですから実際のインデックスの表示には
影響されません
add_to_indexを呼び出しすべての単語を調べ
それをインデックスに追加しています
ですからこのコードを変える必要はありません
別の2つを変更する必要があります
crawl_webから始めて
ディクショナリに使用するために
これにどんな変更を加えればいいか解明します
変更はとても小さいものになりますよね?
インデックスがここにあります
古いバージョンではインデックスに
空のリストを設定しています
そしてインデックスで行うことは
それをadd_page_to_indexに渡すことです
ディクショナリに使用する変更を行うために
角括弧を波括弧に変える必要があります
そこで空のリストから開始するのではなく
空のディクショナリから開始しましょう
これがcrawl_web行う必要のある唯一の変更です
add_indexへの変更はもう少し複雑になります
そしてcrawl_webのコードについては
各ページで行うことはadd_to_indexを呼び出し
インデックスを渡すことでした
これは今はディクショナリです
add_page_to_indexを見てみましょう
これには変更が必要ないと言いました
これがadd_page_to_indexのコードで
インデックスを使用します
単語を1つずつ調べインデックスに追加します
インデックスがリストであれディクショナリであれ
同じことができます
add_page_to_indexは変更する必要がありません
add_to_indexを変更する必要があります
ですからadd_to_indexのコードを変更します
どのように行うのか考えてみましょう
add_to_indexはインデックス、キーワード、
URLを使用します
現在も同じパラメータを使いますが
リストの場合に行ったことは
インデックス内のすべてのエントリを1つずつ調べ
探しているキーワ-ドと一致するかどうか
チェックすることでした
一致することが分かればURLを追加します
見つけられずに終わりに達したら
新しいエントリをappendします
それは1つ目のURLを含むURLのリストとキーワードです
ハッシュテーブルインデックスと連携させるために
これをどのように変更するのか解明しましょう
ハッシュテーブルの素晴らしい点は
何もループする必要がないということです
それはハッシュテーブルによるものだと分かっています
ディクショナリでは組み込み演算が同じことを行い
ループすることなく キーワードがインデックスに
あるかどうかすぐにチェックできます
インデックスでキーワードを
見つけた時に起きることは
それをlookupできるということで
インデックスに相当する
ディクショナリのエントリでもlookupします
それは既存のURLのリストになります
今行う必要があることは
そのエントリを新しいURLにappendすることです
インデックスにない場合はというと
別のことをする必要があります
以前行っていたことはappendを使用して
新しい要素をインデックスリストに追加することです
今はする必要はありません
新しいキーと値の組を
ディクショナリに追加する必要があります
代入を使ってこれを行います
追加するエントリは
このURLだけを含んだリストになります
ですからこのすべてを削除することができます
新たなエントリをキーワードに追加します
とても簡単です
コードが減り実行がとても速くなりました
何もループする必要はありません
ハッシュテーブルのおかげでインデックスに
キーワードがあるかすぐにlookupできます
キーワードがあれば
ディクショナリlookupを使用することで
その値が分かります
新しいURLをキーワードに関連するURLのリストに
appendすることができます
もし見つからなければディクショナリ構文を使用し
新しいエントリを作成することができます
それにはそのURLだけが含まれます
これでadd_to_indexを
かなりシンプルにすることができました
皆さんがこれを理解できていることを願います
できていれば自分でlookupを定義できるはずです