メモ

.gitignore

**/.*.swp

1-1-bi-list.go

package memo_dokusyo

type BiList struct {
	Next  *BiList
	Prev  *BiList
	Value int
}

func (list *BiList) Insert(data int) *BiList {
	var next BiList
	next.Value = data
	next.Next = list.Next
	next.Prev = list
	list.Next = &next
	return &next
}

func (list *BiList) Remove() *BiList {
	list.Prev.Next = list.Next
	list.Next.Prev = list.Prev
	return list.Prev
}

func RemoveBy(head *BiList, tail *BiList, value int) {
	for it := head; it != nil; it = it.Next {
		if it.Value == value {
			it = it.Remove()
		}
	}
}

1-1-bi-list_test.go

package memo_dokusyo

import (
	"fmt"
	"testing"
)

func TestBiList(t *testing.T) {
	// 元データ
	A := []int{
		1,
		2,
		3,
		4,
		5,
		6,
		7,
		8,
		9,
		10,
	}

	// リストにデータを追加
	var first_element BiList
	first_element.Value = A[0]
	head := &first_element
	tail := head
	for _, element := range A[1:] {
		tail = tail.Insert(element)
	}

	// 表示（削除前）
	for it := head; it != nil; it = it.Next {
		fmt.Printf("value = %d\n", it.Value)
	}
	fmt.Printf("\n")

	// 3, 6を削除する
	RemoveBy(head, tail, 3)
	RemoveBy(head, tail, 6)

	// 表示（削除後）
	for it := head; it != nil; it = it.Next {
		fmt.Printf("value = %d\n", it.Value)
	}
	fmt.Printf("\n")
}

1-1-binary-tree.go

package memo_dokusyo

import (
	"fmt"
	"strings"
)

// 二分木の頂点
type Node struct {
	Left  *Node
	Right *Node
	Value int
}

func (node *Node) SetLeft(left_value int) *Node {
	var child Node
	child.Value = left_value
	node.Left = &child
	return &child
}

func (node *Node) SetRight(right_value int) *Node {
	var child Node
	child.Value = right_value
	node.Right = &child
	return &child
}

func (node *Node) Print(indent int) {
	fmt.Printf("%svalue = %d\n", strings.Repeat(" ", indent), node.Value)
	if node.Left != nil {
		fmt.Printf("%sleft:\n", strings.Repeat(" ", indent))
		node.Left.Print(indent + 4)
	}
	if node.Right != nil {
		fmt.Printf("%sright:\n", strings.Repeat(" ", indent))
		node.Right.Print(indent + 4)
	}
}

1-1-binary-tree_test.go

package memo_dokusyo

import (
	"testing"
)

func TestBinaryTree(t *testing.T) {
	var root Node
	root.Value = 1
	left_child := root.SetLeft(2)
	root.SetRight(3)
	left_child.SetLeft(4)
	left_child.SetRight(5)

	root.Print(0)
}

1-1-list.go

package memo_dokusyo

// ポインタを使ったリスト構造の実装
type List struct {
	Value int
	Next  *List
}

1-1-list_test.go

package memo_dokusyo

import (
	"fmt"
	"testing"
)

func TestList(t *testing.T) {
	// 元データ
	A := []int{
		1,
		2,
		3,
		4,
		5,
		6,
		7,
		8,
		9,
		10,
	}

	// リストをつくる
	var root List
	p := &root
	for i := 0; i < len(A); i++ {
		p.Value = A[i]
		if i+1 < len(A) {
			var next List
			p.Next = &next
			p = &next
		}
	}

	// データを表示する
	p = &root
	for p != nil {
		fmt.Printf("value = %4d\n", p.Value)
		p = p.Next
	}
}

1-1-queue.go

package memo_dokusyo

import (
	"container/list"
)

// キューの実装
type Queue struct {
	List *list.List
}

func (queue *Queue) Push(data int) {
	queue.List.PushBack(data)
}

func (queue *Queue) Pop() {
	queue.List.Remove(queue.List.Front())
}

func (queue *Queue) Front() int {
	return queue.List.Front().Value.(int)
}

func (queue *Queue) Back() int {
	return queue.List.Back().Value.(int)
}

func (queue *Queue) Empty() bool {
	return queue.List.Len() == 0
}

1-1-queue_test.go

package memo_dokusyo

import (
	"container/list"
	"fmt"
	"testing"
)

func TestQueue(t *testing.T) {
	queue := Queue{list.New()}
	queue.Push(1)
	queue.Push(2)
	queue.Push(3)

	// 空になるまで取り出す
	for !queue.Empty() {
		fmt.Printf("value = %4d\n", queue.Front())
		queue.Pop()
	}
}

