Эффективно бинарный поиск [] байт, а не [] [] байт - PullRequest
Новая
       24

Эффективно бинарный поиск [] байт, а не [] [] байт

1 голос
/ 19 октября 2019

TL; DR Мне нужен эффективный двоичный поиск байтового среза для последовательности байтов.

Releated: byte [] поиск по массиву

У меня есть двоичный файл с 16-байтовыми IP-адресами, которые я хотел бы сделать бинарный поискна. Я встраиваю этот файл в go Binary, используя Packr, который выдаст []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")
    }
}

1 Ответ

3 голосов
/ 19 октября 2019

Используйте следующий код для двоичного поиска 16-байтового IP-адреса в срезе байтов, содержащих отсортированные 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, чтобы получить смещение в байтах.

...