如何在非常大的结构中找到范围内的ip

Question

我有一个像下面这样的结构，大约有 10 万个。

我想遍历它并检查 IP 地址是否在范围内。

我目前的代码：

type Users struct {

    Id        string

    Descr     string

    IpStart   string

    IpEnd     string

}

var users []*Users

func LookUpIP(IpAddress string) (string, string) {

    iptocheck := net.ParseIP(IpAddress)

    for _, elem := range users {

        if bytes.Compare(iptocheck, elem.IpStart) >= 0 && bytes.Compare(iptocheck, elem.IpEnd) <= 0 {

            fmt.Printf("%v is between %v and %v\n", IpAddress, elem.IpStart, elem.IpEnd)

            return elem.Id, elem.Descr 

        }

    }

    return "0", "null"

}

以上对大约 40k 的整数工作正常，但超过它会变慢。有没有更快的方法来确定一个 ip 地址是否在我的结构内的范围内？

更新：现在只解析一次 IP 并将其存储为结构中的数字

Answer 1

我看到有两个简单的步骤。进行一次解析并将 IP 地址存储为单个数字。按范围的开头对范围进行排序并使用二分搜索。

Answer 2

作为@Grzegorz Żur建议使用二分搜索来减少搜索时间的补充，这里是一个二分搜索实现。但首先什么是二分搜索？二分搜索将一系列值分成两半，并继续缩小搜索范围，直到找到未知值。它是“分而治之”算法的经典示例。该算法返回与给定值相等的某个元素的索引（如果有多个这样的元素，它返回任意一个）。当未找到元素时，也可以为其返回“插入点”（如果将值插入数组，则该值将具有的索引）。递归方法func binarySearch(a []float64, value float64, low int, high int) int {&nbsp; &nbsp; if high < low {&nbsp; &nbsp; &nbsp; &nbsp; return -1&nbsp; &nbsp; }&nbsp; &nbsp; mid := (low + high) / 2 // calculate the mean of two values&nbsp; &nbsp; if a[mid] > value {&nbsp; &nbsp; &nbsp; &nbsp; return binarySearch(a, value, low, mid-1)&nbsp; &nbsp; } else if a[mid] < value {&nbsp; &nbsp; &nbsp; &nbsp; return binarySearch(a, value, mid+1, high)&nbsp; &nbsp; }&nbsp; &nbsp; return mid}迭代法func binarySearch(a []float64, value float64) int {&nbsp; &nbsp; low := 0&nbsp; &nbsp; high := len(a) - 1&nbsp; &nbsp; for low <= high {&nbsp; &nbsp; &nbsp; &nbsp; mid := (low + high) / 2&nbsp; &nbsp; &nbsp; &nbsp; if a[mid] > value {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; high = mid - 1&nbsp; &nbsp; &nbsp; &nbsp; } else if a[mid] < value {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; low = mid + 1&nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return mid&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return -1}但是，如果您查看sort 包，您会发现已经实现了基于二进制搜索的排序算法。所以这可能是最好的选择。