go - 高效二分查找 []byte 而不是 [][]byte

标签 go binary binary-search

TL;DR I need to efficiently binary search a byte slice for a sequence of bytes.

相关: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 地址的 byte slice 中二分查找 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 得到字节偏移量。

关于go - 高效二分查找 []byte 而不是 [][]byte,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58458933/

相关文章:

MySQL 十六进制二进制限制

java - 为什么java.util.Arrays中的binarySearch()方法是使用循环实现的?

algorithm - 平行二分

go - 一个结构体的单向链表的初始化

html - 处理 CORS 表单提交

Golang Google Drive Oauth2 不返回刷新 token

linux - 未提供 http 静态目录

c++ - 如何在C++中将二进制文件转换为WAV文件

Java:二分搜索实现无法使用延迟相等检测来工作

控件可能到达非空函数的末尾...实现二分查找时出错