I have a struct like below, with about 100k entires.
I would like to loop over it and check if a ip address is in range.
My current code:
type Users struct {
Id string
Descr string
IpStart string
IpEnd string
}
var users []*Users
func LookUpIP(IpAddress string) (string, string) {
iptocheck := net.ParseIP(IpAddress)
for _, elem := range users {
if bytes.Compare(iptocheck, elem.IpStart) >= 0 && bytes.Compare(iptocheck, elem.IpEnd) <= 0 {
fmt.Printf("%v is between %v and %v
", IpAddress, elem.IpStart, elem.IpEnd)
return elem.Id, elem.Descr
}
}
return "0", "null"
}
The above works fine with about 40k entires but over that it gets slow. Is there any faster way to find out if a ip address is in range inside my struct?
Update: Now only parsing ip once and storing it as number in struct
There are two simple steps I see.
As a completion of @Grzegorz Żur suggestion to use binary search for reducing the search time, here is a binary search implementation in go.
But first what is binary search? A binary search divides a range of values into halves, and continues to narrow down the field of search until the unknown value is found. It is the classic example of a "divide and conquer" algorithm.
The algorithm returns the index of some element that equals the given value (if there are multiple such elements, it returns some arbitrary one). It is also possible, when the element is not found, to return the "insertion point" for it (the index that the value would have if it were inserted into the array).
The recursive method
func binarySearch(a []float64, value float64, low int, high int) int {
if high < low {
return -1
}
mid := (low + high) / 2 // calculate the mean of two values
if a[mid] > value {
return binarySearch(a, value, low, mid-1)
} else if a[mid] < value {
return binarySearch(a, value, mid+1, high)
}
return mid
}
The iterative method
func binarySearch(a []float64, value float64) int {
low := 0
high := len(a) - 1
for low <= high {
mid := (low + high) / 2
if a[mid] > value {
high = mid - 1
} else if a[mid] < value {
low = mid + 1
} else {
return mid
}
}
return -1
}
But if you take a look into the sort package you can observe that there is an already implemented sorting algorithm based on binary search. So probably this would be the best option.