アルゴリズム超初心者入門

アルゴリズム超初心者入門 探索アルゴリズムをscratchで実装してみよう

この資料について 対象とする読者： • scratch学習済み • プログラミングを知らない人向け（中学生想定） 内容： • 探索アルゴリズム • 線形探索、二分探索、ハッシュ探索について

「問題を解決する定型的な手法・技法」のこと。(広辞苑から引用)

「問題を解決する定型的な手法・技法」のこと。(広辞苑から引用) →色々な「問題」がある Ex) ・クラス全員を身長の高い順に並べる(整列) ・特定の身長に一致する人物を探し出す(探索) ・文章の中から特定の単語を探す(文字列照合)

「問題を解決する定型的な手法・技法」のこと。(広辞苑から引用) →色々な「問題」がある Ex) ・クラス全員を身長の高い順に並べる(整列) ・特定の身長に一致する人物を探し出す(探索) ・文章の中から特定の単語を探す(文字列照合) →これら問題ごとに「定型的な」解き方が存在することが多い →「アルゴリズム」と呼ぶ

今回扱うアルゴリズム：探索（サーチ） 例）クラス全員の身長を集めたデータの中から、 特定の身長に一致する人物を探す

今回扱うアルゴリズム：探索（サーチ） 例）クラス全員の身長を集めたデータの中から、 特定の身長に一致する人物を探す より一般には「探索」とは、 あるデータの集合から、特定の値を持った要素を取り出すこと

今回扱うアルゴリズム：探索（サーチ） 例）クラス全員の身長を集めたデータの中から、 特定の身長に一致する人物を探す より一般には「探索」とは、 あるデータの集合から、特定の値を持った要素を取り出すこと 例えば、 [165, 161, 157, 171, 160, 172, 168] という配列から171を探す。 ・何番目にある？ ・そもそもあるかどうかもわからない

同じ問題を解くにしても、 いろんなアルゴリズムがある 今回紹介する探索のアルゴリズムは3つ • 線形探索 • 二分探索 • ハッシュ探索 ・それぞれメリットやデメリットがある。 ・どんな状況でどんな探索をしたいかによって使い分ける

さっそくアルゴリズムの解説 ・・・のまえに、実際に探索アルゴリズムを 利用した例を紹介してみる

Q. とある１週間にTwitterに投稿された全フリー素材の中で、 RT数がちょうど100のものを見てみたい

Q. とある１週間にTwitterに投稿された全フリー素材の中で、 RT数がちょうど100のものを⾒てみたい RT数がちょうど100のものを見てみたい データの集合…Twitter API というものを使って ツイートの情報を取得できる ※2021/6/14~6/21に、＃フリー素材 をつけて投稿されたものをデータの対象とした

Q. とある１週間にTwitterに投稿された全フリー素材の中で、 RT数がちょうど100のものを見てみたい データの集合…Twitter API というものを使って ツイートの情報を取得できる ※2021/6/14~6/21に、＃フリー素材 をつけて投稿されたものをデータの対象とした 実際にデータを集めてみると、731ツイートもある 目視で探すのは大変・・・

Q. とある１週間にTwitterに投稿された全フリー素材の中で、 RT数がちょうど100のものを見てみたい データの集合…Twitter API というものを使って ツイートの情報を取得できる ※2021/6/14~6/21に、＃フリー素材 をつけて投稿されたものをデータの対象とした 実際にデータを集めてみると、731ツイートもある 目視で探すのは大変・・・ →探索アルゴリズムの出番

結果 無事、所望のイラストを 見つけることができた 出典 : @mirumirumirumo_ https://twitter.com/mirumirumirumo_/status/140510998 6913525760

• https://twitter.com/mirumirumirumo_/status/1405109986913525760

結果 無事、所望のイラストを 見つけることができた 「え？どうやったの？」 出典 : @mirumirumirumo_ https://twitter.com/mirumirumirumo_/status/140510998 6913525760

