是否有更有效的函数来查找 []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 {

    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.7ns/op vs 7.40ns/op

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

Answer 2

如果与您的问题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