slices: add Replace
This CL adds a strightforward implementation of a Replace function.
Benchmark:
name time/op
Replace/naive-fast-8 144ns ± 2%
Replace/optimized-fast-8 136ns ± 1%
Replace/naive-slow-8 267ns ± 8%
Replace/optimized-slow-8 252ns ±14%
Fixes golang/go#55358
Change-Id: Ibf7187a890385a454c5b5daff9f731da11e6fd72
Reviewed-on: https://go-review.googlesource.com/c/exp/+/444682
Auto-Submit: Ian Lance Taylor <iant@google.com>
Run-TryBot: Ian Lance Taylor <iant@google.com>
Run-TryBot: Changkun Ou <mail@changkun.de>
Reviewed-by: Ian Lance Taylor <iant@google.com>
Reviewed-by: David Chase <drchase@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
diff --git a/slices/slices.go b/slices/slices.go
index a9fe63f..0c756c4 100644
--- a/slices/slices.go
+++ b/slices/slices.go
@@ -162,6 +162,23 @@
return append(s[:i], s[j:]...)
}
+// Replace replaces the elements s[i:j] by the given v, and returns the
+// modified slice. Replace panics if s[i:j] is not a valid slice of s.
+func Replace[S ~[]E, E any](s S, i, j int, v ...E) S {
+ tot := len(s[:i]) + len(v) + len(s[j:])
+ if tot <= cap(s) {
+ s2 := s[:tot]
+ copy(s2[i+len(v):], s[j:])
+ copy(s2[i:], v)
+ return s2
+ }
+ s2 := make(S, tot)
+ copy(s2, s[:i])
+ copy(s2[i:], v)
+ copy(s2[i+len(v):], s[j:])
+ return s2
+}
+
// Clone returns a copy of the slice.
// The elements are copied using assignment, so this is a shallow clone.
func Clone[S ~[]E, E any](s S) S {
diff --git a/slices/slices_test.go b/slices/slices_test.go
index 97c4718..367dcf1 100644
--- a/slices/slices_test.go
+++ b/slices/slices_test.go
@@ -614,3 +614,99 @@
t.Errorf("cap(Clip(%v)) = %d, want 3", orig, cap(s2))
}
}
+
+// naiveReplace is a baseline implementation to the Replace function.
+func naiveReplace[S ~[]E, E any](s S, i, j int, v ...E) S {
+ s = Delete(s, i, j)
+ s = Insert(s, i, v...)
+ return s
+}
+
+func TestReplace(t *testing.T) {
+ for _, test := range []struct {
+ s, v []int
+ i, j int
+ }{
+ {}, // all zero value
+ {
+ s: []int{1, 2, 3, 4},
+ v: []int{5},
+ i: 1,
+ j: 2,
+ },
+ {
+ s: []int{1, 2, 3, 4},
+ v: []int{5, 6, 7, 8},
+ i: 1,
+ j: 2,
+ },
+ {
+ s: func() []int {
+ s := make([]int, 3, 20)
+ s[0] = 0
+ s[1] = 1
+ s[2] = 2
+ return s
+ }(),
+ v: []int{3, 4, 5, 6, 7},
+ i: 0,
+ j: 1,
+ },
+ } {
+ ss, vv := Clone(test.s), Clone(test.v)
+ want := naiveReplace(ss, test.i, test.j, vv...)
+ got := Replace(test.s, test.i, test.j, test.v...)
+ if !Equal(got, want) {
+ t.Errorf("Replace(%v, %v, %v, %v) = %v, want %v", test.s, test.i, test.j, test.v, got, want)
+ }
+ }
+}
+
+func BenchmarkReplace(b *testing.B) {
+ cases := []struct {
+ name string
+ s, v func() []int
+ i, j int
+ }{
+ {
+ name: "fast",
+ s: func() []int {
+ return make([]int, 100)
+ },
+ v: func() []int {
+ return make([]int, 20)
+ },
+ i: 10,
+ j: 40,
+ },
+ {
+ name: "slow",
+ s: func() []int {
+ return make([]int, 100)
+ },
+ v: func() []int {
+ return make([]int, 20)
+ },
+ i: 0,
+ j: 2,
+ },
+ }
+
+ for _, c := range cases {
+ b.Run("naive-"+c.name, func(b *testing.B) {
+ for k := 0; k < b.N; k++ {
+ s := c.s()
+ v := c.v()
+ _ = naiveReplace(s, c.i, c.j, v...)
+ }
+ })
+ b.Run("optimized-"+c.name, func(b *testing.B) {
+ for k := 0; k < b.N; k++ {
+ s := c.s()
+ v := c.v()
+ _ = Replace(s, c.i, c.j, v...)
+ }
+ })
+ }
+
+}
