如何有效地索引和搜索ipv4地址範圍在c＃

Question

我有大約90000個IPv4地址範圍與數據與每個範圍相關聯

例如，

1.0.0.0 - 1.1.0.0 -> "foo" 
2.0.0.0 - 10.0.0.0 -> "bar" 

給定一個IP地址，我需要檢索關聯的數據。我怎樣纔能有效地？

我想我可以通過將地址轉換爲單個整數來簡化操作，但是最好使用什麼數據結構來存儲這個數據以便快速地搜索？

澄清 - 我有一個IP，而不是一個範圍（例如 「192.168.0.1」）進行搜索

感謝

Answer 1

在單個數組中排列非重疊區間的末端。馬克每端有一個標誌，指示，如果它是一開始或間隔的結束，就像這樣：

1.0.0.0 1.1.0.0 2.0.0.0 10.0.0.0 
start end  start end 

現在運行與目標地址，也就是說，3.2.1.0二進制搜索。插入點位於2.0.0.0，標記爲start。這意味着3.2.1.0是間隔之一。

現在考慮搜索1.2.3.4。其插入點位於1.1.0.0，標記爲end。由於1.2.3.4不等於1.1.0.0，因此我們知道1.2.3.4不是其中的一個間隔。

搜索的成本是Log(N)，其中N是間隔數。

如果您覺得冒險，請考慮實施interval tree。不過，這可能不適合非重疊的時間間隔。

Answer 2

如果你只需要支持IPv4地址，而不是IPv6地址，可以將每個地址存儲爲UInt32。這將使他們比較容易和高效。

如果IP範圍不重疊，並且可以將它們保留在列表中，則可以使用二進制搜索的變化快速查找範圍。

Answer 3

尋找從0到20的數字是否包括符合下列範圍：

2-5 -> "a" 
6-7 -> "b" 
9-11 -> "c" 
12-12 -> "d" 
15-18 -> "e" 
19-19 -> "f" 

內循環1,000,000次，其中1次創建和RangeCollection的初始化：僅有3秒！

所有剩下的事情就是準備一個元組IEnumerable，其中第一個int是最小的IP int值，第二個是最大值，而TValue是與該最小值到最大值範圍相關聯的數據。

這是我實現：

public class RangeCollection<TValue> 
{ 
    private readonly int[] _mins; 
    private readonly int[] _maxs; 
    private readonly TValue[] _values; 

    public RangeCollection(params Tuple<int, int, TValue>[] input) 
     : this((IEnumerable<Tuple<int, int, TValue>>)input) 
    { 
    } 

    public RangeCollection(IEnumerable<Tuple<int, int, TValue>> input) 
    { 
     var tuples = input.OrderBy(tuple => tuple.Item1).ToArray(); 

     for (var i = 1; i < tuples.Length; i++) 
     { 
      if (tuples[i].Item1 <= tuples[i - 1].Item2) 
      { 
       throw new ArgumentException("Ranges should not overlap."); 
      } 
     } 

     this._mins = new int[tuples.Length]; 
     this._maxs = new int[tuples.Length]; 
     this._values = new TValue[tuples.Length]; 

     for (var i = 0; i < tuples.Length; i++) 
     { 
      var tuple = tuples[i]; 

      this._mins[i] = tuple.Item1; 
      this._maxs[i] = tuple.Item2; 
      this._values[i] = tuple.Item3; 
     } 
    } 

    public bool TryGetValue(int key, out TValue value) 
    { 
     if (this.Contains(key, out key)) 
     { 
      value = this._values[key]; 
      return true; 
     } 

     value = default(TValue); 
     return false; 
    } 

    public bool Contains(int key) 
    { 
     return this.Contains(key, out key); 
    } 

    private bool Contains(int key, out int index) 
    { 
     index = 0; 

     if (this._mins.Length == 0 || key < this._mins[0] || key > this._maxs[this._maxs.Length - 1]) 
     { 
      return false; 
     } 

     var low = 0; 
     var high = this._mins.Length - 1; 

     while (high >= low) 
     { 
      index = (low + high)/2; 

      var cmp = this._mins[index].CompareTo(key); 

      if (cmp == 0) 
      { 
       return true; 
      } 

      if (cmp == 1) 
      { 
       high = index - 1; 
      } 
      else 
      { 
       low = index + 1; 
      } 
     } 

     if (this._mins[index] > key) 
     { 
      index--; 
     } 
     else if (this._mins[index + 1] <= key) 
     { 
      index++; 
     } 

     return this._maxs[index] >= key; 
    } 
} 

用法：

var collection = new RangeCollection<string>(new Tuple<int, int, string>(2, 5, "a"), 
              new Tuple<int, int, string>(6, 7, "b"), 
              new Tuple<int, int, string>(9, 11, "c"), 
              new Tuple<int, int, string>(12, 12, "d"), 
              new Tuple<int, int, string>(15, 18, "e"), 
              new Tuple<int, int, string>(19, 19, "f")); 

for (var i = 0; i <= 20; i++) 
{ 
    string val; 
    if (collection.TryGetValue(i, out val)) 
    { 
     Debug.WriteLine("Contains {0}. Value: {1}", i, val); 
    } 
    else 
    { 
     Debug.WriteLine("Doesn't contain " + i); 
    } 
} 

/* Output: 

Doesn't contain 0 
Doesn't contain 1 
Contains 2. Value: a 
Contains 3. Value: a 
Contains 4. Value: a 
Contains 5. Value: a 
Contains 6. Value: b 
Contains 7. Value: b 
Doesn't contain 8 
Contains 9. Value: c 
Contains 10. Value: c 
Contains 11. Value: c 
Contains 12. Value: d 
Doesn't contain 13 
Doesn't contain 14 
Contains 15. Value: e 
Contains 16. Value: e 
Contains 17. Value: e 
Contains 18. Value: e 
Contains 19. Value: f 
Doesn't contain 20 

*/