Go言語 スライスのSort & Unique

Go言語の配列? である「スライス」は、追加(Append関数)で容易にできるます。でも「並び替え」や「一部の削除」が、ちょっと面倒な操作が必要です。

並び替え(Sort)

SortStr

func SortStr(list []string) []string {
	var result []string
	var ix []int

	if len(list) == 0 {
		return result
	}

	ix = make([]int, len(list))
	for i := range list {
		ix[i] = i
	}

	for i := 0; i < len(list)-1; i++ {
		ii := ix[i]

		for j := i + 1; j < len(list); j++ {
			jj := ix[j]

			// sort
			if list[ii] > list[jj] {
				xx := ii
				ii = jj
				jj = xx

				ix[i] = ii
				ix[j] = jj
			}
		}
	}

	for i := range list {
		ii := ix[i]
		result = append(result, list[ii])
	}

	return result
}

SortStr関数の解説

並び替えは、一番 初歩的な「バブルソート」を使っています。

バブルソート

  for i := 0; i < len(list)-1; i++ {
    for j := i + 1; j < len(list); j++ {
       ...
    }
  }

バブルソートは、並び替えの際、頻繁に配列の中身を入れ替えるため、文字列の入れ替えは、かなりCPUやMemoryに負担をかけます。
そこで、配列の位置で索引を作り、索引を並び替えして、最後に索引順で、配列(スライス)を再構築して戻します。

この索引を使う方法は、データベースでは、一般的な方法です。この索引を応用すると、次の RemoveStr関数(Append関数の逆)も作れます。

RemoveStr

func RemoveStr(list []string, item ...string) []string {
	var result []string
	var ix []int

	if len(list) == 0 {
		return result
	}

	ix = make([]int, len(list))
	for i := range list {
		ix[i] = i
	}

	for i := range list {
		for j := range item {

			// remove
			if list[i] == item[j] {
				ix[i] = -1
			}
		}
	}

	for i := range list {
		ii := ix[i]
		if ii >= 0 {
			result = append(result, list[ii])
		}
	}

	return result
}

RemoveStr関数の解説

この引数2: itemの文字列と同じ値は、索引上で、-1に設定して、理論上 消して、配列(スライス)の再構築時に除外します。

RemoveStr関数の使い方

引数1: 元データの配列(スライス)
引数2: 削除したい、文字列のリスト(Go言語の可変引数 引数の一番末尾に固定される)

  list := []string{"Q","W","E","R","T","Y"}
  list = RemoveStr(list, "E","T")
  for i := range list {
    fmt.Printf("%v, ",list[i])
  }
  fmt.Println()

出力結果は、Q, W, R, Y, となる。

UniqueStr関数

RemoveStr関数のロジックを応用して、重複した文字列を削除します。

UniqueStr

func UniqStr(list []string, sort bool) []string {
	var result []string
	var ix []int

	if len(list) == 0 {
		return result
	}

	ix = make([]int, len(list))
	for i := range list {
		ix[i] = i
	}

	for i := 0; i < len(list)-1; i++ {
		ii := ix[i]
		if ii < 0 {
			continue
		}

		for j := i + 1; j < len(list); j++ {
			jj := ix[j]
			if jj < 0 {
				continue
			}

			// sort
			if sort {
				if list[ii] > list[jj] {
					xx := ii
					ii = jj
					jj = xx

					ix[i] = ii
					ix[j] = jj
				}
			}

			// remove
			if list[ii] == list[jj] {
				ix[j] = -1
			}
		}
	}

	for i := range list {
		ii := ix[i]
		if ii >= 0 {
			result = append(result, list[ii])
		}
	}

	return result
}

UniqueStr関数の使い方

ついでに並び替え (引数2: sort=true)

  list := []string{"Q","E","W","E","E","R","E","T","E","Y","E"}
  list = UniqueStr(list, true)
  for i := range list {
    fmt.Printf("%v, ",list[i])
  }
  fmt.Println()

出力結果は、E, Q, R, T, W, Y, となる。

まとめ

今回の関数は、文字列スライス( []string )にしているが、他の整数型(int,int8 ... int64)や浮動小数点型(float32/64)などに書き換え可能である。
バブルソートは、少ない件数の場合は、他の並び替え方法よりも高速に動作する。
数千件以上になるならば、バブルソート以外にする事をお勧めする。