アルゴリズムめっちゃ大事
エンジニアにとってCSの基礎知識を学んでいない筆者が効率的に処理を書くとはを自慢気に語れるようになりたいと思い
個人で学習したアルゴリズムの書き方をまとめる。
解説は必要と思ったタイミングでは入れますが、詳細には書かれていないので学びたい方は更にググるかコメントください。
超基本のmap
mapはGoには標準搭載されている。mapはO(1)で値にアクセスできる優れものである。
例として要素数N個のスライス中に重複する要素があるかを判定する関数を考えてみよう。
最初に筆者が考えたのは
- 一番目の要素を二番目以降の要素と比較して重複があるか判定
- 二番目の要素を三番目以降の要素と比較して重複があるか判定
... - N-1番目の要素をN番目以降の要素と比較して重複があるか判定
この処理だと時間計算量は**O(N^2)**となり効率は良くはありません。
これをmapを使う方法で考えてみます。
- mapを定義
- スライスをループして、mapのキーにindexの要素があるか重複判定。重複がなければmapのキーにindexの要素を追加
これをすることで計算量はO(N)となる。空間計算量はO(N)。
コードを見てみよう。
func containsDuplicate(nums []int) bool {
hm := make(map[int]struct{})
for i := range nums {
if _, ok := hm[nums[i]]; ok {
return true
}
hm[nums[i]] = struct{}{}
}
return false
}
mapのvalueにはstruct{}{}を入れているが、もちろんtrueを入れてもOK。
two pointers
two pointersはleftとrightの2つのポインタを使ったテクニックになる。
パターンは色々あるが回分の判定を例に見てみよう。
回分はある文字列が左から順に読んでも右から順に読んでも一致する状態であり、英語ではpalindromeという。
条件として引数の文字列は小文字の英語のみとします。
func isPalindrome(s string) bool {
l, r := 0, len(s) - 1
for l < r {
if s[l] != s[r] {
return false
}
l++
r--
}
return true
}
時間計算量はO(N)で空間計算量はO(1)
sliding window
two pointersに似ているがsliding windowはスライス内の特定の範囲に着目し、範囲をずらして比較するを繰り返すアルゴリズムです。
例えばスライスの中n個の部分スライスの和の最大を求めるコードを考える。
func maxSubarraySum(array []int, n int) int {
// nがスライスの長さよりも大きければ0で終了
if n > len(array) {
return 0
}
maxSum := 0 // 求めたい最大の和
tempSum := 0 // n要素のスライスの要素の和
// 0からn-1番目までの要素の和を求める
for i := 0; i < n; i++ {
maxSum += array[i]
}
tempSum = maxSum
for i := n; i < len(array); i++ {
// i-n番目の要素を引いてi番目を足せば次の部分スライスの我が求められる
tempSum = tempSum - array[i-n] + array[i]
maxSum = max(maxSum, tempSum)
}
return maxSum
}
func max(x int, y int) int {
if x < y {
return y
}
return x
}
時間計算量は**O(N)で空間計算量はO(1)**となる。
stack
Stackは最後に入れた要素が最初に取り出されるデータ構造。
LIFO(Last In First Out)ともいわれる。
例えばコードを書いているときに括弧の個数が間違っていないかを判定するときに使える。
与えられた文字列のうち{}, [], ()の対応が正しいかを判定するコードを考えてみます。
文字の種類は{}[]()のいずれかのみとします
func isValid(s string) bool {
// それぞれの括弧閉じるの対応する括弧開けるをmapで定義しておく
pairs := map[byte]byte{
'}': '{',
']': '[',
')': '(',
}
// stackを定義。今回はスライスで行う。
stack := make([]byte, 0)
for _, char := range []byte(s) {
// 文字が閉じ括弧でない場合、スタックに追加する
pair, ok := pairs[char]
if !ok {
stack = append(stack, char)
continue
}
// スタックが空である場合は無効な括弧の組み合わせのためfalseを返す
if len(stack) == 0 {
return false
}
// スタックの最後の要素が対応する開き括弧でない場合は無効な括弧の組み合わせのためfalseを返す
if stack[len(stack) - 1] != pair {
return false
}
// スタックの最後の要素が対応する開き括弧である場合、その要素をスタックから削除
stack = stack[:len(stack) - 1]
}
// スタックが空であればすべての括弧が正しくペアになっているためtrue
// スタックが空でない場合、一部の開き括弧に対応する閉じ括弧がないためfalseを返す
return len(stack) == 0
}
このようにすると()[]{}はtrue、([)]はfalseが帰るようになります。
sの文字列の長さをNとすると、時間計算量はO(N)、空間計算量は**O(N)**となる
Queue
Queueは最初に入れられた要素が最初に取り出されるデータ構造。
FIFO(First In First Out)と呼ばれることもあり、Stackとよく対比される。
使い所はtreeのBFS(Breadth First Search)で処理を行いたいとき。
以下の二分木を考える。
1
/ \
2 3
/ \ / \
4 5 6 7
各要素をnodeと称するが、nodeは左右に別のnodeへのアクセスができるとする。
例えば1の要素はleftは2、rightは3といったデータ構造になる。
これを1, 2, 3, ..., 7と順番に処理をしたいときのコードは以下のようになる。
type node struct {
val int
left *node
right *node
}
func bfs(root *node) []int {
if root == nil {
return []int{}
}
// nodeのポインタのqueueを作成
queue := []*node{root}
result := make([]int, 0)
for len(queue) > 0 {
// dequeue
// queueの先頭要素を取得
current := queue[0]
// queueの先頭要素を削除
queue = queue[1:]
result = append(result, current.val)
// enqueue
if current.left != nil {
queue = append(queue, current.left)
}
if current.right != nil {
queue = append(queue, current.right)
}
}
return result
}
func main() {
root := &node{val: 1}
root.left = &node{val: 2}
root.right = &node{val: 3}
root.left.left = &node{val: 4}
root.left.right = &node{val: 5}
root.right.left = &node{val: 6}
root.right.right = &node{val: 7}
fmt.Println(bfs(root))
}
先頭の要素を取得して削除する行為をdequeue, 末尾に要素を挿入する行為をenqueueと言う。
Nをnode数として
- 時間計算量は二分木の各ノードを一度だけ訪問するのみのため時間計算量はO(N)
- 空間計算量はキューとしてスライスを使用し、最悪の場合（すべてのノードが同じレベルにある場合）、スライスの長さはノード数と同じになるため空間計算量はO(N)
Binary Search
Binary Searchはソート済みの配列に対してターゲットとなる要素を取り出すアルゴリズム。
intのスライスの中にtargetがあるかを判定し、存在すればtargetを、存在しなければ-1を返す関数を考える。
func search(nums []int, target int) int {
left, right := 0, len(nums) - 1
for left <= right {
// 中央をmidとして取得
mid := (left + right) / 2
if nums[mid] > target {
// ターゲットがmidよりも小さい場合は左側にスコープを絞る
right = mid - 1
} else if nums[mid] < target {
// ターゲットがmidよりも大きい場合は右側にスコープを絞る
left = mid + 1
} else {
// targetと同じならmidを返す
return mid
}
}
return -1
}
numsの長さをNとすると
-
時間計算量：二分探索は各ステップで探索範囲を半分に狭めるためO(log N)
-
空間計算量：left、right、midの3つの変数のみ使うためO(1)
Linked List
日本語では連結リストで、各データが一つ前もしくは一つ後ろへの参照情報を持つデータ構造。
ここでは一つ後ろへの参照情報を持つ連結リストを反転させる処理を書く。
再帰を利用するパターンとloopを利用するパターン両方書いてみる。
type linkedListNode struct {
Val int
Next *linkedListNode
}
// Recursive version
func reverseListRecursive(head *linkedListNode) *linkedListNode {
if head == nil || head.Next == nil {
return head
}
// headの次を変数として再帰的に処理した結果を変数として保持
reversedListHead := reverseListRecursive(head.Next)
// 反転する処理
head.Next.Next = head
head.Next = nil
return reversedListHead
}
// Iterative version
func reverseListIterative(head *linkedListNode) *linkedListNode {
// 現在のnodeと一つ前のnodeを変数として保持
var prev *linkedListNode
curr := head
for curr != nil {
// 元々の一つ後の要素を保持
tmp := curr.Next
// 反転する処理
curr.Next = prev
prev = curr
curr = tmp
}
return prev
}
リストの個数をNとして計算量について
- 再帰
- 時間計算量はO(N)
- 空間計算量は再帰を使用して全ノードが再帰スタックにプッシュされるためO(N)
- イテレーション
- 時間計算量はO(N)
- 空間計算量はprev、curr、tmpの3つの変数のみ利用するためO(1)
backtrack
ある問題を解くときに仮に一つの部分解を設定し、残りの問題を解く。
解が見つかった場合は正式に解のひとつとして採用し、解がない場合は棄却する。
文字で書くと難しいので例題とコードで見てみよう。
ある配列の部分要素を全て求めたいとする。
例えば[1, 2, 3]は[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]と8通りとなるが関数を書いて見てみる。
func subsets(nums []int) [][]int {
ans := make([][]int, 0)
curr := make([]int, 0)
var backtrack func(idx int)
backtrack = func(idx int) {
ans = append(ans, append([]int{}, curr...))
if idx == len(nums) {
return
}
for i := idx; i < len(nums); i++ {
// nums[i]が含まれるパターン
curr = append(curr, nums[i])
backtrack(i + 1)
// nums[i]が含まれないパターン
curr = curr[:len(curr)-1]
}
}
backtrack(0)
return ans
}
配列の要素数をNとすると計算量について
-
時間計算量は部分集合の数は2^NのためO(2^N)
-
空間計算量は部分集合の数は2^NのためO(2^N)
まとめ
ここまで学んだアルゴリズムとデータ構造について例題とコードで説明してきた。
この他にもDP、貪欲法、Heapなど様々学習すべきものがあるので、引き続き理解して効率の良いエンジニアリングライフを！