• https://twitter.com/mirumirumirumo_/status/1405109986913525760

結果 無事、所望のイラストを 見つけることができた 「え？どうやったの？」 さっそくアルゴリズムを学んでいきましょう 出典 : @mirumirumirumo_ https://twitter.com/mirumirumirumo_/status/140510998 6913525760

• https://twitter.com/mirumirumirumo_/status/1405109986913525760

線形探索

線形：「直線状」 • 単純に一番左から順番に探していく。

線形：「直線状」 • 単純に一番左から順番に探していく。 [165, 161, 157, 171, 160, 172, 168] から171を探す

線形：「直線状」 • 単純に一番左から順番に探していく。 [165, 161, 157, 171, 160, 172, 168] から171を探す ①165は171じゃない

線形：「直線状」 • 単純に一番左から順番に探していく。 [165, 161, 157, 171, 160, 172, 168] から171を探す ①165は171じゃない ②161は171じゃない

線形：「直線状」 • 単純に一番左から順番に探していく。 [165, 161, 157, 171, 160, 172, 168] から171を探す ①165は171じゃない ②161は171じゃない ③157は171じゃない

線形：「直線状」 • 単純に一番左から順番に探していく。 [165, 161, 157, 171, 160, 172, 168] から171を探す ①165は171じゃない ②161は171じゃない ③157は171じゃない ④171は171 → 見つけた！

Scratchで実装してみよう #データ集合を作る #linear_searchブロックで線形探索を行う

#発見！

・メリット：元のデータの形はなんでもよい ・デメリット：時間がかかる

・メリット：元のデータの形はなんでもよい ・デメリット：時間がかかる 先ほどの例では配列の要素数が7 →探す値によって何回目に見つかるかが変わるが、 平均的にはだいたい４回目に見つかる

・メリット：元のデータの形はなんでもよい ・デメリット：時間がかかる 先ほどの例では配列の要素数が7 →探す値によって何回目に見つかるかが変わるが、 平均的にはだいたい４回目に見つかる →配列の要素数が70なら、だいたい35回目 →配列の要素数が700なら、だいたい350回目 →配列の要素数が2Nなら、だいたいN回目

・メリット：元のデータの形はなんでもよい ・デメリット：時間がかかる 先ほどの例では配列の要素数が7 →探す値によって何回目に見つかるかが変わるが、 平均的にはだいたい４回目に見つかる →配列の要素数が70なら、だいたい35回目 →配列の要素数が700なら、だいたい350回目 →配列の要素数が2Nなら、だいたいN回目 1回の操作で要素1つの正誤を判断しているので、操作回数は要素数に比例する

二分探索

• 昇順（or降順）に整列されたデータの集合に対して 適用できるアルゴリズム • まず真ん中の要素から比較する

• 昇順（or降順）に整列されたデータの集合に対して 適用できるアルゴリズム • まず真ん中の要素から比較する [157, 160, 161, 165, 168, 171, 172] から171を探す ※昇順に整列しといた

• 昇順（or降順）に整列されたデータの集合に対して 適用できるアルゴリズム • まず真ん中の要素から比較する [157, 160, 161, 165, 168, 171, 172] から171を探す ①165は171より小さい ※昇順に整列しといた

• 昇順（or降順）に整列されたデータの集合に対して 適用できるアルゴリズム • まず真ん中の要素から比較する [157, 160, 161, 165, 168, 171, 172] から171を探す ※昇順に整列しといた ①165は171より小さい したがって171は後半のどこかにある

• 昇順（or降順）に整列されたデータの集合に対して 適用できるアルゴリズム • まず真ん中の要素から比較する [157, 160, 161, 165, 168, 171, 172] から171を探す ※昇順に整列しといた ①165は171より小さい したがって171は後半のどこかにある [168, 171, 172] から171を探す