1-1-stack.go

package memo_dokusyo

import (
	"container/list"
)

// スタックの実装
type Stack struct {
	List *list.List
}

func (stack *Stack) Push(data int) {
	stack.List.PushBack(data)
}

func (stack *Stack) Top() int {
	return stack.List.Back().Value.(int)
}

func (stack *Stack) Pop() {
	stack.List.Remove(stack.List.Back())
}

func (stack *Stack) Empty() bool {
	return stack.List.Len() == 0
}

1-1-stack_test.go

package memo_dokusyo

import (
	"container/list"
	"fmt"
	"testing"
)

func TestStack(t *testing.T) {
	stack := Stack{list.New()}
	stack.Push(1)
	stack.Push(2)
	stack.Push(3)

	// 空になるまで取り出す
	for !stack.Empty() {
		fmt.Printf("value = %4d\n", stack.Top())
		stack.Pop()
	}
}

1-2-quicksort.go

package memo_dokusyo

import (
	"fmt"
)

func quick_sort_split(A []int, l int, r int, mid int) int {
	i := l
	j := r
	pivot := A[mid]
	for i < j {
		for A[i] < pivot {
			i++
		}
		for pivot < A[j] {
			j--
		}
		if i < j {
			A[i], A[j] = A[j], A[i]
		}
	}
	return j
}

// [l, r]を並べ替える
func quick_sort_func(A []int, l int, r int) {
	if l < r {
		mid := (l + r) / 2
		fmt.Printf("@quick_sort_func: l = %d, r = %d, mid = %d,%d\n", l, r, mid, A[mid])
		fmt.Printf("  @quick_sort_func: A = %s\n", A[l:r+1])
		mid = quick_sort_split(A, l, r, mid)
		fmt.Printf("@quick_sort_func: l = %d, r = %d, mid = %d,%d\n", l, r, mid, A[mid])
		quick_sort_func(A, l, mid-1)
		quick_sort_func(A, mid+1, r)
	}
}

func QuickSort(A []int) {
	quick_sort_func(A, 0, len(A)-1)
}

1-2-quicksort_test.go

package memo_dokusyo

import (
	"fmt"
	"testing"
)

func TestQuickSort(t *testing.T) {
	A := []int{4, 6, 3, 2, 1, 7, 9, 8, 5}
	QuickSort(A)
	for _, element := range A {
		fmt.Printf("%d, ", element)
	}
}

1-3-strassen.go

package memo_dokusyo

import (
	"bufio"
	"fmt"
)

type Matrix struct {
	N    int
	Data [][]int
}

func (mat *Matrix) Init() {
	mat.Data = make([][]int, mat.N, mat.N)
	for i := 0; i < mat.N; i++ {
		mat.Data[i] = make([]int, mat.N)
	}
	for i := 0; i < mat.N; i++ {
		for j := 0; j < mat.N; j++ {
			mat.Data[i][j] = 0
		}
	}
}

func (mat *Matrix) Set(i int, j int, value int) {
	mat.Data[i][j] = value
}

func (mat Matrix) Get(i int, j int) int {
	return mat.Data[i][j]
}

func (mat Matrix) GetSubMatrix(sr int, sc int, n int) Matrix {
	var res Matrix
	res.N = n
	res.Init()
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			res.Set(i, j, mat.Get(sr+i, sc+j))
		}
	}
	return res
}

func (mat Matrix) Print() {
	for i := 0; i < mat.N; i++ {
		fmt.Printf("%4d\n", mat.Data[i])
	}
	fmt.Printf("\n")
}

func (mat *Matrix) Input(reader *bufio.Reader) {
	for i := 0; i < mat.N; i++ {
		for j := 0; j < mat.N; j++ {
			fmt.Fscanf(reader, "%d", &mat.Data[i][j])
		}
		reader.ReadString('\n')
	}
}

func input_matrix(reader *bufio.Reader, n int) Matrix {
	var res Matrix
	res.N = n
	res.Init()
	res.Input(reader)
	return res
}

func matrix_mul_naive(A Matrix, B Matrix) Matrix {
	var res Matrix
	n := A.N
	res.N = n
	res.Init()
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			for k := 0; k < n; k++ {
				res.Set(i, k, res.Get(i, k)+A.Get(i, j)*B.Get(j, k))
			}
		}
	}
	return res
}

func make_matrix_matrix(n int) [][]Matrix {
	res := make([][]Matrix, n, n)
	for i := 0; i < n; i++ {
		res[i] = make([]Matrix, n)
	}
	return res
}

