在Golang的Integer范围地图中查找

Question

我想解决的问题可以这样表达:我想在整数范围的hashmap中查找Integer.

0-4: dog,
5-8: cat,
9-18: bird,
19-21: dog,
22-22: bird,
...

哪里:

lookup(3) -> dog
lookup(10) -> bird

但是,将此问题视为散列图可能不是正确的方法.我正在使用~140,000个范围,属于~200个可能类别中的一个.

知道如何在Golang中做到这一点？或者通过哪条跟踪来达到合理的解决方案(~O(log(n)？)？更一般地描述这个问题的方法是什么？

谢谢你的帮助 !

Answer 1

如果范围是间断的(这是一个具体的数字只能属于一个范围),您可以使用二进制搜索找到一个范围.这很O(log(n))复杂.

如果范围是连续的,那么仅使用一个数字来"建模"一个范围就足够了,无论是开始还是结束.这也适用于您的情况.

我们可以int按照上升顺序列出切片中的范围边界,并且我们可以在此排序切片中执行二进制搜索.我们用最大值对范围进行建模,因为范围序列没有任何孔.这将为我们提供范围的索引.我们可以将名称存储在单独的切片中,并在我们刚刚找到的索引处返回名称作为二进制搜索的结果.

这是一个令人惊讶的简短实现,一个单行功能:

var ranges = []int{-1, 4, 8, 18, 21, 22}
var names = []string{"", "dog", "cat", "bird", "dog", "bird", ""}

func getName(n int) string {
    return names[sort.SearchInts(ranges, n)]
}

测试它:

nums := []int{-1, 3, 6, 10, 20, 22, 100}
for _, n := range nums {
    if name := getName(n); name == "" {
        fmt.Printf("Invalid number: %4d\n", n)
    } else {
        fmt.Printf("Number        : %4d, Name: %s\n", n, name)
    }
}

输出(在Go Playground上试试):

Invalid number:   -1
Number        :    3, Name: dog
Number        :    6, Name: cat
Number        :   10, Name: bird
Number        :   20, Name: dog
Number        :   22, Name: bird
Invalid number:  100

注意:此解决方案也用于Code Review StackExchange站点上的类似问题:按年龄分类

处理非连续范围

如果范围不会覆盖每个数字(意味着范围之间存在"漏洞"),那么您可以通过将孔添加为"虚拟"范围来轻松处理,并为它们提供空字符串""名称(我们用于无效范围).就这样.

例如,让我们将原始问题修改为:

0-4: dog,
5-8: cat,
9-15: bird,
19-21: dog,
22-22: bird,

如你所见,在9-15: bird和之间有一个"洞" 19-21:dog.范围16-17无效.这是你如何映射这个:

var ranges = []int{-1, 4, 8, 15, 18, 21, 22}
var names = []string{"", "dog", "cat", "bird", "", "dog", "bird", ""}

和""之间的范围有一个空名称.测试它:1518

nums := []int{15, 16, 19}
for _, n := range nums {
    if name := getName(n); name == "" {
        fmt.Printf("Invalid number: %4d\n", n)
    } else {
        fmt.Printf("Number        : %4d, Name: %s\n", n, name)
    }
}

输出(在Go Playground上尝试此变体):

Number        :   15, Name: bird
Invalid number:   16
Number        :   19, Name: dog