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