学習アルゴリズム

第3章. より良いハッシングを通してより良い生活を

この作品はAIを使って翻訳されている。ご意見、ご感想をお待ちしている：[e-mail]

この章では、次のことを学ぶ：

• シンボルテーブルに(キーと値)のペアを格納し、キーに関連する値を取り出す方法。¹

• 配列のサイズが格納されるペアの数に比べて十分に大きい場合、効率的な検索のために（キーと値）のペアを格納するために配列を使用する方法。

• リンクリストの配列を使って（キーと値）のペアを格納し、キーの削除に対応する。

• 効率的なシンボルテーブルのサイズを変更する方法。

• 連続した呼び出しによって演算子の振る舞いが変化する可能性がある場合に、平均的な実行時パフォーマンスを決定するための償却分析。

• 幾何学的リサイズがどのように軽減されるかというと、 、コストのかかるリサイズ操作の頻度が減る。つまり、put() 、平均してO(1)の性能が償却されることになる。

• 計算ハッシュ関数はどのようにキー値を一様に分散させることができるのか、それはシンボルテーブル実装の効率を保証する。

値をキーに関連付ける

単に値を格納するのではなく、特定のキーに値を関連付けるために、（キーと値）のペアのコレクションを格納する必要があるかもしれない。これはシンボル・テーブル・データ型として知られており、キーだけを指定して関連付けられた値を発見することができる。ハッシュは、（キーと値）のペアを見つけるために最初から最後まで手作業でコレクションを検索する効率的な代替手段を提供する。先に説明した検索アルゴリズムよりも優れている。シンボル・テーブルは、キー（とその値）の削除を許容しながらも効率的である。すべてのキーを特定の順序、たとえば昇順で取り出す機能は失うが、結果として得られるシンボル・テーブルは、個々のキーに関連する値を取り出したり格納したりするのに最適なパフォーマンスを提供する。

任意の月と年のカレンダーを印刷する関数print_month(month, year) を書きたいとしよう。例えば、print_month('February', 2024) は次のように出力する：

   February 2024
Su Mo Tu We Th Fr Sa
             1  2  3
 4  5  6  7  8  9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29

どのような情報が必要だろうか？その年のその月の最初の日の平日が必要であり（上記では木曜日）、2月の日数が28日（2024年のようなうるう年では29日）であることを知る必要がある。その年の各月の長さを日単位で記録した値を持つ固定配列、month_length を使うことができる：

month_length = [ 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]

最初の月である1月は31日あるので、month_length[0] = 31となる。2月は次の月で28日あるので、リストの次の値は28である。1年の最後の月である12月は31日なので、month_length の最後の値は31である。

これまで本書で紹介してきたことを踏まえると、同じ長さのkey_array を保存しておき、その中から月を検索して、month_length に対応する値を割り出すという方法もある。次のコードは、February has 28 days ...