diff options
author | Tobias Klauser <tklauser@distanz.ch> | 2019-03-08 11:39:08 +0100 |
---|---|---|
committer | Tobias Klauser <tobias.klauser@gmail.com> | 2019-03-08 13:46:43 +0000 |
commit | ce7534ff06df5b3148aa325deedcb94ac5b30ec0 (patch) | |
tree | ccfb8f651e1e8683214e34e37581ec6b669f16f4 /src/bytes | |
parent | b4baa8dd1d8bc1d65e80e88c294729554bab72b8 (diff) | |
download | go-ce7534ff06df5b3148aa325deedcb94ac5b30ec0.tar.gz go-ce7534ff06df5b3148aa325deedcb94ac5b30ec0.zip |
bytes: use Rabin-Karp algorithm for LastIndex
Implement LastIndex using the Rabin-Karp algorithm akin to
strings.LastIndex
name old time/op new time/op delta
LastIndexHard1-8 3.16ms ± 1% 1.44ms ± 0% -54.35% (p=0.008 n=5+5)
LastIndexHard2-8 3.17ms ± 1% 1.45ms ± 0% -54.27% (p=0.008 n=5+5)
LastIndexHard3-8 3.05ms ± 1% 1.44ms ± 1% -52.58% (p=0.008 n=5+5)
Change-Id: Ie8ddd179cd84dfa00e3e4e2327ef932975c88670
Reviewed-on: https://go-review.googlesource.com/c/go/+/166258
Run-TryBot: Tobias Klauser <tobias.klauser@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Diffstat (limited to 'src/bytes')
-rw-r--r-- | src/bytes/bytes.go | 47 |
1 files changed, 43 insertions, 4 deletions
diff --git a/src/bytes/bytes.go b/src/bytes/bytes.go index daf4a32f26..f65bf214cc 100644 --- a/src/bytes/bytes.go +++ b/src/bytes/bytes.go @@ -114,12 +114,34 @@ func indexBytePortable(s []byte, c byte) int { // LastIndex returns the index of the last instance of sep in s, or -1 if sep is not present in s. func LastIndex(s, sep []byte) int { n := len(sep) - if n == 0 { + switch { + case n == 0: return len(s) + case n == 1: + return LastIndexByte(s, sep[0]) + case n == len(s): + if Equal(s, sep) { + return 0 + } + return -1 + case n > len(s): + return -1 } - c := sep[0] - for i := len(s) - n; i >= 0; i-- { - if s[i] == c && (n == 1 || Equal(s[i:i+n], sep)) { + // Rabin-Karp search from the end of the string + hashss, pow := hashStrRev(sep) + last := len(s) - n + var h uint32 + for i := len(s) - 1; i >= last; i-- { + h = h*primeRK + uint32(s[i]) + } + if h == hashss && Equal(s[last:], sep) { + return last + } + for i := last - 1; i >= 0; i-- { + h *= primeRK + h += uint32(s[i]) + h -= pow * uint32(s[i+n]) + if h == hashss && Equal(s[i:i+n], sep) { return i } } @@ -987,3 +1009,20 @@ func hashStr(sep []byte) (uint32, uint32) { } return hash, pow } + +// hashStrRev returns the hash of the reverse of sep and the +// appropriate multiplicative factor for use in Rabin-Karp algorithm. +func hashStrRev(sep []byte) (uint32, uint32) { + hash := uint32(0) + for i := len(sep) - 1; i >= 0; i-- { + hash = hash*primeRK + uint32(sep[i]) + } + var pow, sq uint32 = 1, primeRK + for i := len(sep); i > 0; i >>= 1 { + if i&1 != 0 { + pow *= sq + } + sq *= sq + } + return hash, pow +} |