使用键值范围的字典对象 [英] A dictionary object that uses ranges of values for keys

问题描述

我需要一种专门的字典。我的用例是这样的：用户想要指定值的范围（范围也可以是单个点），并将值分配给特定的范围。然后，我们要使用单个值作为键执行查找。如果这个单一值发生在一个范围内，那么我们将返回与范围相关联的值。

例如：

  //表示键值
 struct Interval 
 {
 public int Min; 
 public int Max; 
} 
 
 //程序中某些代码
 var dictionary = new Dictionary< Interval，double>（）; 
 dictionary.Add（new Interval {Min = 0，Max = 10}，9.0）; 
 var result = dictionary [1]; 
 if（result == 9.0）JumpForJoy（）; 
  

这显然只是一些代码来说明我正在寻找什么。有没有人知道一个算法来实现这样的事情？如果可以，我们可以指向我吗？

我已经尝试实现一个自定义IEqualityComparer对象，并在Interval上重载Equals（）和GetHashCode（），但无效至今。可能是我在做错事了。

解决方案

字典不是适合您操作的数据结构描述。

如果需要间隔时间不要重叠，那么您可以建立一个排序的间隔列表并进行二进制搜索。

如果间隔可以重叠，那么你有一个更难解决的问题。为了有效地解决这个问题，你需要建立一个间隔树：

http://en.wikipedia.org/wiki/Interval_tree

这是一个众所周知的数据结构。请参见算法简介或数据结构中任何其他体面的本科文本。

I have need of a sort of specialized dictionary. My use case is this: The user wants to specify ranges of values (the range could be a single point as well) and assign a value to a particular range. We then want to perform a lookup using a single value as a key. If this single value occurs within one of the ranges then we will return the value associated to the range.

For example:

// represents the keyed value
struct Interval
{
    public int Min;
    public int Max;
}

// some code elsewhere in the program
var dictionary = new Dictionary<Interval, double>();
dictionary.Add(new Interval { Min = 0, Max = 10 }, 9.0);
var result = dictionary[1];
if (result == 9.0) JumpForJoy();

This is obviously just some code to illustrate what I'm looking for. Does anyone know of an algorithm to implement such a thing? If so could they point me towards it, please?

I have already tried implementing a custom IEqualityComparer object and overloading Equals() and GetHashCode() on Interval but to no avail so far. It may be that I'm doing something wrong though.

解决方案

A dictionary is not the appropriate data structure for the operations you are describing.

If the intervals are required to never overlap then you can just build a sorted list of intervals and binary search it.

If the intervals can overlap then you have a more difficult problem to solve. To solve that problem efficiently you'll want to build an interval tree:

http://en.wikipedia.org/wiki/Interval_tree

This is a well-known data structure. See "Introduction To Algorithms" or any other decent undergraduate text on data structures.

这篇关于使用键值范围的字典对象的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！