Lookup in a map of Integer ranges in Golang

Question

The problem I want to resolve can be expressed this way: I want to lookup an Integer in a hashmap of integer ranges.

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

Where:

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

However, thinking of this problem as a hashmap is probably not the right way to go. I'm working with ~ 140,000 ranges, which belong to one of ~ 200 possible classes.

Any idea of how to do this in Golang ? Or which track to follow to reach a reasonable solution (~O(log(n) ?) ? A way to describe this problem more generically ?

Thanks for your help !

Answer 1

If ranges are disjunct (that is a concrete number can only belong to one range), you can find a range using a binary search. This is O(log(n)) complexity.

If ranges are contiguous, it is also enough to "model" a range using only one number, either with its start or its end. This also applies in your case.

We can list the range boundaries in an int slice in ascendent order, and we can perform a binary search in this sorted slice. We model ranges with their maximum value since the sequence of ranges is without any holes. This will give us the index of the range. We can store the names in a separate slice, and return the name at the index we just found as the result of binary search.

Here's the surprisingly short implementation, a one-line function:

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

Testing it:

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

Output (try it on the 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

Note: this solution is also used in a similar question on the Code Review StackExchange site: Classifying by age

Handling non-contiguous ranges

If ranges would not cover every number (meaning there are "holes" between ranges), then you may easily handle that by adding the holes as "virtual" ranges, and give them the empty string "" name (which we used for invalid ranges). That's all.

For example, let's modify your original problem to this:

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

As you can see, there is a "hole" between 9-15: bird and 19-21:dog. The range 16-17 is invalid. Here's how you can map this:

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

There is an empty "" name for the range between 15 and 18. Testing it:

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

Output (try this variant on the Go Playground):

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

Answer 2

A slightly different approach that implements the sort.Interface rather than using 2 slices and handles non-contiguous ranges:

type Range struct {
    Min, Max int
    Value    string
}
type Ranges []Range

func (r Ranges) Len() int           { return len(r) }
func (r Ranges) Less(i, j int) bool { return r[i].Min < r[j].Min }
func (r Ranges) Swap(i, j int)      { r[i], r[j] = r[j], r[i] }
func (r Ranges) Sort()              { sort.Sort(r) }
func (r Ranges) Search(v int) string {
    ln := r.Len()
    if i := sort.Search(ln, func(i int) bool { return v <= r[i].Max }); i < ln {
        if it := &r[i]; v >= it.Min && v <= it.Max {
            return it.Value
        }
    }
    return ""
}

playground