// n*n行列同士の積を求める(n = 2^k)
func matrix_mul(A Matrix, B Matrix) Matrix {
	n := A.N

	if n > 2 {
		m := n / 2

		a_sub := make_matrix_matrix(2)
		for i := 0; i < 2; i++ {
			for j := 0; j < 2; j++ {
				a_sub[i][j] = A.GetSubMatrix(i*m, j*m, m)
			}
		}

		b_sub := make_matrix_matrix(2)
		for i := 0; i < 2; i++ {
			for j := 0; j < 2; j++ {
				b_sub[i][j] = B.GetSubMatrix(i*m, j*m, m)
			}
		}

		M1 := matrix_mul(matrix_sub(a_sub[0][1], a_sub[1][1]), matrix_add(b_sub[1][0], b_sub[1][1]))
		M2 := matrix_mul(matrix_add(a_sub[0][0], a_sub[1][1]), matrix_add(b_sub[0][0], b_sub[1][1]))
		M3 := matrix_mul(matrix_sub(a_sub[0][0], a_sub[1][0]), matrix_add(b_sub[0][0], b_sub[0][1]))
		M4 := matrix_mul(matrix_add(a_sub[0][0], a_sub[0][1]), b_sub[1][1])
		M5 := matrix_mul(a_sub[0][0], matrix_sub(b_sub[0][1], b_sub[1][1]))
		M6 := matrix_mul(a_sub[1][1], matrix_sub(b_sub[1][0], b_sub[0][0]))
		M7 := matrix_mul(matrix_add(a_sub[1][0], a_sub[1][1]), b_sub[0][0])

		C := make_matrix_matrix(m)

		C[0][0] = M1
		C[0][0] = matrix_add(C[0][0], M2)
		C[0][0] = matrix_sub(C[0][0], M4)
		C[0][0] = matrix_add(C[0][0], M6)

		C[0][1] = M4
		C[0][1] = matrix_add(C[0][1], M5)

		C[1][0] = M6
		C[1][0] = matrix_add(C[1][0], M7)

		C[1][1] = M2
		C[1][1] = matrix_sub(C[1][1], M3)
		C[1][1] = matrix_add(C[1][1], M5)
		C[1][1] = matrix_sub(C[1][1], M7)

		var res Matrix
		res.N = n
		res.Init()

		for i := 0; i < 2; i++ {
			for j := 0; j < 2; j++ {
				for r := 0; r < m; r++ {
					for c := 0; c < m; c++ {
						res.Set(i*m+r, j*m+c, C[i][j].Get(r, c))
					}
				}
			}
		}

		return res
	} else {
		return matrix_mul_naive(A, B)
	}
}

func matrix_add(A Matrix, B Matrix) Matrix {
	var res Matrix
	n := A.N
	res.N = n
	res.Init()
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			res.Set(i, j, A.Get(i, j)+B.Get(i, j))
		}
	}
	return res
}

func matrix_sub(A Matrix, B Matrix) Matrix {
	var res Matrix
	n := A.N
	res.N = n
	res.Init()
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			res.Set(i, j, A.Get(i, j)-B.Get(i, j))
		}
	}
	return res
}

1-3-strassen.input.txt

4
1 2 3 6
2 1 4 7
3 2 1 7
4 2 3 4
3 1 1 2
2 2 4 2
7 3 4 3
5 5 5 5
8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8

1-3-strassen_test.go

package memo_dokusyo

import (
	"bufio"
	"fmt"
	"os"
	"testing"
)

func TestStrassen(t *testing.T) {
	file, _ := os.Open("1-3-strassen.input.txt")
	reader := bufio.NewReader(file)
	var n int
	for {
		terms, error := fmt.Fscanf(reader, "%d", &n)
		if terms == 0 || error != nil {
			break
		}
		reader.ReadString('\n')
		fmt.Printf("n = %d\n", n)

		mat_A := input_matrix(reader, n)
		fmt.Printf("Matrix A:\n")
		mat_A.Print()
		mat_B := input_matrix(reader, n)
		fmt.Printf("Matrix B:\n")
		mat_B.Print()

		mat_C := matrix_mul_naive(mat_A, mat_B)
		fmt.Printf("Matrix C:\n")
		mat_C.Print()

		mat_D := matrix_mul(mat_A, mat_B)
		fmt.Printf("Matrix D:\n")
		mat_D.Print()
	}
}

README.md

目標: 大人の読書をしよう

