[algorith_meetup]アルゴリズムとデータ構造 ミートアップ#2

[Eigo-Mt-Fuji]

やりたいこと

• 問題解決力を鍛える！アルゴリズムとデータ構造 - Kindle を読みたい

  • 大槻兼資. 問題解決力を鍛える！アルゴリズムとデータ構造 Kindle 版.

• 読んだ結果１つでもいいから得るもの得て整理したい

  • アルゴリズムとデータ構造なんて今更だし、おさらいだけど。

進め方

• https://github.com/Eigo-Mt-Fuji/portfolio-2022/issues/7 と同じ
  • 本書のねらいを確認
  • ポイントを3つ選んで学習
  • まとめると

本書のねらいを確認

• アルゴリズムとは「問題を解くための方法，手順」
• 単にアルゴリズムの動作を説明するだけでなく，「どうしたらよいアルゴリズムを設計できるか」という視点

3点集中

今回は、データ構造(1) 配列 連結リスト　ハッシュテーブル、データ構造(2) スタックとキュー、データ構造(3) グラフと木 の3つに集中してミートアップ

データ構造(1) 配列 連結リスト　ハッシュテーブル

がんばってミートアップした点をここに書く！

• データ構造を学ぶ意義

• データ構造1 配列と連結リストの比較

• データ構造1 ハッシュテーブル

• データ構造（datastructure）とは https://github.com/Eigo-Mt-Fuji/portfolio-2022/issues/11#issuecomment-1146533733

  • データ構造(1) 配列 https://github.com/Eigo-Mt-Fuji/portfolio-2022/issues/11#issuecomment-1146538122
  • データ構造(1) 連結リスト https://github.com/Eigo-Mt-Fuji/portfolio-2022/issues/11#issuecomment-1146545439
  • データ構造(1) ハッシュテーブル https://github.com/Eigo-Mt-Fuji/portfolio-2022/issues/11#issuecomment-1146577179
  • まとめると https://github.com/Eigo-Mt-Fuji/portfolio-2022/issues/11#issuecomment-1146577711

データ構造(2) スタックとキュー

がんばってミートアップした点をここに書く！

• スタックとキューの概念
• スタックとキューの動作と実装

データ構造(3) グラフと木

がんばってミートアップした点をここに書く！

• 順序木と二分木
• スタックとキューの動作と実装

[Eigo-Mt-Fuji]

• データ構造（datastructure）とは
  • データのもち方のこと
    • アルゴリズムを実装するときに，読み込んだ値や計算中に求めた値をデータ構造という形で保持
    • 必要に応じて
    • データ構造から所望の値を取り出す
    • データ構造に値を挿入して管理
  • データ構造によって「クエリ」の計算時間に差が生じる
    • データ構造から所望の値を取り出したりするような要求（＝クエリ（query））
    • クエリタイプ１
      • 要素xをデータ構造に挿入する
    • クエリタイプ２
      • 要素xをデータ構造から削除する
    • クエリタイプ３
      • 要素xがデータ構造に含まれるかどうかを判定する
  • 基本的なデータ構造「配列」「連結リスト」「ハッシュテーブル」
  • 「データ構造」ごとの「得意なクエリ」「苦手なクエリ」

[Eigo-Mt-Fuji]

• データ構造(1) 配列
  • 配列とは
  • 大量のデータに対して１つ１つの要素に気軽にアクセスできるようにするためのデータ構造
  • この本では、配列といえば「可変長配列」を指す
  • 得意なクエリ
  • ランダムアクセス
    • 記憶されている場所や書き込みの順序に関係なく直接アクセスすることをランダムアクセスという
  • 苦手なクエリ
  • 要素xの挿入(要素yの直後に要素xを挿入するクエリ)
    • 要素yが配列内のどこにあるかを特定する必要がある
    • この操作だけでも最悪O(N)の計算量を要する
      • 3.2 線形探索法を活用できる。
    • 次に、要素yより後ろの配列要素を後ろにずらす必要がある
    • この操作にも最悪O(N)の計算量を要する
  • 要素xの削除

[Eigo-Mt-Fuji]

• データ構造(1) 連結リスト
  • 連結リストとは
    • 各要素を「ポインタ」と呼ばれる「矢印」によって一列でつないだものを連結リストという。
    • 連結リスト内の１つ１つの要素＝ノード
      • 連結リストでは、前（または後）がどのノードか管理する。
      • 配列のように各ノードが何番目かという情報は管理しない。
        • 挿入・削除クエリを処理する度に「各ノードが全体で何番目か」の情報を更新するとなれば、大きな計算時間を要するため、配列のように各ノードが何番目かという情報は管理しない。
      • なにもないことを表す存在の必要性（＝ダミーノード、番兵）
      • 各ノードがポインタで連結されているデータ構造の実装する手段（＝自己参照構造体）
        • 自己参照構造体とは自分自身の型へのポインタ
    • 配列の弱点である挿入・削除クエリに強いデータ構造
  • 得意なクエリ
    • 挿入・削除操作をO(1)の操作で実行できる
  • 苦手なクエリ
    • i番目の要素xを参照するクエリ
    • 配列とは異なりi番目の要素へアクセスするにはO(N)の計算量を要する
      • 連結リストでは、「各ノードが全体で何番目か」の情報をもたず、前（または後）がどのノードかのみ管理するので、i番目の要素へアクセスするには、先頭からポインタを辿っていく捜査が必要になる。
    • 連結リスト内で要素xを検索するには、O(N)の計算量を要する
    • 配列内で要素xを検索する場合も、O(N)の計算量を要する(要素xを検索する上で、連結リストと配列の計算量は同じといえる）

[Eigo-Mt-Fuji]

• データ構造(1) ハッシュテーブル
  • ハッシュテーブルとは
  • データ集合Sの各要素xに対し、ハッシュ関数h(x)(xがハッシュテーブルのキー、h(x)はハッシュ値と呼ぶ。0 < h(x) < M)を対応付けする方法で、挿入・検索・削除の各クエリを処理するデータ構造をハッシュテーブルと呼ぶ
    • 「バケット」のアイディアに汎用性をもたせたのがハッシュテーブル
    • バケットとは
      • 某配列の要素xを添え字に持つ配列T[x]のこと。T[x]の値(true/false)が某配列内に値xが存在するかどうかを表す
      • 通常、このバケットは、某配列の要素xの値範囲は、一定の範囲に制限(0〜M未満(Mは正の整数)に限定)される前提で実装される
    • 単純一様ハッシュでは、ハッシュテーブルの各要素にアクセスする計算量はO(1+N/M)
    • N個のキー
    • データ集合Sの要素の最大値M
  • 得意なクエリ　
  • 挿入、削除、検索いずれのクエリもO(1)の計算量で処理できる
  • 苦手なクエリ
  • データ構造に挿入したN個のキーがすべて同じハッシュキーを持つ時、キーの探索にO(N)の計算量が必要となる
    • 単純一様ハッシュ
    • 負荷率

[Eigo-Mt-Fuji]