在戈朗的整数范围地图上查找

Question

我想要解决的问题可以这样表达:我想在整数范围的哈希映射中查找一个整数。

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

其中：

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

然而，把这个问题看作一个hashmap可能不是正确的方法。我正在研究14万个范围，它们属于大约200个可能的类中的一个。

知道在戈朗怎么做吗？或者遵循哪条轨道才能得到合理的解(~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)
    }
}

输出(在围棋游乐场上尝试)：

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

注意:此解决方案也用于代码评审 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", ""}

对于15和18之间的范围，有一个空的18名称。测试它：

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)
    }
}

输出(在围棋游乐场上尝试这个变体)：

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