sortパッケージから学ぶ汎用的なパッケージ作成

Goでソートを行うときにsortパッケージを活用すると思います。Goを使っている人はこのsortパッケージの実装を熟知してから、自分で新規パッケージを作成すると、汎用的に利用できるパッケージを作ることができるはずです。

モチベーション

コーディングインタビューの話ではないが自分が人のコードを読むとしたら「どういうレイヤー／パッケージ構成」にしているか、というのは設計力を測る一つの観点にしています。

coding interviewは好きじゃないけど、やるならこういうの出してみるかな〜ってのを仮で作ってみた。 https://t.co/gP7MkBCkd0
純粋に言語の習熟度とアルゴリズムの実装経験を測れる具合にしている。
— kaneshin (@kaneshin0120) September 15, 2018

shuffle package

sortパッケージを模倣するのに作成するのは要素のシャッフルを行うshuffleパッケージというのを作成して解説していこうと思います。

interfaceの提供

早速、サンプルとして下記のようなinterfaceをパッケージから提供し、Shuffle関数を用意することによってGoらしさが際立つと思います。

package shuffle

import (
    "math/rand"
    "time"
)

type Interface interface {
    Seed() int64
    Len() int
    Swap(int, int)
}

func Shuffle(data Interface) {
    rand.Seed(data.Seed())
    n := data.Len()
    for i := n - 1; i >= 0; i-- {
        j := rand.Intn(i + 1)
        data.Swap(i, j)
    }
}

// ... implemented more

github.com

※ sortパッケージにある sort#Slice のような関数は今回の話には含みません。

shuffle#Interface

一番重要なところですが、何かしらのアルゴリズムの情報操作を容易にするパッケージを作成したい場合、特に数値解析をしているときは下記のような型を用意しておくことによって、外部からでも柔軟に型が違ってもパッケージに見合う型でアルゴリズムを適用出来ることが可能です。

type Interface interface {
    Seed() int64
    Len() int
    Swap(int, int)
}

Function	Description
`Seed() int64`	シャッフルするときのシードを設定する
`Len() int`	シャッフルするコレクションの要素数
`Swap() (int, int)`	シャッフルする要素の入れ替え

このようなinterfaceを提供しておけば、import元のパッケージでは下記のように使用することができます。

package main

import (
    "fmt"
    "os"

    "github.com/kaneshin/playground/shuffle"
)

type Dice []int

func (d Dice) Seed() int64   { return int64(os.Getpid()) }
func (d Dice) Len() int      { return len(d) }
func (d Dice) Swap(i, j int) { d[i], d[j] = d[j], d[i] }

var dice = Dice([]int{1, 2, 3, 4, 5, 6})

func main() {
    fmt.Printf("%v\n", dice)
    shuffle.Shuffle(dice)
    fmt.Printf("%v\n", dice)
}

このような実装方法を理解しておけば、上記のような状況におけるジェネリクスは特段必要が無いということもわかりますね。

playground/main.go at master · kaneshin/playground · GitHub

shuffle#Shuffle

実際にアルゴリズムを適用するところですが、今回のサンプルはひとつのアルゴリズムに留まっていますが、ここで前処理や与えられている型からの情報からアルゴリズムの適用を変更することも可能です。

func Shuffle(data Interface) {
    rand.Seed(data.Seed())
    n := data.Len()
    for i := n - 1; i >= 0; i-- {
        j := rand.Intn(i + 1)
        data.Swap(i, j)
    }
}

特に、sortパッケージを読み込むと、コレクションの長さによってアルゴリズムを変更したりしています。

