🤑
ゼロサプレスは難しい
はじめに
ゼロサプレスまたはゼロ抑制 (英: zero suppress, zero suppression) は、数の表記から冗長なゼロを除去することである。逆の処理を行う対義語はゼロパディングである。
先日たまたま見た Qiita の記事にゼロサプレスに関する物があった。
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
ゼロサプレスの罠
ゼロサプレスは数が前提。つまり 000 は 0 でなければならない。なので 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