• 昇順（or降順）に整列されたデータの集合に対して 適用できるアルゴリズム • まず真ん中の要素から比較する [157, 160, 161, 165, 168, 171, 172] から171を探す ※昇順に整列しといた ①165は171より小さい したがって171は後半のどこかにある [168, 171, 172] から171を探す 以降同じことを繰り返す

scratchで実装してみよう #昇順に並んだデータを適当に生成 #「答え」に探したいキーを入力

＃リストの要素からsearchvalueを探す #findID番目にあるとする #見つかったら終わり #見つからなくても全て探索したら終わり

#見つかったということ #右半分にsearchValueがあるはず # 左半分にsearchValueがあるはず

・デメリット：元のデータの形が整列されてなければ使えない ・メリット：線形探索に比べて速い

・デメリット：元のデータの形が整列されてなければ使えない ・メリット：線形探索に比べて速い 1回比較するごとに探す範囲が半分になっていく 配列の要素数が7のとき: 配列の要素数が70のとき:

・デメリット：元のデータの形が整列されてなければ使えない ・メリット：線形探索に比べて速い 1回比較するごとに探す範囲が半分になっていく 配列の要素数が7のとき: 7→4→2→1 3回で終わる 配列の要素数が70のとき:

・デメリット：元のデータの形が整列されてなければ使えない ・メリット：線形探索に比べて速い 1回比較するごとに探す範囲が半分になっていく 配列の要素数が7のとき: 7→4→2→1 3回で終わる 配列の要素数が70のとき:70→35→18→9→5→3→2→1 7回で終わる

・デメリット：元のデータの形が整列されてなければ使えない ・メリット：線形探索に比べて速い 1回比較するごとに探す範囲が半分になっていく 配列の要素数が7のとき: 7→4→2→1 3回で終わる 配列の要素数が70のとき:70→35→18→9→5→3→2→1 7回で終わる やはり、平均35回かかる線形探索より早い！

配列の要素数が700のときは？

配列の要素数が700のときは？ 700を2で割っていくと（商は切り上げ）、10回目で1になる

配列の要素数が700のときは？ 700を2で割っていくと（商は切り上げ）、10回目で1になる →10回で終わる

配列の要素数が700のときは？ 700を2で割っていくと（商は切り上げ）、10回目で1になる →10回で終わる つまり、配列の要素数が1024（＝210）以下なら、最大でも10回で終わる

配列の要素数が700のときは？ 700を2で割っていくと（商は切り上げ）、10回目で1になる →10回で終わる つまり、配列の要素数が1024（＝210）以下なら、最大でも10回で終わる 配列の要素数が2NならN回で終わる！

配列の要素数が700のときは？ 700を2で割っていくと（商は切り上げ）、10回目で1になる →10回で終わる つまり、配列の要素数が1024（＝210）以下なら、最大でも10回で終わる 配列の要素数が2NならN回で終わる！ 線形探索の2N個から探すだけで平均N回もかかった

配列の要素数が700のときは？ 700を2で割っていくと（商は切り上げ）、10回目で1になる →10回で終わる つまり、配列の要素数が1024（＝210）以下なら、最大でも10回で終わる 配列の要素数が2NならN回で終わる！ 線形探索のN回は2N個しか探せなかった Nが大きくなるほど差がつく 二分探索は線形探索に比べ指数的に早くなっていく

Q 紙を何回折ると月に届く？

Q 紙を何回折ると月に届く？ 0.1mmの紙を1回折ると0.2mm、2回折ると0.4mm 折るごとに厚さは2倍になっていく

Q 紙を何回折ると月に届く？ 0.1mmの紙を1回折ると0.2mm、2回折ると0.4mm 折るごとに厚さは2倍になっていく 25回折ると富士山とほぼ同じ高さ 35回折ると日本列島の長さ

Q 紙を何回折ると月に届く？ 0.1mmの紙を1回折ると0.2mm、2回折ると0.4mm 折るごとに厚さは2倍になっていく 25回折ると富士山とほぼ同じ高さ 35回折ると日本列島の長さ 41回折ると約22万km 42回折ると約44万km > 地球と月の距離約38万km

