# 問題解決力を鍛える！アルゴリズムとデータ構造

## 第8章(8.5~8.7)

- 任意参加
- ファシリテーター: chen

### 話す・書く順番決めルーレット

in Ruby

['hsu', 'chen', 'teruya', 'kanazawa', 'okura', 'tsujita'].shuffle.each { |v| puts ">[name=#{v}]\n\n" }

in JavaScript

const l = ['hsu', 'chen', 'teruya', 'kanazawa', 'okura', 'tsujita']
l[Math.floor(Math.random()*l.length)]

### ファシリテーター決め方

- `%w(hsu chen teruya kanazawa okura kanno)`の順番でやっていく

### 参加者がやること
- 事前に決められた章を読む
- 学んだことやわからなかったことを書き込む（任意）

当日
- 最初に感想や質問を書く時間を設ける(10分)
- 時間枠 60分
- 延長枠 30分

### 勉強会時にやること

各自学びや気付き、疑問を発表していく
ファシリテーターがよしなに議論を進める
終了前に勉強会を振り返る？（KPTなどで）← 60分のときに仮締め

## 各自が書き込む場所

>[name=chen]

### 8.5 配列と連結リストの比較
- 配列：i番目の要素にアクセスする必要がある時使う
- 連結リスト：要素を頻繁に挿入・削除する必要がある時使う

用途が違いますよね

### 8.6 ハッシュテーブル
- 挿入・削除・検索どれも処理しやすいもの
- 要は、key/valueをペアしている関数

Javaでコーディングする時によくハッシュテーブル（HashMap）が使われた記憶がある...

### 8.7 まとめ
この表、一目で見ると各データ構造の用途が大体わかる

>[name=tsujita]

> 8.5
- 要素xを検索する処理は、配列も連結リストもO(N)の計算量になる

> 8.6
- ハッシュテーブルは要素の挿入、削除、検索がO(1)でできる

なんとなく配列が便利というイメージがありましたが、ハッシュの優秀さがわかりました

>[name=okura]

### 8.5 配列と連結リストの比較

基本的にコレクションの途中にデータを挿入するとき以外は配列が優位になりがちなのかな。

### 8.6 ハッシュテーブル

ここからRubyの"Hash"の名前は来ているんだけど、Matzが（ちょっと）後悔していた。

https://twitter.com/yukihiro_matz/status/1402052061592621059

### 8.6.4 C++やPythonにおけるハッシュテーブル

ここには"set"が出てくるけど、Rubyにも"Set"ライブラリはあって実装はHashを使っている。

https://docs.ruby-lang.org/ja/latest/library/set.html

### 8.6.5 連想配列

Rubyの"Hash"はこっち。

>[name=teruya]

> ハッシュの衝突対策
ほぼO(1)（優秀）

> 連想配列
連想配列のデータ構造として主にハッシュテーブルが用いられている、という関係性なんですね（違いをよく知らなかった）

> 各データ構造の各クエリに対する計算量
やはりハッシュテーブルの優秀さが際立つ、実際はi番目の要素へのアクセスが必要になるケースが多いのだとは思いますが…
二次元配列の代わりにhash1つで賄うみたいなのも可能だったりする。

> 章末問題8.7

hashを使ったO(N)版(3秒程度)

N = 10_000_000
K = 1_000_000
nums_array = Array.new(N) { rand(N) }
nums_hash = Array.new(N) { rand(N) }.each_with_object({}) { |num, hash| hash[num] = nil }

puts "Preparation Done"

answer = []
nums_array.each do |num|
  rest = K - num
  if nums_hash.key?(rest)
    answer << [num, rest]
  end
end

p answer

bsearchを使ったO(NlogN)版(30秒程度)

N = 10_000_000
K = 1_000_000
nums_array = Array.new(N) { rand(K) }
nums_array2 = Array.new(N) { rand(K) }

puts "Preparation Done"

#O(NlogN)
nums_array2.sort!

answer = []
# O(N)
# 全体としてO(NlogN)
nums_array.each do |num_from_array|
  # O(logN)
  num_from_array2 = nums_array2.bsearch { |n| num_from_array + n >= K }
  next unless num_from_array2
  if (num_from_array + num_from_array2) == K
    answer << [num_from_array, num_from_array2]
  end
end

p answer

## 振り返り

>[name=chen]

照屋さんのdemo、いつも楽しかったと思います
計算量が体感できて面白いですね。

>[name=tsujita]

せっかくの機会なので、と思い最近AtCoderの過去問を解いてみたりしてます

>[name=teruya]

データ構造は実務にも活かせる知見が多くありそうですね👀
https://qiita.com/drken/items/fd4e5e3630d0f5859067

>[name=okura]

今日の内容にはなかったけど、Rubyの配列は無限に拡張されるので便利。

## 終了後ファシリテーターがやること
- 次回のファシリテーターを決める
　- 照屋さん
- 読む範囲を決める
- 第九章全部