go で algorithm : map/reduce/filter
はじめに
go で競プロを始める前の肩慣らしとして基本的なデータ構造、アルゴリズムを復習します。
今回は go でシンプルな map/reduce/filter を実装します。
go で map(写像)
配列の各要素に対して処理をしたのち配列を返す関数です。
package main import ( "fmt" ) func square(x int) int { return x * x } func Mapping(f func(int) int, array []int) []int { buff := make([]int, len(array)) for i, v := range array { buff[i] = f(v) } return buff } func main() { a := []int{1, 2, 3} got := Mapping(square, a) fmt.Println(got) // [1 4 9] }
テストも書くくせをつけます。
package main import ( "reflect" "testing" ) func TestMapping(t *testing.T) { tests := []struct { input []int want []int }{ {input: []int{}, want: []int{}}, {input: []int{1, 2}, want: []int{1, 4}}, {input: []int{1, 2, 3}, want: []int{1, 4, 9}}, } for _, test := range tests { got := Mapping(square, test.input) if !reflect.DeepEqual(got, test.want) { t.Fatalf("\n want: %v, \n actual: %v", test.want, got) } } }
go で reduce(畳み込み)
配列に対して処理をする関数です。
初期値を与えることもできます。
package main import "fmt" func add(x, y int) int { return x + y } func Reduce(f func(int, int) int, a int, ary []int) int { for _, x := range ary { a = f(a, x) } return a } func main() { a := []int{1, 2, 3, 4, 5} fmt.Println(Reduce(add, 1, a)) // 16 }
reduce のテストはこちらです。
package main import ( "reflect" "testing" ) func TestReduce(t *testing.T) { tests := []struct { input []int init int want int }{ {input: []int{}, init: 0, want: 0}, {input: []int{1, 2, 3}, init: 0, want: 6}, {input: []int{1, 2, 3, 4, 5}, init: 1, want: 161}, } for _, test := range tests { got := Reduce(add, test.init, test.input) if !reflect.DeepEqual(got, test.want) { t.Fatalf("\n want: %v, \n actual: %v", test.want, got) } } }
go で filter
配列の各要素に対して条件にマッチした要素を配列にして返す関数です。
package main import "fmt" func isEven(x int) bool { return x%2 == 0 } func isOdd(x int) bool { return x%2 != 0 } func Filter(f func(int) bool, ary []int) []int { buff := make([]int, 0) for _, v := range ary { if f(v) { buff = append(buff, v) } } return buff } func main() { a := []int{1, 2, 3, 4, 5} got := Filter(isEven, a) fmt.Println(got) // [2, 4] }
filter のテストはこちらです。
package main import ( "reflect" "testing" ) func TestFilter(t *testing.T) { tests := []struct { input []int want []int }{ {input: []int{1, 2}, want: []int{2}}, {input: []int{1, 2, 3, 4, 5}, want: []int{2, 4}}, {input: []int{}, want: []int{}}, } for _, test := range tests { got := Filter(isEven, test.input) if !reflect.DeepEqual(got, test.want) { t.Fatalf("\n want: %v, \n actual: %v", test.want, got) } } }
まとめ
go で シンプルな map/reduce/filter を実装しました。