go で algorithm : map/reduce/filter

はじめに

go で競プロを始める前の肩慣らしとして基本的なデータ構造、アルゴリズムを復習します。
今回は go でシンプルな map/reduce/filter を実装します。

github.com

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 を実装しました。

参考
お気楽 Go 言語プログラミング入門