func quickSort(data Interface, a, b, maxDepth int) {
    for b-a > 12 { // Use ShellSort for slices <= 12 elements
        if maxDepth == 0 {
            heapSort(data, a, b)
            return
        }
        maxDepth--
        mlo, mhi := doPivot(data, a, b)
        // Avoiding recursion on the larger subproblem guarantees
        // a stack depth of at most lg(b-a).
        if mlo-a < b-mhi {
            quickSort(data, a, mlo, maxDepth)
            a = mhi // i.e., quickSort(data, mhi, b)
        } else {
            quickSort(data, mhi, b, maxDepth)
            b = mlo // i.e., quickSort(data, a, mlo)
        }
    }
    if b-a > 1 {
        // Do ShellSort pass with gap 6
        // It could be written in this simplified form cause b-a <= 12
        for i := a + 6; i < b; i++ {
            if data.Less(i, i-6) {
                data.Swap(i, i-6)
            }
        }
        insertionSort(data, a, b)
    }
}

// Sort sorts data.
// It makes one call to data.Len to determine n, and O(n*log(n)) calls to
// data.Less and data.Swap. The sort is not guaranteed to be stable.
func Sort(data Interface) {
    n := data.Len()
    quickSort(data, 0, n, maxDepth(n))
}

src/sort/sort.go - The Go Programming Language

sortパッケージに関して

先に、汎用的なパッケージ作成を解説しましたが、題材にあげているsortパッケージも解説します。

サンプルコード

Goの公式ページからの引用ですが、サンプルコードから解説したいと思います。

package main

import (
    "fmt"
    "sort"
)

type Person struct {
    Name string
    Age  int
}

func (p Person) String() string {
    return fmt.Sprintf("%s: %d", p.Name, p.Age)
}

type ByAge []Person

func (a ByAge) Len() int           { return len(a) }
func (a ByAge) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a ByAge) Less(i, j int) bool { return a[i].Age < a[j].Age }

func main() {
    people := []Person{
        {"Bob", 31},
        {"John", 42},
        {"Michael", 17},
        {"Jenny", 26},
    }

    fmt.Println(people)

    // ascending
    sort.Sort(ByAge(people))
    fmt.Println(people)

    // descending
    sort.Slice(people, func(i, j int) bool {
        return people[i].Age > people[j].Age
    })
    fmt.Println(people)

}

https://play.golang.org/p/LZgZi-s8IX-

非常にシンプルな形ですが、これだけでPerson.Ageによってソート処理を行うことができています。

sort#Interface

さて、どのようなinterfaceが定義されているのかですが、先ほど紹介したのと似たようにInterfaceという型が定義されており、それを満たした関数を定義したに過ぎません。

https://golang.org/pkg/sort/#Interface

// A type, typically a collection, that satisfies sort.Interface can be
// sorted by the routines in this package. The methods require that the
// elements of the collection be enumerated by an integer index.
type Interface interface {
    // Len is the number of elements in the collection.
    Len() int
    // Less reports whether the element with
    // index i should sort before the element with index j.
    Less(i, j int) bool
    // Swap swaps the elements with indexes i and j.
    Swap(i, j int)
}

Function	Description
`Len() int`	ソートするコレクションの要素数
`Less(int, int) bool`	ソートにおける要素の比較
`Swap() (int, int)`	ソートにおける要素の入れ替え

sort#Slice

上の方でも解説しましたが、場合によってはソート処理を行う前処理を行ったりしています。パッケージ内のI/Fを変更せずに内部アルゴリズムを変更するのは当たり前なんですが、とてもキレイな実装でもあるので、自身でコードを書くときも意識できると良いですね。

https://golang.org/pkg/sort/#Slice

おわりに

毎回、登壇するたびに話しているのですがGoでは自分の考えで実装するよりかも標準コードを読み込んでから実装をしていくことによって"Goらしさ"が発揮されます。なかなか良いコードが書けないと思っている方は、もっとGoの標準コードを読み込みましょう

Go開発のメンタリング

時々、「Goを自社に導入したいので導入する方法などのお話を聞きたい」などのお問い合わせが来るのでGoの技術支援をしています。何かあればTwitterまでご連絡ください。

よくあるのは下記の質問です。

どのようにAPIサーバーを作成すればよいか
Goらしさとは？
- パッケージ構成
- 社内での布教方法
- 初手は何から始めたほうがよいか

twitter.com

at kaneshin

Free space for me.