是否有更有效的函数来查找 []byte 相似性？

Question

我正在寻找一种有效的方法来查找两个字节片之间的前缀相似性。我目前正在使用它，但如果可能的话，我正在寻找一种更有效的方法。

谢谢你。

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

Answer 1

我认为，从您上面的代码来看，以下部分在 I/O 资源上非常昂贵s1 = s1[:len(s1)-1]s2 = s2[:len(s2)-1]我们实际上可以做一个简单的循环并在找到不同的字节时提前退出。使用这种方法，我们不需要太多的内存分配过程。它的代码行数更多，但性能更好。代码如下func bytesSimilar2(s1 []byte, s2 []byte) []byte {&nbsp; &nbsp; l1 := len(s1)&nbsp; &nbsp; l2 := len(s2)&nbsp; &nbsp; least := l1&nbsp; &nbsp; if least > l2 {&nbsp; &nbsp; &nbsp; &nbsp; least = l2&nbsp; &nbsp; }&nbsp; &nbsp; count := 0&nbsp; &nbsp; for i := 0; i < least; i++ {&nbsp; &nbsp; &nbsp; &nbsp; if s1[i] == s2[i] {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count++&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; continue&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; break&nbsp; &nbsp; }&nbsp; &nbsp; if count == 0 {&nbsp; &nbsp; &nbsp; &nbsp; return []byte{}&nbsp; &nbsp; }&nbsp; &nbsp; return s1[:count]}func BenchmarkBytePrefix200v1(b *testing.B) {&nbsp; &nbsp; s1 := []byte{0, 15, 136, 96, 88, 76, 0, 0, 0, 1}&nbsp; &nbsp; s2 := []byte{0, 15, 136, 96, 246, 1, 255, 255, 255, 255}&nbsp; &nbsp; b.ReportAllocs()&nbsp; &nbsp; b.ResetTimer()&nbsp; &nbsp; for i := 0; i < b.N; i++ {&nbsp; &nbsp; &nbsp; &nbsp; bytesSimilar1(s1, s2)&nbsp; &nbsp; }}func BenchmarkBytePrefix200v2(b *testing.B) {&nbsp; &nbsp; s1 := []byte{0, 15, 136, 96, 88, 76, 0, 0, 0, 1}&nbsp; &nbsp; s2 := []byte{0, 15, 136, 96, 246, 1, 255, 255, 255, 255}&nbsp; &nbsp; b.ReportAllocs()&nbsp; &nbsp; b.ResetTimer()&nbsp; &nbsp; for i := 0; i < b.N; i++ {&nbsp; &nbsp; &nbsp; &nbsp; bytesSimilar2(s1, s2)&nbsp; &nbsp; }}比较结果如下，38.7ns/op vs 7.40ns/opgoos: darwingoarch: amd64pkg: git.kanosolution.net/kano/aclBenchmarkBytePrefix200v1-8&nbsp; &nbsp; &nbsp; 27184414&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 38.7 ns/op&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;0 B/op&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 0 allocs/opBenchmarkBytePrefix200v2-8&nbsp; &nbsp; &nbsp; 161031307&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 7.40 ns/op&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 0 B/op&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 0 allocs/opPASS

Answer 2

如果与您的问题bytePrefix相同：bytesSimilarfunc BytesSimilarNew(s1 []byte, s2 []byte) []byte {&nbsp; &nbsp; for i := 0; i < len(s1); i++ {&nbsp; &nbsp; &nbsp; &nbsp; if s1[i] ^ s2[i] > 0 {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return s1[:i]&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return []byte{}}然后比较：BenchmarkBytePrefix200BenchmarkBytePrefix200-8&nbsp; &nbsp; &nbsp; &nbsp; 28900861&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 36.5 ns/op&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;0 B/op&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 0 allocs/opBenchmarkByteSimilarNew200BenchmarkByteSimilarNew200-8&nbsp; &nbsp; 237646268&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 5.06 ns/op&nbsp; &nbsp; &nbsp; &nbsp; 0 B/op&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 0 allocs/opPASS