アルゴリズムとデータ構造(1)
1

もくじ
第一回

なぜアルゴリズムを学ぶのか
単純なデータ構造
オーダーとは？
ソートアルゴリズム
2

もくじ
第二回

アルゴリズムと密接に関係するデータ構造
木構造
グラフ構造
ハッシュテーブル演習3

なぜアルゴリズムを学ぶのか4

なぜアルゴリズムを学ぶのか

日常的な実装でアルゴリズムの知識が役に立つ場面:
例えば…

5

なぜアルゴリズムを学ぶのか

日常的な実装でアルゴリズムの知識が役に立つ場面:
例えば…

6

なぜアルゴリズムを学ぶのか
ぶっちゃけ最近の言語は基本的なアルゴリズムが標準装備！
各種データ構造
ソートマップ(Key-Value ペア)→ 使い方だけ知っていればよい場面がほとんど

7

なぜアルゴリズムを学ぶのか
真に役立つ場面標準装備の機能を適切に使い分けるとき標準装備の機能では実現できない複雑な実装をするとき
パフォーマンスが重要で、標準装備の機能が最適解でないとき例) ユーザー同士のマッチング
8

なぜアルゴリズムを学ぶのかまとめ

普段は「標準装備の機能」を使うので意識することは少ないけど、「ここぞ！」という場面でアルゴリズムの知識が役に立つ！
少なくとも機能を適切に使い分けるためには絶対に知っておきたい！

9単純なデータ構造
10単純なデータ構造
もくじ

配列
連結リスト
スタックキュー
11

配列

データを連続したメモリに並べたもの「先頭のアドレス」と「長さ」で管理することが多い
長さが決まっており、ランダムアクセスが早い
一般的に広く使われる12連結リスト

データと「次のデータへのポインタ」をセットにして管理長さが無制限で、途中へのデータ追加・削除が早い
先頭から順にデータを辿るのは早いが、ランダムアクセスが遅い
データの追加・削除を多く行う場面で使われる

13

スタック

後入れ先出し(LIFO: Last In First Out)で保存するデータ構造
プログラムの基本構造など、様々な場面で使われる
例: 関数の呼び出しアドレスの保存("スタック"トレース)

14

キュー

先入れ先出し(FIFO: First In First Out)で保存するデータ構造
順序が重要なものによく使われる
例: 非同期処理の処理順制御(メッセージ"キュー")15

オーダーとは?
16

オーダーとは?

オーダーは、アルゴリズムを学ぶ上で無視できない計算量を表す概念
長さ n のデータを処理するのに必要なステップ数が、n に応じてどのように変化するか(n = 1 のときに比べて何倍に増えるか)を表す
値が小さいほうが優れている
17

いつ使うのかアルゴリズムの早さを、その詳細な実装に依存せずに考えるのに使う。
例: アルゴリズムAよりアルゴリズムBのほうがオーダーが小さい ので優れている
例えば Redis のオンラインマニュアル
は各操作のオーダーを公開している18

オーダーの書き方と意味

データの長さを n として、n が変化した時の処理ステップ数の変化をO(nを使った式) で表す。
一番次数が高い項以外は無視し、たとえば O(n2 + n) とはならずO(n2 ) になる
O(1) … 処理ステップ数は n に関わらず常に一定になる
O(n) … 処理ステップ数がデータの長さ n に比例する( データの長さが 2 倍になると、処理ステップ数も 2 倍になる )O(n2 ) … 処理ステップ数が n の2乗に比例する

19

オーダーの見方

オーダーは「 n が増えたときに処理ステップ数がどのように変わっていくか」を表すので、グラフで表すことができる。

よくあるオーダーの例

O(1) < O(log n) < O( n )​< O(n) < O(n log n)
20

オーダーの見方

オーダーがあまりにも大きいア
ルゴリズムは、現実的には使い物にならないことが多い

オーダーが非常に大きい例

O(n2 ) < O(2n ) < O(n!)

21オーダーの比べ方

オーダーが小さいほど、処理ステップ数が少ない = CPU負荷や処理時間が少ないので優れている
オーダーの大小関係は、前ページのようにグラフを描いてもよいし、n に十分大きな値を代入して計算して比べてもよい
1 < log n <n < n < n log n < n2 < n3 < 2n < n!
​22O(n)の例

func Calc(data []int) int {var result int = 0for i := 0; i < len(data); i++ {result += data[i]}return result}forは、 data の長さに比例して処理ステップ数が増える → O(n)23O(n)の例

func Calc(data []int) int {var result int = 0
for i := 0; i < len(data); i++ {result += data[i]}for i := 0; i < len(data); i++ {result *= data[i]}return result}が繰り返されても n に 比例するという点は変わらない → O(n)※ O(2n) とはならない!!
for24

2O(n )の例

func Calc(data []int) int {var result int = 0
for i := 0; i < len(data); i++ {for j := 0; j < len(data); j++ {result += data[i] * data[j]}}return result}forが入れ子になると n ステップがさらに n ステップ繰り返される→ O(n 2 )25

O(1)の例

func Calc(data []int) int {return data[0]}dataの長さにかかわらず常に一定ステップ数で終わる → O(1)26

O(log n)の例

func Search(data []int, value int) int {var i, j = 0, len(data)for i < j {var h = (i + j) / 2
if data[h] > value { i = h + 1 } else { j = h }}return i}

二分探索(1ループにつき検索対象を半分に狭めながら検索するアルゴリズム)は O(log n)27

ソート28ソート

ソートとは、データを一定の順序に並べ替えること。
ソートはオーダーが高くなりやすい操作のひとつであり、オーダーを減らすために古くから研究されてきた。

29

代表的なソート

