YouTube

Got a YouTube account?

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

Japanese subtitles

← 18-30 Better Hash Functions Solution

18-30 Better Hash Functions Solution

Get Embed Code
2 Languages

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

  1. これはとても難易度の高い問題です
    もし自分で解けなくても問題ありません

  2. でも説明の途中であきらめないでください
  3. 行き詰まってしまったパートを理解できたら
    自分で終わらせられるか確認してください
  4. 関数を定義する必要があります
  5. hash_string関数を定義します
    2つの入力、キーワード、バケット数を使用します
  6. 円のどこにあるか追跡します
  7. そのために新たな変数を挿入する必要があります
  8. ゼロの位置から開始します その変数を設定します
  9. ハッシュを示すhを使用します
    それをゼロに設定します
  10. キーワードの文字列を1つずつ調べる必要があります
  11. キーワードの文字列1つ1つを調べる
    forループを実装します
  12. 各文字でハッシュに加える必要があります
    ハッシュにその文字の値を加えます
  13. ここでモジュロを行うことができます
  14. この時点でモジュロバケットを使用します
  15. 丸括弧が必要なことに注意してください
  16. ここにモジュロバケットだけを置いた場合
    正確な結果を得られません
  17. なぜならord (c) % bucketsを行うことになるからです
  18. しかし本当に行う必要があることは
  19. h+ord(c)の合計のモジュロバケットです
    そして最後にハッシュ値を返します
  20. ここで毎回モジュロを行う代わりに
  21. 最後に1回だけモジュロを行うことができます
  22. 本当に大きな文字列の場合
    大きな数値を計算することになります
  23. 最後にモジュロバケットを計算します
    どちらの方法でも機能します
  24. 文字列がとても長いなら
    こちらの方が少しよいでしょう
  25. 非常に大きな数値を計算するとなると
    費用もかかります
  26. とても長いキーワードなら
    電源まで切れてしまうかもしれません
  27. ここでモジュロを行う方がよいでしょう
  28. どちらの方法でも結果は同じです
    これをPythonインタプリタで試してみましょう
  29. スケッチパッドに書き出したコードです
  30. 変数hがあります
    これはハッシュ値を追跡するものです
  31. キーワードにあるすべての文字を調べます
  32. ハッシュ値にそれぞれの値を加えます
  33. バケット数をモジュロします 例を試してみましょう
  34. 12バケットでaは予想どおり
    バケット1をハッシュします
  35. bを見るとやはり予測したとおり
    バケット2をハッシュします
  36. もう1つ試すことがあります
  37. bad_hash_string関数を覚えていますね
  38. この関数の問題の1つが
  39. すべての文字列で機能しないことでした
    特に空の文字列で機能しません
  40. このhash_string関数は空の文字列で
    機能すると思いますか?
  41. 実行する前に結果を想像してみてください
  42. では実行します 結果がゼロになります
  43. エラーは出ません 結果がゼロになのは当然です
  44. hはゼロから開始します 文字列に文字がない時
  45. ループはまったく行いません
  46. ですからhは返す時もゼロのままです
    もっと長い例も試してみましょう
  47. 文字列udacityを12バケットでハッシュする時
  48. バケット11を取得します
    バケット数を増やすことができます
  49. バケット数を増やしてみましょう
    1,000バケットあると仮定してみましょう
  50. バケット755を取得しました
    これではhash_string関数によって
  51. すべてのバケットにすべての文字列を
    うまく分配できたという十分な確証にはなりません
  52. しかし非常に大きな数値を得たことから
    すべてのバケットを使用していると思われます