diff options
| author | Ilya Tocar <ilya.tocar@intel.com> | 2016-09-07 16:35:32 +0300 |
|---|---|---|
| committer | Brad Fitzpatrick <bradfitz@golang.org> | 2016-10-15 16:39:31 +0000 |
| commit | 6347367be36df608cce84beb097378f8654dd208 (patch) | |
| tree | 5b1afdeb10eb308855c3e2eddfbddfeeda127981 /src/strings/strings.go | |
| parent | 86b2f29676c52774d91dda96e0ba5d4d7bcd3b47 (diff) | |
| download | go-6347367be36df608cce84beb097378f8654dd208.tar.xz | |
strings: use Index in Count
This simplifies code and provides performance iprovments:
Similar to https://go-review.googlesource.com/#/c/28577
CountHard1-48 1.74ms ±14% 0.17ms ±14% -90.16% (p=0.000 n=19+19)
CountHard2-48 1.78ms ±15% 0.25ms ±13% -86.10% (p=0.000 n=19+20)
CountHard3-48 1.78ms ±12% 0.80ms ±11% -55.19% (p=0.000 n=17+20)
CountTorture-48 13.5µs ±14% 13.6µs ±11% ~ (p=0.625 n=18+19)
CountTortureOverlapping-48 6.92ms ±13% 8.42ms ±11% +21.72% (p=0.000 n=19+17)
Change-Id: Ief120aee918a66487c76be56e0796871c8502f89
Reviewed-on: https://go-review.googlesource.com/28586
Run-TryBot: Ilya Tocar <ilya.tocar@intel.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Diffstat (limited to 'src/strings/strings.go')
| -rw-r--r-- | src/strings/strings.go | 46 |
1 files changed, 8 insertions, 38 deletions
diff --git a/src/strings/strings.go b/src/strings/strings.go index 10922f3c1d..5be32fce5c 100644 --- a/src/strings/strings.go +++ b/src/strings/strings.go @@ -77,48 +77,18 @@ func hashStrRev(sep string) (uint32, uint32) { func Count(s, sep string) int { n := 0 // special cases - switch { - case len(sep) == 0: + if len(sep) == 0 { return utf8.RuneCountInString(s) + 1 - case len(sep) == 1: - // special case worth making fast - c := sep[0] - for i := 0; i < len(s); i++ { - if s[i] == c { - n++ - } - } - return n - case len(sep) > len(s): - return 0 - case len(sep) == len(s): - if sep == s { - return 1 - } - return 0 - } - // Rabin-Karp search - hashsep, pow := hashStr(sep) - h := uint32(0) - for i := 0; i < len(sep); i++ { - h = h*primeRK + uint32(s[i]) } - lastmatch := 0 - if h == hashsep && s[:len(sep)] == sep { - n++ - lastmatch = len(sep) - } - for i := len(sep); i < len(s); { - h *= primeRK - h += uint32(s[i]) - h -= pow * uint32(s[i-len(sep)]) - i++ - if h == hashsep && lastmatch <= i-len(sep) && s[i-len(sep):i] == sep { - n++ - lastmatch = i + offset := 0 + for { + i := Index(s[offset:], sep) + if i == -1 { + return n } + n++ + offset += i + len(sep) } - return n } // Contains reports whether substr is within s. |