我想要一个
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"
谁能推荐一下?
最佳答案
如果你希望能够使用类似 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})");
结果如下:
因此,除非您计划处理此数据集中的超过数千万条记录,否则像这样的方法应该在性能方面令人满意。
关于c# - 我想要以 (start,end) 为键的数据结构,然后能够在整个数据结构中搜索整数并获得相应的值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54655539/