arrays - 在 Golang 的整数范围 map 中查找

Question

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

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

地点:

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

但是，将此问题视为 HashMap 可能不是正确的方法。我正在处理大约 140,000 个范围，它们属于大约 200 个可能的类别之一。

知道如何在 Golang 中执行此操作吗？或者遵循哪条轨道才能找到合理的解决方案 (~O(log(n) ？)？一种更通用地描述此问题的方法？

感谢您的帮助!

Answer 1

如果范围不相交(即一个具体数字只能属于一个范围)，您可以使用二分查找找到一个范围。这是 O(log(n)) 复杂度。

如果范围是连续的，则仅使用一个数字“建模”​​一个范围也足够了，无论是开始还是结束。这也适用于您的情况。

我们可以按升序列出 int slice 中的范围边界，我们可以在这个排序的 slice 中执行二分查找。我们使用最大值对范围进行建模，因为范围序列没有任何漏洞。这将为我们提供范围的索引。我们可以将名称存储在单独的 slice 中，并返回我们刚刚找到的索引处的名称作为二分查找的结果。

这是一个非常短的实现，一个单行函数:

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 站点:Classifying by age

处理不连续的范围

如果范围不会涵盖每个数字(意味着范围之间有“空洞”)，那么您可以通过将空洞添加为“虚拟”范围并为其提供空字符串来轻松处理该问题 "" 名称(我们用于无效范围)。就这样。

例如，让我们将您的原始问题修改为:

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 之间的范围有一个空的 "" 名称。测试它:

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