安定性: 並べ替えキーが等しい2つの要素が元と同じ順に並ぶこと
名称
計算時間 安定性
O(n2 )
バブルソート○O(n log n) ○マージソート
クイックソート O(n log n) ×
ボゴソート(おまけ) O(∞)×
30

代表的なソート

バブルソート - O(n2 ) / 安定

分かりやすいので勉強によく使われるが、実用性はない

マージソート - O(n log n) / 安定

元の配列と同じサイズの一時メモリが必要だが並列化しやすい

クイックソート - O(n log n) / 不安定
一般的に最も高速だと言われている31代表的なソート

ボゴソート - O(∞) / 不安定

ランダムに並び替えて、揃ってたらヨシ！！
アホみたいだが、量子コンピュータでは実用的になるかもしれない32

クイックソート

最も効率がいいと言われているアルゴリズム。
よく使われるアルゴリズムで、効率化のヒントにもなるので詳しく見ていく。
まずは動画で→babble_100.mp4 … バブルソート ( 速度比較用 )quick_100.mp4 … クイックソート
33クイックソート
1.

データの中からピボット(基準値)をひとつ選ぶ34

クイックソート2.

ピボットより大きい値を左から順に探す

35

クイックソート3.

ピボットより小さい値を右から順に探す

36

クイックソート
4.

それらを入れ替える

37

クイックソート
5.

左からのポインタと右からのポインタが出会うまで繰り返す

38

クイックソート

左のほうにピボット以下の値が、右のほうにピボット以上の値が集まる39

クイックソート
6.

配列をピボット以下/以上の領域に分け、再帰的にクイックソートする

40

クイックソート
1回目の再帰まで終わったところ

41

クイックソート最初のピボット以下の領域をソートし終えたところ

42

クイックソートソート完了!!

43

実装例
func QuickSort(data []int) {if len(data) <= 1 { return }var left, right = 0, len(data) - 1
var pivot = getPivot(data) //for {for data[left] < pivot { left++ }for data[right] > pivot { right-- }if left >= right { break }data[left], data[right] = data[right], data[left]
left++
right-}
var p = right + 1
QuickSort(data[:p])QuickSort(data[p:])}平均的なデータをひとつピックアップ 先頭、中間、末尾の中央値を使うことが多い

44

クイックソートがなぜ早いのか
大まかな手順とオーダー1.

配列の中からピボットを1つ選ぶ
O(1)

2.

配列の左側にピボット以下を、右側にピボット以上を集める
O(n)

3.

ピボット以下/以上に分けた領域をそれぞれクイックソートする
O(?) ← 想像しにくい
45

クイックソートがなぜ早いのか早いアルゴリズムによく使われるテクニック「ループの代わりに『より小さな同じ問題への分割』を使う」
この操作は普通 O(log n) になる
使用例: クイックソート、マージソート、二分探索46

クイックソートのオーダー
1.

配列の中からピボットを1つ選ぶ
O(1)

2.

配列の左側にピボット以下を、右側にピボット以上を集める
O(n)

3.

ピボット以下/以上に分けた領域をそれぞれクイックソートする
O(log n)クイックソートは 基本操作 O(n) × 再帰 O(log n) なので、全体のオーダーは O(n log n) になる47

演習

やってみよう

48

演習

クイックソートの getPivot() を実装して動かしてみましょう。
どう実装したら動作効率がいいか考えてみましょう。
余裕がある方は、どう実装したら効率が悪いかも考えてみましょう。

49

演習

回答例: 先頭・中間・末尾のデータの中央値を返す
func getPivot(data []int) int {var first, middle, last = data[0], data[len(data)/2], data[len(data)-1]
if first < last {if middle < first { return first }if middle < last { return middle }middle return last}
if first < middle { return first }if middle < last { return last }return middle}

50

演習

なぜ中央値だと動作効率が良いのか？

ループの代わりに『より小さな同じ問題への分割』を使う場合、素早く「小さな問題」に分割するほうが再帰回数が少なくなる。
データの中央値を使えば半分に分割でき、2分割する場合は最速で1再帰あたりのデータ数を減らしていけるので最も効率がよい。
逆に、1 : 他全部 みたいな分割をすると効率が悪くなる。
51

おまけ

時間が余ったら52

実際のプロジェクトでの使用例

アルゴリズムの知識を使って、ユーザーマッチングを改善した
O(n3 ) → O(n)for _, user1 := range users {for _, user2 := range users {for _, user3 := range users {// ...
}
}
}
53

実際のプロジェクトでの使用例
マッチング 仕様

人でマッチングする同じバトルを選択していること
3 人全員が違うキャラクターであること
パーティ内に回復役キャラクターが1人以上いること
その他細かい条件354

実際のプロジェクトでの使用例

マッチング 初期コード - O(n3 ) / メモリ消費 O(n)仕様上これしか思いつかないが、これが問題であることは認識
for _, user1 := range users {for _, user2 := range users {for _, user3 := range users {if IsMatched(user1, user2, user3) {result = append(result, NewRoom(user1, user2, user3))
}
}
}
}
55

実際のプロジェクトでの使用例

マッチング 修正後コード - 速度 O(n) / メモリ消費 O(n)負荷をメモリに寄せることで、劇的な高速化に成功した
仮ルーム作成ユーザーをキャラクターごとに分類し、重複しないように並べる

//
O(n)
//
tempRooms := CreateTempRooms(users)
var missmatchRooms = []TempRoom{}
for _, tempRoom := range tempRooms {////missmatchRooms}

マッチング条件を満たしていないルームを発見したら missmatchRooms の先頭10個とメンバーの入れ替えを試し、それでも成立しない場合はに追加する

56