我正在寻找一种有效的方法来寻找两个字节片之间的前缀相似性。我目前正在使用这个方法,但如果可能的话,我正在寻找一种更有效的方法。
谢谢你。
s1 -> [0 15 136 96 88 76 0 0 0 1]
s2 -> [0 15 136 96 246 1 255 255 255 255]
output -> [0 15 136 96]
func bytesSimilar(s1 []byte, s2 []byte) []byte {
for !bytes.Equal(s1,s2) {
s1 = s1[:len(s1)-1]
s2 = s2[:len(s2)-1]
}
return s1
}
基准测试代码。
func BenchmarkBytePrefix200(b *testing.B) {
s1 := []byte{0, 15, 136, 96, 88, 76, 0, 0, 0, 1}
s2 := []byte{0, 15, 136, 96, 246, 1, 255, 255, 255, 255}
b.ReportAllocs()
b.ResetTimer()
for i := 0; i < b.N; i++ {
bytePrefix(s1, s2)
}
}
MBP上的结果
BenchmarkBytePrefix200-8 48738078 29.5 ns/op 0 B/op 0 allocs/op
如果 bytePrefix
同为 bytesSimilar
在你的问题。
func BytesSimilarNew(s1 []byte, s2 []byte) []byte {
for i := 0; i < len(s1); i++ {
if s1[i] ^ s2[i] > 0 {
return s1[:i]
}
}
return []byte{}
}
然后再进行比较。
BenchmarkBytePrefix200
BenchmarkBytePrefix200-8 28900861 36.5 ns/op 0 B/op 0 allocs/op
BenchmarkByteSimilarNew200
BenchmarkByteSimilarNew200-8 237646268 5.06 ns/op 0 B/op 0 allocs/op
PASS
我的看法是,从你上面的代码来看,下面这一段的IO资源是非常昂贵的。
s1 = s1[:len(s1)-1]
s2 = s2[:len(s2)-1]
其实我们可以只做一个简单的循环,当发现不同的字节时就提前退出。采用这种方法,我们不需要太多的内存分配过程。它的代码行数较多,但性能较好。
代码如下
func bytesSimilar2(s1 []byte, s2 []byte) []byte {
l1 := len(s1)
l2 := len(s2)
least := l1
if least > l2 {
least = l2
}
count := 0
for i := 0; i < least; i++ {
if s1[i] == s2[i] {
count++
continue
}
break
}
if count == 0 {
return []byte{}
}
return s1[:count]
}
func BenchmarkBytePrefix200v1(b *testing.B) {
s1 := []byte{0, 15, 136, 96, 88, 76, 0, 0, 0, 1}
s2 := []byte{0, 15, 136, 96, 246, 1, 255, 255, 255, 255}
b.ReportAllocs()
b.ResetTimer()
for i := 0; i < b.N; i++ {
bytesSimilar1(s1, s2)
}
}
func BenchmarkBytePrefix200v2(b *testing.B) {
s1 := []byte{0, 15, 136, 96, 88, 76, 0, 0, 0, 1}
s2 := []byte{0, 15, 136, 96, 246, 1, 255, 255, 255, 255}
b.ReportAllocs()
b.ResetTimer()
for i := 0; i < b.N; i++ {
bytesSimilar2(s1, s2)
}
}
比较结果如下,38.7nsop与7.40nsop的对比。
goos: darwin
goarch: amd64
pkg: git.kanosolution.net/kano/acl
BenchmarkBytePrefix200v1-8 27184414 38.7 ns/op 0 B/op 0 allocs/op
BenchmarkBytePrefix200v2-8 161031307 7.40 ns/op 0 B/op 0 allocs/op
PASS