• 10ページ単位で進める
• 読んだページ数はStudyplusで記録
• gistにメモ
  • 数式は![test](http://latex.codecogs.com/svg.latex?1%2Bsin%28x%29)
  • URLのエンコード: http://www.url-encode-decode.com/urlencode

iwanami-basic-algorithm-2013-08-06-03-23.md

1-1. データの表現

• 初歩的なデータ構造（1次元のリスト, 木, 二分木）の説明
• ポインタを使ったリスト構造
  • サンプルコード
• スタック
  • 配列の片方だけで要素の追加や削除ができるもの
  • 各操作は要素数に関係しない一定の時間で実行できる
  • サンプルコード
• キュー
  • 配列の片方で追加、もう片方で削除ができるもの
  • サンプルコード
• 双方向リスト
  • 前後の要素へのポインタをもたせたリスト
  • サンプルコード
• 木の定義
  • 再帰的に
  • ある要素以外の要素の集合が分割されて、各部分がまた木をなしている
  • 根, 部分木
  • 各要素を頂点、節点
  • 頂点の親子関係
  • 葉: 子要素を持たない頂点
  • 高さ: 根要素までの距離
  • 森: 木の集合
  • 有向グラフ
• 二分木の定義
  • 有限個の集合Bが要素b[r](根)と左側B[L]と右側B[R]に分割されていて、B[L]とB[R]が各々再び二分木をなしている
  • 頂点数nと高さhの関係
    • 
      • 
  • サンプルコード

iwanami-basic-algorithm-2013-08-07-14-05.md

1-2 再帰呼び出し

• 何らかの手続きを実行するときに自分自身を再び呼び出す
• 例題
  • 整列問題
    • 複数の実数が与えられたとき、それを大きさ順に並べる
    • クイックソート
      • 標本となる、ある要素sについて、それより小さい部分と大きい部分に分ける
      • 分けられた部分が十分に小さくなるまで再帰的に操作を繰り返す
      • サンプルコード

1-3 算法と計算量

• アルゴリズムの性能
  • 計算時間の長さ
  • 記憶領域の大きさ
• 入力xに対して、その大きさsize(x)を適当に定義する
• クイックソート
  • size(x) = 要素数n とする
• 行列積の問題
  • 実数を要素とするnnの2つの行列A, Bが与えられて、その積C=ABを求める問題
  • size(x) = 行列の大きさn とする
    • 実際には2*n^2個のデータがある
• 入力の大きさごとに最悪の場合に要する量を測ったりする
  • 最大時間計算量
    • 計算時間のうち最大のもの
  • 最大記憶領域計算量
    • 必要な記憶領域で最大のもの
• 平均
  • ある大きさの入力の順列ごとに測った量の和をその順列の個数で割る

iwanami-basic-algorithm-2013-08-09-17-18.md

1-3. 算法と計算量

• クイックソートの計算量について
  • 要素の比較回数で計算量T(n)を定義してみる
  • 単位として選んだ演算だけを考える
  • 抽象的な計算モデルの上でアルゴリズムが実行されるものとする考え方
  • 評価方法
    • 計算量T(n)がnの増加にしたがって、どのような様子で増加していくか
    • O-記法
      • ある関数f(n)に対して、計算量T(n)がO(f(n))であるとは、任意のn(>=m)に対して、T(n)<=cf(n)であること
      • c, mは適当に選んだ定数
      • f(n)はT(n)の上界とよばれる
      • できるだけ増加の様子をよく表すシンプルな関数を使う
• 行列積の問題の例
  • 単純なアルゴリズム
    • O(n^3)
  • Strassenのアルゴリズム
    • O(n^log(7))
    • n = 2^p (p >= 1) と仮定する
      • nnの行列A, B, Cをそれぞれn/2n/2の行列A[i][j], B[i][j], C[i][j]に分割する(i, j = 1, 2)
        • 分割後の各部分行列について、再帰的に計算を繰り返すことで答えを求める
    • サンプルコード
• 整列問題の例
  • 一般的に、能率の良いアルゴリズムをみつけることは、その問題を解くための計算量の上界を改良すること
  • 下界: 最低必要とする計算量
  • 下界に一致する上界を計算量に持つアルゴリズムは最適ということになる
  • クイックソートの解析
    • 平均時間計算量E(n)
    • 入力データとして、(1, 2, ..., n)の順列の1つがランダムに与えられたとする
      • pivotとして選んだ要素の行き先はn通りの候補のうち、どれも等確率で起こる
      • pivotによって分割された2つのグループは、各々再びランダムに並んでいる
    • 実行される比較回数の期待値E(n)
      • 
        • E(0) = E(1) = 0, E(2) = 3
        • 
        • 
        •