Japanese subtitles

← 21-01 Hash Tables

Get Embed Code
3 Languages

Showing Revision 2 created 06/01/2015 by sk.

  1. ハッシュテーブルについて
    皆さんからの質問にお答えします
  2. 受講生のバラシャさんからの質問です
  3. “Pythonではバケットのサイズを
    どう決めるのですか?”
  4. レッスン5で取り上げきれなかった
    ハッシュテーブルに関する内容はたくさんあります
  5. メモリが使い放題で
    どれだけ使っても速度に問題なければ
  6. 好きなだけハッシュテーブルを大きくできます
  7. その場合 複数の要素がバケットに
    ハッシュされることはありません
  8. レッスン3ではメモリのコストについて学びました
  9. メモリは性能がよくなればなるほど高価になるので
    いくらでも使えるわけではなりません
  10. ハッシュテーブルを可能な限り小さくし
    妥協点を探る必要があるのはそのためです
  11. ハッシュテーブルの適切な実装では
  12. パフォーマンスとメモリ利用のバランスが
    上手に取れています
  13. バランスはレッスン4で使った
    ロードファクタで決まります
  14. ロードファクタは
    全要素数をバケット数で割った値です
  15. これに関する問題はレッスン4…
    いえレッスン5ですね レッスン5でやりました
  16. NをBで割ることでバケット数と要素数の
    変化に対する影響が分かりました
  17. ここで見えているキー数とバケット数は
    平均値であるということに注意してください
  18. 最悪値の考慮が必要なアプリケーションは
    数多くあります
  19. そのため平均値が小さくても
    最悪値が大きい可能性があるのです
  20. 最悪値の場合はバケット数を更に増やすか
    何とかしてハッシュ関数を変えなければなりません
  21. ハッシュテーブルの実装では
    ロードファクタを1以下にするのが一般的です
  22. Pythonの辞書を実装する時に
  23. キー数がテーブルサイズの3分の2以上になる場合は
    テーブルサイズを変えましょう
  24. テーブルサイズを倍にすると
    ハッシュ値も変わります
  25. バケットの数によって
    ハッシュ関数の返す結果が変わるからです
  26. 新たなハッシュテーブルへの置換作業が必要ですが
    探索速度は速くなります
  27. つまりハッシュテーブルに
    100万個の要素があるとしたら
  28. 150万個のバケットが必要です
  29. しかし要素が100万個を超える場合は
    バケットのサイズを倍にしなければなりません
  30. その場合は
    300万個のバケットを持つことになります
  31. レッスン5で見てきた例と比べると
  32. ロードファクタの値が
    小さく感じるかもしれませんね
  33. 例に挙げたハッシュテーブルは
  34. バケット数が非常に少ない一方で
    多くの要素がある場合の例でした
  35. 何が起きているのか
    部分的に分かりやすくしています
  36. 何千もの空のバケットがあるとしたら
    何が起きているのかが見えづらいからです
  37. またレッスン5では
    各バケットをリストとして実装しました
  38. リストはコストの高いデータ構造です
  39. ハッシュテーブルを作るため
    空のリストが大量に必要です
  40. Pythonの辞書は1つのフラットリストとして
    実装されています
  41. つまり各ハッシュ値に1つのスペースがあり
    1スペースに1バケットが割り当てられます
  42. 1つのバケットに2つのキーは
    割り当てられません
  43. Pythonの辞書の実装時には
    空きスペースの探索が必要です
  44. 最初のスペースが埋まっていた場合に
    次のスペースを探す手順が必要なのです
  45. これには探索とテーブルの追加が必要で
    複雑なのでレッスンでは取り上げませんでした
  46. しかし空のリストがなくなるので
    メモリの使用量は減ります
  47. Pythonの辞書の実装は
  48. 「Beautiful Code」という本で
    詳しく紹介されています
  49. どんな実装なのか興味のある方は
    ぜひ読んでみてください