Golang在非常大的結構中查找ip範圍

我有一個像下面的結構，約100k entires。Golang在非常大的結構中查找ip範圍

我想循環它，並檢查IP地址是否在範圍內。

我當前的代碼：

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\n", IpAddress, elem.IpStart, elem.IpEnd) 
      return elem.Id, elem.Descr 
     } 
    } 
    return "0", "null" 
}

以上正常工作與40K左右entires但在它得到慢。有沒有更快的方法來找出一個IP地址是否在我的結構內的範圍內？

更新：現在只能解析IP一次，把它作爲數量結構

來源

2016-03-18 mjhd

只是最初的想法是將用戶信息存儲在地圖中，以ip地址作爲密鑰。然後在搜索時不必循環訪問IP地址。 – Wade73

我可以這樣做，因爲我想知道ip：123.123.123.123是否在123.123.123.1和123.123.123.250範圍內？ – mjhd

知識產權是否會落入多個範圍？意思是說'123.123.123.123'是否適用於'123.123.123.1 - > 123.123.123.250'和'123.123.123.128 - > 123.123.124.1'範圍內的2+用戶的範圍？ – sberry

有兩個簡單的步驟，我明白了。

執行解析一次並將IP地址存儲爲單個數字。
按範圍的開始順序排列範圍並使用binary search。

來源

2016-03-18 10:33:55

作爲@Grzegorz Żur的完成建議使用二進制搜索來減少搜索時間，這裏是一個二進制搜索實現。

但首先什麼是二進制搜索？二進制搜索將一系列值分爲兩半，並繼續縮小搜索範圍，直至找到未知值。這是「分而治之」算法的典型例子。

該算法返回某個元素的索引等於給定的值（如果有多個這樣的元素，它返回一些任意的元素）。當找不到元素時，也可以返回它的「插入點」（插入數組中的值）。

遞歸方法

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 
}

的迭代法

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 
}

但是，如果你看一看到sort package你可以觀察，有基於已經實現的排序算法二進制搜索。所以這可能是最好的選擇。

來源

2016-03-18 11:13:32

Golang在非常大的結構中查找ip範圍

回答

相關問題