なっとく!アルゴリズム16 ハッシュテーブル

ハッシュテーブルは、最も便利な基本データ構造の一つである。

ハッシュテーブルの仕組み(実装、衝突、ハッシュ関数

食料品店で働いているとして、客の商品購入の際、その値段を価格表で調べる必要がある。

単純探索→O(n)

二分探索→O(log n)

もっと早く調べたい。

商品をO(1)時間で調べたい。

 

ハッシュ関数は、文字列を渡すと、数字を返す関数である。

(コレを、ハッシュ関数が「文字列を数字にマッピングする」という。)

ハッシュ関数の要件>

・一貫していなければならない

→"apple"を渡すと"4"が返される。それも、いつも。

・単語を、それぞれ異なる数字にマッピングする

→どの単語を渡しても、常に"1"を返すようなハッシュ関数は使い物にならない。最良のケースにおいては、どの単語も、それぞれ異なる数字にマッピングされるはずである。

 

<仕組み>

ハッシュ関数は、一貫して、名前を同じインデックスにマッピングする。

ハッシュ関数は、異なる文字列を異なるインデックスにマッピングする。

ハッシュ関数は、配列の大きさを把握しており、有効なインデックスのみを返す

 

ハッシュ関数と配列を組み合わせると、ハッシュテーブルというデータ構造になる。

これは最も基本的な、追加のロジックを持つデータ構造である。

配列やリンクリストはメモリに直接マッピングされるのに対して、ハッシュテーブルはもう少しスマートであって、ハッシュ関数を使って要素の格納場所をスマートに判断する。

・ハッシュテーブルはまた、高速でもある。ハッシュテーブルは、データの格納に配列を使うからだ。

 

・ハッシュテーブルは、キーと値のペアで構成される。ハッシュテーブルは、キーを値にマッピングする。

 

 

 

 

なっとく!アルゴリズムを読んで15 マージソートとクイックソート

最悪なケース、と平均的なケース、とは、それぞれいかなるものか?

なっとく!アルゴリズム14 クイックソートについて

クイックソートは、ソートアルゴリズムの一種であって、選択ソートよりもずっと高速で、実際によく使われている。

クイックソートも、分割統治を用いる。

クイックソートを使って、配列を並び替える。ソートアルゴリズムで処理できる、最も単純な配列とは、いかなるものであろうか。

 

配列によっては、ソートの必要が全くないものもある。

 

a.空の配列、または要素が一つだけの配列、基本ケース。(そのまま返せば良い)

→ソートの必要がないケース

b.もう少し大きな配列(要素が2つとか、非常に簡単)

c.もう少し大きな配列の場合

分割統治を使っているので、基本ケースに到達するまで、この配列を分割していくことになる。

クイックソートの仕組み)

1.配列から要素を一つ取り出す。この要素をピポットと呼ぶ。

2.次に、ピポットよりも大きな要素と、小さな要素にを見つけ出す。これをパーティショニングという。

この時点で、

1.ピポットよりも小さいかずを全て含んだ部分配列

2.ピポット

3.ピポットよりも大きいかずを含んだ全ての部分配列

の三つがあることになる。

 

1.3の部分配列が仮にソート済みであるとしたら、問題は至極簡単である。

→左配列+ピポット+右配列 で終わるので。

 

クイックソートの基本ケースにおいては、2つの部分配列のソート法を既に知っているものとする。そのため、2つの部分配列でクイックソートを呼び出し、結果を結合すれば、ソート済みの配列になる。

 

[10, 15, 33]について。

例えば15をピポットしたとして、(1、ピポットを選ぶ)

2、配列のパーティショニングを行い、2つの部分配列(ピポットよりも小さい要素とピポットよりも大きい要素)に分割する

3、2つの部分配列で、クイックソート再帰的に呼び出す。

、の3ステップだ。

 

[1,10, 15, 33]について、33をピポットした場合には、左の部分配列について、クイックソート再帰的に呼び出す。

 

したがって、要素が4つの配列も、ソートできる。

ならば、5つでもできる。

つまり、[3,5,2,1,4]について、

ピポットとして3を選んだとすると、部分配列でクイックソートを呼び出す。

(qsort(2,1) 3 qsort(5,4)のイメージ)

部分配列をソートした後に、全体を結合すれば、ソート済みの配列が得られる。

 

以上のような、帰納法による証明によって、アルゴリズムがうまくいくことがわかる。

帰納法においては、基本ケース(0と1)についてアルゴリズムがうまくいくこと、また帰納ケース(1が行けるなら2,2がいけるなら3,3がいけるなら4,,,,といった連鎖)を証明するものである。

なっとく!アルゴリズム13 クイックソートの例(配列の合計)

数字の配列があったとして、全ての数字を足して、合計を返すメソッドは、ループを使えばとても簡単である。

再帰関数を使うとどうなるか。

 

1.基本ケースの想定

配列の要素が、0または1この配列を思いついた場合、合計を出すのはとても簡単である。

2.再帰呼び出しのために、空の配列に近づいていく必要がある。問題の規模を縮小するには、どうすれば良いか。

sum (2,4,6) = 12

2 + sum(4,6) = 12

下の式の方が、問題を縮小していると言える。

 

リストを取得

→リストが空ならば、0を返す

→リストが空でなければ、合計はリストの最初の数に、残りの数の合計を足したものになる

再帰では、状態が追跡される

(基本ケースに到達するまで、再帰が部分的な完了している関数呼び出しの状態を保存している)

 

 

なっとく!アルゴリズム12 クイックソートについて

ひとつ目の重要な分割統治アルゴリズムとして、クイックソートについて学ぶ。

クイックソートはソートアルゴリスムの一つであり、第二章で選択ソートよりも、ずっと高速です。

 

分割統治

3つの例を用いて、分割統治を用いたソートアルゴリズムである、クイックソートを見ていきます。

 

・農地を、正方形の形に分割したい。ひとつの区画として使うことができる正方形を割り出すにはどうすれば良いか。→分割統治(再帰アルゴリスムの一種)

手順は、以下の2段になる。

1.基本ケースを特定する。基本ケースは、できるだけ単純なものであるほど良い。

2.基本ケースになるまで問題を分割(縮小)していく。

 

1.基本ケース

一辺がもう一辺の倍になっているケース

2.短い方の辺の倍数分長辺から正方形を切り取った後、あまりについて同じ作業をする。

*このサイズに適合するマットも大きな正方形を見つけ出せれば、それは農地全体で支える最も大きな正方形になる(ユークリッドの互除法

1680 ✖️ 640 から640 ✖️400に、問題が縮小

 

なっとく!アルゴリスムを読んで⑩ スタックについて

コールスタック、という、基本的かつ重要なデータ構造の概念がある。

(例えば、バーベキュの手順が書いてある)todoリストの例で言えば、スタックからアイテムをポップし、→「get food(食材調達)」と書かれていると読み取る→実際には、細かくいうとハンバーガーの材料を買い、ケーキを焼く必要があるということを書く→これらの作業を付箋紙にかき、スタックにプッシュする、といった形である。

 

*関数から別の関数を呼び出すと、呼び出している側の関数は、部分的に中断した状態で中断する。

複数の変数の関数を保存するために使われるスタックをコールスタックと呼ぶ。

 

再帰においても、コールスタックは使われる。

なっとく!アルゴリスムを読んで⑨ 基本ケースと、再帰ケース

再帰関数は自身を呼び出すため、無限ループに陥らない意味でも、基本ケースと再帰ケースの二つで構成される。

再帰ケースで、関数が自身を呼び出す。基本ケースでは、関数が自身をよび出さないので、無限ループに無限ループには陥らない。