C＃ - 允許您根據範圍內的值訪問元素的數據結構

Question

我有一個對象列表。它們都與該對象所獨有的範圍有關。沒有重疊。我想要一種方式儘可能快地訪問與該範圍相關聯的對象。目前的數據結構都不適合這種情況。這裏有一個圖：

Element 1 
0.0-1.39 

Element 2 
1.4-2.09 

Element 3 
2.1-4.89 

Element 4 
4.9-5.0 

什麼是理想的是一種鍵/字典式的東西，我可以在範圍值1.7要求的元素，它會返回元素2.

的回退是列表，但這意味着每次都會對其進行迭代，並且取決於大小，理論上它可能會變慢。

Answer 1

有沒有重疊

這個假設可以讓你簡單地存儲地圖，其中的關鍵是降低（或上）的約束，你正在尋找，並找到最近的構件¹到它。基於樹的地圖很容易實現。另外，如果您沒有這種限制並且時間間隔可能重疊 - 您可能需要更改intervals tree。 （1）關於「最接近」的說明：你需要一個尋找:(假設下界被存儲）：找到最接近的較小/相等的值。檢查它是否適合該範圍。在基於樹的地圖中，這在對數時間內很容易完成。
如果存儲上限，則需要反過來執行。

Answer 2

 List<Tuple<string, double, double>> ElmList = new List<Tuple<string, double, double>>(); 

     private void LoadTuple() 
     { 

      ElmList.Add(new Tuple<string, double, double>("Element 1", 0.0, 1.39)); 
      ElmList.Add(new Tuple<string, double, double>("Element 2", 1.4, 2.09)); 
      ElmList.Add(new Tuple<string, double, double>("Element 3", 2.1, 4.89)); 
      ElmList.Add(new Tuple<string, double, double>("Element 4", 4.9, 5.0)); 

     } 

     private void button2_Click(object sender, EventArgs e) 
     { 
      double temp = double.Parse(textBox1.Text); 
      var element = ElmList.FirstOrDefault(x => x.Item2 <= temp && x.Item3 >= temp); 
      MessageBox.Show(element.Item1); 
     } 

元組將解決您的問題，我已經嘗試過類似上述

Answer 3

你可以嘗試創建一個搜索樹。您將不得不根據里程碑對範圍進行分組，例如1到5.然後，我們會創建一個字典，將這些milstones作爲關鍵字，並將這些里程碑作爲值更接近這些里程碑。

Key  Value 
1  0.0-1.39 
2  0.0-1.39, 1.4-2.09 
3  2.1-4.89 
4  2.1-4.89 
5  2.1-4.89, 4.9-5.0 

當我們試圖在其中找到了一些限制在上述範圍，

1. 我們將在數做了Math.Ceil（）
2. 匹配它的里程碑字典和發現的範圍的列表爲關鍵
3. 現在通過迭代範圍內的里程碑下找到包含數字的範圍

您可能必須根據您的範圍來定義不同的里程碑。

Answer 4

我認爲你可以簡單地使用二叉搜索樹，或者更好的AVL（如果你不期待大量的插入或刪除）。

示例代碼：使用跨樹遍歷上限值（使用此repository通過bitlush AVL實現）

class Range<T> where T : IComparable<T> 
{ 
    public T LBound { get; set; } 

    public T UBound { get; set; } 

    public bool ContainsValue(T value) 
    { 
     return (this.LBound.CompareTo(value) <= 0) && (value.CompareTo(this.UBound) <= 0); 
    } 
} 

class RangeKeyComparer : IComparer<Range<double>> 
{ 
    public int Compare(Range<double> x, Range<double> y) 
    { 
     return x.UBound.CompareTo(y.UBound); 
    } 
} 

class RangeAvlTree<T, TValue> : AvlTree<Range<T>, TValue> where T : IComparable<T> 
{ 

    public RangeAvlTree(IComparer<Range<T>> comparer) 
    { 
     //update access modifier to 'protected' in base class 
     _comparer = comparer; 
    } 

    public bool Search(T searchKey, out TValue value) 
    { 
     //update access modifier to 'protected' in base class 
     AvlNode<Range<T>, TValue> node = _root; 

     while (node != null) 
     { 
      if (node.Key.ContainsValue(searchKey)) 
      { 
       value = node.Value; 
       return true; 
      } 
      else if (searchKey.CompareTo(node.Key.UBound) == 1) 
       node = node.Right; 
      else if (searchKey.CompareTo(node.Key.UBound) == -1) 
       node = node.Left; 
     } 

     value = default(TValue); 

     return false; 
    } 
} 

使用

static void Main(string[] args) 
{ 
    var tree = new RangeAvlTree<double, string>(new RangeKeyComparer()); 

    tree.Insert(new Range<double> { LBound = 0.0, UBound = 1.39 }, "Element: 0.0 - 1.39"); 
    tree.Insert(new Range<double> { LBound = 1.4, UBound = 2.09 }, "Element: 1.4 - 2.09"); 
    tree.Insert(new Range<double> { LBound = 2.1, UBound = 4.89 }, "Element: 2.1 - 4.89"); 
    tree.Insert(new Range<double> { LBound = 4.9, UBound = 5.0 }, "Element: 4.9 - 5.00"); 

    string element; 

    foreach(var value in new[] { 0.1, 1.41, 3, 2.04, 2.092, 4.93, 3.4 }) 
     if (tree.Search(value, out element)) 
      Console.WriteLine($"Found match: {value} matches {element}"); 
     else 
      Console.WriteLine($"Not found: {value}"); 
    Console.ReadLine(); 
}