Есть ли более эффективная функция для нахождения [] сходства байтов? - PullRequest
Новая
       26

Есть ли более эффективная функция для нахождения [] сходства байтов?

1 голос
/ 28 апреля 2020

Я ищу эффективный способ найти сходство префикса между двумя байтовыми срезами. Я в настоящее время использую это, но ищу более эффективный способ, если это возможно.

Спасибо. 

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

Ответы [ 2 ]

2 голосов
/ 28 апреля 2020

По моему мнению, из приведенного выше кода следующий раздел очень дорогой для ресурса ввода-вывода 

s1 = s1[:len(s1)-1]
s2 = s2[:len(s2)-1]

На самом деле мы можем просто сделать простой l oop и выйти рано, когда будет найден другой байт. При таком подходе нам не нужно много процесса выделения памяти. В коде больше строк, но производительность выше.

Код такой, как показано ниже 

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,7 нс / оп против 7,40 нс / оп 

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
0 голосов
/ 28 апреля 2020

Если 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
...