Software Engineer Blog

エンジニアブログです。技術情報(Go/TypeScript/k8s)や趣味の話も書くかもです。

GolangのSort処理について

Golang

GolangのSort処理

GolangのSort処理について、まとめました。
(// package sort と記載があるサンプルコードは、Golang本体のソースコードです)

Sort

Sort Interface

Golangでは、structのソートを行うため、sort.Interfaceを実装する必要があります。
(実際はGo1.8以降、下記の sort.Slice() を利用して、ソートすることができるようになりました。参考)

// sort.Interface
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)
}
メソッド 特徴
Len() int 配列・リストの要素数
Less(i, j int) bool i < j を満たすかの真偽値
Swap(i,j int) iとjの要素を入れ替える

Sortの方法

標準パッケージで対応している型は下記になります。

  • float64
  • int
  • string

ここでは、ソートの方法をint配列をもとにみていきます。

sort.Ints(a int[])

Ints() メソッドは、int[]型をソートするメソッドです。
これは、昇順(increacing)にソートされます。

nums := []int{4, 3, 2, 10, 8}
sort.Ints(nums)
fmt.Println(nums)

// output: [2 3 4 8 10]

内部では、 IntSlice 型のstructにつめかえを行い、Sort関数を呼んでいます。
(sort.Interfaceを実装するルールは同じ)

// package sort

// Ints sorts a slice of ints in increasing order.
func Ints(a []int) { Sort(IntSlice(a)) }


// IntSlice
// Len,Less,Swapを実装したstruct

// IntSlice attaches the methods of Interface to []int, sorting in increasing order.
type IntSlice []int

func (p IntSlice) Len() int           { return len(p) }
func (p IntSlice) Less(i, j int) bool { return p[i] < p[j] }
func (p IntSlice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }

sort.Reverse(data Interface) Inteface

Reverse(data Interface) は、sort.Interface型のソート方法を逆順に修正する関数です。
実際に内部で行っていることは、下記の２点です。

\1. reverse structにstructを詰め替える
reverse struct は、 sort.Interface を埋め込んでいます。

// package sort

type reverse struct {
    // This embedded Interface permits Reverse to use the methods of
    // another Interface implementation.
    Interface
}

// Reverse returns the reverse order for data.
func Reverse(data Interface) Interface {
    return &reverse{data}
}

\2. Lessメソッドの引数をスワップ
reverse struct は、実装を参照したところ、 Less(i,j int) bool のみを再実装しています。
これにより、比較条件を逆にすることで、逆順ソートを実現しています。

// Less returns the opposite of the embedded implementation's Less method.
func (r reverse) Less(i, j int) bool {
    return r.Interface.Less(j, i)
}

sort.Search(n int, f func(int) bool) int

nの長さの配列内でf()=true となる最小のindexを返却します。
→ 配列内で指定のvalueがあるかどうかを調べる関数です。

特徴

  • 条件を満たさなかった場合、nが返却
  • 一致を探すことも、ある数値以上の値を探すことも可能
  • binary search(二分探索)で検索
    • ソートされた配列に対して実行しないと正確な結果が返却されない
  • 下記はSearchのラッパー関数
    • func SearchFloat64s(a float64, x float64) int
    • func SearchInts(a int, x int) int
    • func SearchStrings(a []string, x string) int
// package sort

// binary sort の実装
func Search(n int, f func(int) bool) int {
    // Define f(-1) == false and f(n) == true.
    // Invariant: f(i-1) == false, f(j) == true.
    i, j := 0, n
    for i < j {
        h := i + (j-i)/2 // avoid overflow when computing h
        // i ≤ h < j
        if !f(h) {
            i = h + 1 // preserves f(i-1) == false
        } else {
            j = h // preserves f(j) == true
        }
    }
    // i == j, f(i-1) == false, and f(j) (= f(i)) == true  =>  answer is i.
    return i
}

// Int ラッパー関数
func SearchInts(a []int, x int) int {
    return Search(len(a), func(i int) bool { return a[i] >= x })
}

利用サンプル

nums := []int{4, 3, 2, 10, 8}
x := 8

// 事前にソートしておく
sort.Ints(nums)
// search asc
index = sort.Search(len(nums), func(i int) bool {
  return nums[i] >= x
})

if index < len(nums) && nums[index] == x {
  // nums[index] = 8 = x
} else {
  // x は nums[]中に存在しなかった
  // だが、indexはnums[]の中にxをインサートする位置にある
}

sort.Slice(slice interface{}, less func(i, j int) bool)

渡したsliceを、ソートする関数。
less関数で定義された順にソートされる。

特徴

  • Go1.8以上
  • sort.Interfaceを実装していなくてもソートが可能となっている
  • stable sort(安定ソート)を保証していない
    • sort.SliceStableを利用することで保証される

(参考)実際のソート処理の中身について

sort.Sort(data sort.Interface) は渡されるデータによってソートの種別変えています。
流れとしては、基本的にクイックソートを利用して、条件を満たした際の他のソート手法に切り替わるといった挙動です。

  • ヒープソート
    • 条件: log(n+1)の整数値の2乗の深さとなった場合
      • 右に1ビットずつシフト演算して0になるまでの回数の2乗が最大の深さ(maxDepth)
      • maxDepthが0となったときに、ヒープソートに切り替わる
// package golang

// Switch to heapsort if depth of 2*ceil(lg(n+1)) is reached.

// package golang

// Use ShellSort for slices <= 12 elements

まとめ

Golangのsortパッケージについて、学びました。
実際のソート処理の中身までは、深く追求しませんでしたが、
ソートを行う利用方法については触れられたかなと思います。

参考

公式ドキュメント
golang の sort インタフェース難しい問題が解決した