🤑

ゼロサプレスは難しい

2022/12/30に公開約4,300字

はじめに

https://ja.wikipedia.org/wiki/ゼロサプレス

ゼロサプレスまたはゼロ抑制 (英: zero suppress, zero suppression) は、数の表記から冗長なゼロを除去することである。逆の処理を行う対義語はゼロパディングである。

先日たまたま見た Qiita の記事にゼロサプレスに関する物があった。

https://qiita.com/39shin52/items/75f104f2c2ef327244fa

strings.TrimLeft()を使ってゼロサプレスする

package main

import (
	"fmt"
	"strings"
)

func main() {
	str1 := "000012"
	str2 := "001020"

	fmt.Println(strings.TrimLeft(str1, "0"))
	fmt.Println(strings.TrimLeft(str2, "0"))
}

// > 12
// > 1020

ゼロサプレスの罠

ゼロサプレスは数が前提。つまり 0000 でなければならない。なので strings.TrimLeft を使う事はできない。使って空だったら 0 にしちゃえばいいじゃん?という話かもしれないが、そうすると入力が空文字だった場合に 0 を生み出してしまう。やるのであれば空文字かどうかをチェックしなければならない。

その上でベンチマーク

まず上記の記事の中にあった zeroSuppress を、入力があるのに空文字になってしまわない様に修正した。

func zeroSuppress1b(str string) string {

	slice := strings.Split(str, "")
	res := make([]string, 0)
	flag := false

	for _, v := range slice {
		if v != "0" {
			flag = true // 0でないものが現れたら、flagをtrueにしてappendするようにした
		}
		if flag == true {
			res = append(res, v)
		}
	}
	if len(slice) > 0 && len(res) == 0 {
		return "0"
	}

	return strings.Join(res, "")

}

次に誰でも思いつきそうな単純な zeroSuppress を作った。

func zeroSuppress2b(str string) string {
	for i, v := range str {
		if v != '0' {
			return str[i:]
		}
	}
	if str != "" && str[0] == '0' {
		return "0"
	}
	return str
}

こちらも入力があるのに空文字になってしまわない様にした。

そして strings.TrimLeft を使ったバージョンも書いた。

func zeroSuppress3(str string) string {
	if str == "" {
		return ""
	}
	str = strings.TrimLeft(str, "0")
	if str == "" {
		return "0"
	}
	return str
}

最後に高速化版を書いた。


func zeroSuppress4(str string) string {
	for len(str) > 1 {
		if str[0] != '0' {
			break
		}
		str = str[1:]
	}
	return str
}
名称 説明
zeroSuppress1b オリジナル改
zeroSuppress2b バージョン1
zeroSuppress3 TrimSpace版
zeroSuppress4 高速化版

テスト

テストコードとしては以下を書いた。

package main

import (
	"testing"
)

var tests = []struct {
	name string
	in   string
	want string
}{
	{"1", "", ""},
	{"2", "01", "1"},
	{"3", "001", "1"},
	{"4", "0", "0"},
	{"5", "00", "0"},
	{"5", "1", "1"},
	{"6", "10", "10"},
	{"7", "010", "10"},
}

func testZeroSuppress(t *testing.T, f func(string) string) {
	for _, tt := range tests {
		got := f(tt.in)
		if got != tt.want {
			t.Fatalf("test %v: want %q but got %q", tt.name, tt.want, got)
		}
	}
}

func TestZeroSuppress1(t *testing.T) {
	testZeroSuppress(t, zeroSuppress1b)
}

func TestZeroSuppress2(t *testing.T) {
	testZeroSuppress(t, zeroSuppress2b)
}

func TestZeroSuppress3(t *testing.T) {
	testZeroSuppress(t, zeroSuppress3)
}

func TestZeroSuppress4(t *testing.T) {
	testZeroSuppress(t, zeroSuppress4)
}
=== RUN   TestZeroSuppress1
--- PASS: TestZeroSuppress1 (0.00s)
=== RUN   TestZeroSuppress2
--- PASS: TestZeroSuppress2 (0.00s)
=== RUN   TestZeroSuppress3
--- PASS: TestZeroSuppress3 (0.00s)
=== RUN   TestZeroSuppress4
--- PASS: TestZeroSuppress4 (0.00s)
PASS
ok      zero    0.296s

ベンチマーク

ベンチマークコードを書いた。

func BenchmarkZeroSuppress1(b *testing.B) {
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		zeroSuppress1b("000012")
	}
}

func BenchmarkZeroSuppress2(b *testing.B) {
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		zeroSuppress2b("000012")
	}
}

func BenchmarkZeroSuppress3(b *testing.B) {
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		zeroSuppress3("000012")
	}
}

func BenchmarkZeroSuppress4(b *testing.B) {
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		zeroSuppress4("000012")
	}
}
goos: windows
goarch: amd64
pkg: zero
cpu: AMD Ryzen 5 3500U with Radeon Vega Mobile Gfx
BenchmarkZeroSuppress1-8         3156082               378.9 ns/op           146 B/op          4 allocs/op
BenchmarkZeroSuppress2-8        156059976                7.467 ns/op           0 B/op          0 allocs/op
BenchmarkZeroSuppress3-8        225341380                5.969 ns/op           0 B/op          0 allocs/op
BenchmarkZeroSuppress4-8        367777425                3.341 ns/op           0 B/op          0 allocs/op
PASS
ok      zero    7.173s

評価

雑に思いついた zeroSuppress2b は strings.TrimSpace 版よりも遅くなってしまった。これは for で i および v を両方扱っている事が理由だろう。

後から strings.TrimSpace のソースを見たのだが、基本 zeroSuppress4 がやってる事は同じだった。ただ cutsel (Trim で扱う文字種) が1つか複数かの違いだった。

結論

ゼロサプレスは自分で書いた方が速い。

Discussion

ログインするとコメントできます