c# - 我想要以 (start,end) 为键的数据结构，然后能够在整个数据结构中搜索整数并获得相应的值

Question

我想要一个

data structure with <Key, Value> where
  Key = (start, end), 
  Value = string

之后我应该能够在数据结构中最优地搜索一个整数并得到相应的值。

例子:

var lookup = new Something<(int, int), string>()
{
  {(1,100),"In 100s"},
  {(101,200),"In 100-200"},
}

var value1 = lookup[10]; //value1 = "In 100s"
var value2 = lookup[110]; //value2 = "In 100-200"

谁能推荐一下？

Answer 1

如果你希望能够使用类似 lookup[10] 的东西正如您提到的，您可以创建自己的类来实现某种键/值数据类型。您最终决定使用哪种基础数据类型实际上取决于您的数据的外观。

这是一个在实现 Dictionary<> 时执行此操作的简单示例:

public class RangeLookup : Dictionary<(int Min, int Max), string>
{
    public string this[int index] => this.Single(x => x.Key.Min <= index && index <= x.Key.Max).Value;
}

这允许您定义自定义 indexer在字典之上封装你的范围查找。此类的用法如下所示:

var lookup = new RangeLookup
{
    { (1, 100), "In 100s" },
    { (101, 200), "In 101-200s" },
};

Console.WriteLine($"50: {lookup[50]}");

产生的输出为:

---

就此方法的性能而言，以下是一些测试示例(使用 Win10 和 Intel i7-4770 CPU)从具有 10,000,000 条记录的字典中检索值:

var lookup = new RangeLookup();

for (var i = 1; i <= 10000000; i++)
{
    var max = i * 100;
    var min = max - 99;
    lookup.Add((min, max), $"In {min}-{max}s");
}

var stopwatch = new Stopwatch();

stopwatch.Start();
Console.WriteLine($"50: {lookup[50]} (TimeToLookup: {stopwatch.ElapsedMilliseconds})");

stopwatch.Restart();
Console.WriteLine($"5,000: {lookup[5000]} (TimeToLookup: {stopwatch.ElapsedMilliseconds})");

stopwatch.Restart();
Console.WriteLine($"1,000,000,000: {lookup[1000000000]} (TimeToLookup: {stopwatch.ElapsedMilliseconds})");

结果如下:

因此，除非您计划处理此数据集中的超过数千万条记录，否则像这样的方法应该在性能方面令人满意。