[Go]スライスの破壊的なソート, 非破壊的なソート

概要

golangでは標準で破壊的なソートをする関数が用意されているが、非破壊的なソートをする手段は用意されていないため、自前で実装する必要がある。この記事では、それぞれの実装コードを例示する。

破壊的ソート(sort.Slice())

golangでスライスをソートする際には、標準パッケージの関数sort.Slice(x any, less func(i, j int) bool)を使う。

sample.go

package main

import (
	"fmt"
	"sort"
)

// sampleStruct スライスの要素の型となる構造体
type sampleStruct struct {
	a int
}

// String サンプルコード内でのPrintf()でのキレイな出力用に定義してるだけ
func (s *sampleStruct) String() string {
	return fmt.Sprintf("{a: %d}", s.a)
}

func main() {
	sampleStructs := []*sampleStruct{
		{a: 1}, {a: 3}, {a: 2},
	}

	// ソート前
	fmt.Printf("[before sort]sampleStructs address: %p values: %+v\n", sampleStructs, sampleStructs)

	// フィールドaの昇順で破壊的にソート
	sort.Slice(sampleStructs, func(i, j int) bool {
		return sampleStructs[i].a < sampleStructs[j].a
	})

	// ソート後
	fmt.Printf("[after sort]sampleStructs address: %p values: %+v\n", sampleStructs, sampleStructs)
}

注意すべきは、本メソッドが破壊的なソートである点。
ソートを実行したスライスについて、ソート実行前の状態が失われてしまう。

[before sort]sampleStructs address: 0xc00011a000 values: [{a: 1} {a: 3} {a: 2}]
[after sort]sampleStructs address: 0xc00011a000 values: [{a: 1} {a: 2} {a: 3}]

非破壊的ソート

非破壊的にソートする関数・メソッドは標準では用意されていないため、
自前でソート対象のスライスをコピーして別インスタンスにする→sort.Slice()を実行する
というようにしなければならない。

sample.go

package main

import (
	"fmt"
	"sort"
)

// sampleStruct スライスの要素の型となる構造体
type sampleStruct struct {
	a int
}

// String サンプルコード内でのPrintf()でのキレイな出力用に定義してるだけ
func (s *sampleStruct) String() string {
	return fmt.Sprintf("{a: %d}", s.a)
}

func main() {
	sampleStructs := sampleStructs{
		{a: 1}, {a: 3}, {a: 2},
	}

	// ソート前
	fmt.Printf("[before sort]sampleStructs address: %p values: %+v\n", sampleStructs, sampleStructs)

	// フィールドaの昇順で非破壊的にソート
	sortedStructs := make([]*sampleStruct, len(sampleStructs))
	copy(sortedStructs, sampleStructs)
	sort.Slice(sortedStructs, func(i, j int) bool {
		return sortedStructs[i].a < sortedStructs[j].a
	})

	// ソート後
	fmt.Printf("[after sort]sampleStructs address: %p values: %+v\n", sampleStructs, sampleStructs)
	fmt.Printf("[after sort]sortedStructs address: %p values: %+v\n", sortedStructs, sortedStructs)
}

出力結果

[before sort]sampleStructs address: 0xc000010018 values: [{a: 1} {a: 3} {a: 2}]
[after sort]sampleStructs address: 0xc000010018 values: [{a: 1} {a: 3} {a: 2}]
[after sort]sortedStructs address: 0xc000010060 values: [{a: 1} {a: 2} {a: 3}]

オブジェクト指向的にちゃんと実装するならば、ソート対象のスライス要素に対するファーストクラスコレクションを定義し、その非破壊的なソートをするメソッドを実装してあげるとすっきりして使い勝手がよさげである。
※sortedというメソッド名はpythonの非破壊的なソートをする組み込み関数から取った。

sample.go

package main

import (
	"fmt"
	"sort"
)

// sampleStruct スライスの要素の型となる構造体
type sampleStruct struct {
	a int
}

// String サンプルコード内でのPrintf()でのキレイな出力用に定義してるだけ
func (s *sampleStruct) String() string {
	return fmt.Sprintf("{a: %d}", s.a)
}

// sampleStructs sampleStructのファーストクラスコレクション
type sampleStructs []*sampleStruct

// sorted 非破壊的にソート
func (s sampleStructs) sorted(less func(i, j int) bool) sampleStructs {
	copiedStructs := make(sampleStructs, len(s))
	copy(copiedStructs, s)

	sort.Slice(copiedStructs, less)
	return copiedStructs
}

func main() {
	sampleStructs := sampleStructs{
		{a: 1}, {a: 3}, {a: 2},
	}

	// ソート前
	fmt.Printf("[before sort]sampleStructs address: %p values: %+v\n", sampleStructs, sampleStructs)

	// フィールドaの昇順で非破壊的にソート
	sortedStructs := sampleStructs.sorted(func(i, j int) bool {
		return sampleStructs[i].a < sampleStructs[j].a
	})

	// ソート後
	fmt.Printf("[after sort]sampleStructs address: %p values: %+v\n", sampleStructs, sampleStructs)
	fmt.Printf("[after sort]sortedStructs address: %p values: %+v\n", sortedStructs, sortedStructs)
}

出力結果

[before sort]sampleStructs address: 0xc000010018 values: [{a: 1} {a: 3} {a: 2}]
[after sort]sampleStructs address: 0xc000010018 values: [{a: 1} {a: 3} {a: 2}]
[after sort]sortedStructs address: 0xc000010060 values: [{a: 1} {a: 2} {a: 3}]