Q 紙を何回折ると月に届く？ 0.1mmの紙を1回折ると0.2mm、2回折ると0.4mm 折るごとに厚さは2倍になっていく 25回折ると富士山とほぼ同じ高さ 35回折ると日本列島の長さ 41回折ると約22万km 42回折ると約44万km > 地球と月の距離約38万km 242 2×42 44万>>>84

ハッシュ探索

• 探索対象のデータ集合がハッシュになっている場合に使える

• 探索対象のデータ集合がハッシュになっている場合に使える • 「ハッシュ値とは、元になるデータから一定の計算手順により 求められた固定長の値」 IT用語辞典から引用

• 探索対象のデータ集合がハッシュになっている場合に使える • 「ハッシュ値とは、元になるデータから一定の計算手順により 求められた固定長の値」 IT用語辞典から引用 • 計算手順はなんでもいい 良し悪しはあるが

• 探索対象のデータ集合がハッシュになっている場合に使える • 「ハッシュ値とは、元になるデータから一定の計算手順により 求められた固定長の値」 IT用語辞典から引用 • 計算手順はなんでもいい 良し悪しはあるが 例えば157で割ったときの余りをハッシュ値とする 165, 161, 157, 171, 160, 172, 168でハッシュを作ると、

• 探索対象のデータ集合がハッシュになっている場合に使える • 「ハッシュ値とは、元になるデータから一定の計算手順により 求められた固定長の値」 IT用語辞典から引用 • 計算手順はなんでもいい 良し悪しはあるが 例えば157で割ったときの余りをハッシュ値とする 165, 161, 157, 171, 160, 172, 168でハッシュを作ると、 余り 0 データ 157 1 2 3 4 160 161 5 6 7 8 165 9 10 11 168 12 13 14 15 171 172 16

• 171を探す 余り 0 データ 157 1 2 3 4 160 161 5 6 7 8 165 9 10 11 168 12 13 14 15 171 172 16

• 171を探す 余り 0 データ 157 1 2 3 4 160 161 5 6 7 ①171のハッシュ値を計算する 171÷157=1余り14 8 165 9 10 11 168 12 13 14 15 171 172 16

• 171を探す 余り 0 データ 157 1 2 3 4 160 161 5 6 7 ①171のハッシュ値を計算する 171÷157=1余り14 ②データの14番目を探す 8 165 9 10 11 168 12 13 14 15 171 172 16

• 171を探す 余り 0 データ 157 1 2 3 4 160 161 5 6 7 ①171のハッシュ値を計算する 171÷157=1余り14 ②データの14番目を探す 8 165 9 10 11 168 12 13 14 15 171 172 16

• 171を探す 余り 0 データ 157 1 2 3 4 160 161 5 6 7 8 165 9 10 11 168 ①171のハッシュ値を計算する 171÷157=1余り14 ②データの14番目を探す ③171があったら探索成功、 なかったらデータ全体に無いということ 12 13 14 15 171 172 16

・デメリット：データの衝突が起きる可能性がある →色々な解決法

・デメリット：データの衝突が起きる可能性がある →色々な解決法 ・メリット：どの要素も（殆ど）一発で見つかる →データの要素数Nに対して、常に1回

・デメリット：データの衝突が起きる可能性がある →色々な解決法 ・メリット：どの要素も（殆ど）一発で見つかる →データの要素数Nに対して、常に1回 当然、線形探索や二分探索より圧倒的に早い！ ただし、ハッシュを構築しておく必要がある

・線形探索 ・二分探索 ・ハッシュ探索

・線形探索 ・二分探索 ・ハッシュ探索 課題： ・二分探索をするためにはデータをソート（整列）させておく必要がある ・ハッシュ探索で衝突したらどうする？ ・他にどんなアルゴリズムがあるか？