TL; DR我需要高效地对字节片进行二进制搜索以获取字节序列。
发布:byte[] array pattern search
我有一个16字节ip地址的二进制文件,我想对它进行二进制搜索。我正在使用Packr将此文件嵌入go Binary中,该文件将给出文件数据的[]byte
。
这意味着我必须遍历[] byte来创建[] [] byte才能搜索16个字节而不是1个字节。此循环效率不高,我正在寻找避免这种循环的方法。
我在下面没有使用Packr的情况下提供了一个最小的示例。
package main
import (
"fmt"
"io/ioutil"
)
func main() {
// Get our file. It is a file with many 16-byte form IP.
// head -c 32 bin/test | xxd
// 00000000: 0100 0000 0000 0000 0000 0000 0000 0000 ................
// 00000010: 0000 0000 0000 0000 1800 0000 0000 0000 ................
buf, err := ioutil.ReadFile("bin/test")
if err != nil {
fmt.Println(err)
}
// This is too slow :-(
// How could this loop be replaced by some additional logic in the binary search below
data := [][]byte{}
for i := 0; i < len(buf); i += 16 {
data = append(data, buf[i:i+16])
}
i := sort.Search(len(data), func(i int) bool {
fmt.Println(len(data[i]), len(n.Bytes()))
return bytes.Compare(data[i], n.Bytes()) < 1
})
if i < len(data) {
fmt.Println(data[i])
} else {
fmt.Println("Not found")
}
}
使用以下代码在包含已排序IP地址的字节片中二进制搜索16字节IP地址。
func search16(haystack, needle []byte) int {
return 16 * sort.Search(len(haystack)/16,
func(i int) bool { return bytes.Compare(haystack[i*16:(i+1)*16], needle) >= 0 })
}
sort.Search看到的索引是字节偏移量除以16。sort.Search的结果乘以16得到字节偏移量。