Search the Whole Golang Range Map

Question

The problem I want to solve can be expressed as follows: I want to find Integer in the hash map of entire 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. I work with ~ 140,000 ranges, which belong to one of 200 possible classes.

Any idea on how to do this in the Golang? Or what trace should I follow to reach a reasonable solution (~ O (log (n)?)? A way to describe this problem is more general?

Thank you for your help!

Answer 1

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

If the ranges are adjacent, then it is also sufficient to “model” the range using only one number, either with its beginning or with its end. This also applies to your case.

We can list the range boundaries in the int segment in ascending order, and we can perform a binary search in this sorted fragment. We simulate ranges with their maximum value, since the sequence of ranges has no holes. This will give us the range index. We can store the names in a separate fragment and return the name in the index we just found as a result of a binary search.

Here's an amazingly 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:

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

Conclusion (try 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 in Code Overview . StackExchange Website: Classification by Age

Non-contiguous range processing

If the ranges will not cover each number (which means “holes” between the ranges), you can easily deal with this by adding holes as “virtual” ranges and indicating to them the empty string "" name (which we use for invalid ranges). It's all.

For example, let's change the original problem:

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

As you can see, between 9-15: bird and 19-21:dog there is a "hole". Range 16-17 not valid. Here's how to do it:

 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:

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

Conclusion (try this option on Go Playground ):

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

Answer 2

A slightly different approach that implements sort.Interface instead of using 2 slices and processes 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