数据结构，C#：~O(1)带范围键的查找？

Question

我有一个数据集。此数据集将提供查找表。给定一个数字，我应该能够查找该数字的相应值。

不过，数据集(假设是它的CSV)有一些注意事项。而不是：

1,ABC
2,XYZ
3,LMN

数字是范围(-是“通过”，而不是减号)：

1-3,ABC     // 1, 2, and 3 = ABC
4-8,XYZ     // 4, 5, 6, 7, 8 = XYZ
11-11,LMN   // 11 = LMN

所有的数字都是有符号整数。没有与其他范围重叠的范围。有一些差距；有一些范围没有在数据集中定义(比如上面最后一个片段中的9和10 )。`

如何在C#中对此数据集进行建模，以便在保持较低内存占用的同时获得最高性能的查找？

我想出来的唯一选择就是内存消耗过多。假设我的数据集是：

1-2,ABC
4-6,XYZ

然后我创建一个Dictionary<int,string>()，它的键/值是：

1/ABC
2/ABC
4/XYZ
5/XYZ
6/XYZ

现在我有了哈希性能-查找，但在哈希表中浪费了大量空间。

有什么想法吗？也许只需要使用PLINQ来代替，并希望有好的性能？;)

Answer 1

如果您的字典要真正存储大范围的键值，那么将所有可能的范围扩展为显式键的方法将很快消耗比您可用的内存更多的内存。

最好的选择是使用支持二进制搜索某种变体的数据结构(或其他O(log )查找技术)。这是一个在内部使用OrderedList的link to a generic RangeDictionary for .NET，性能为O(log )。

要实现恒定时间O(1)查找，需要将所有范围扩展为显式键。这需要大量内存，而且当您需要拆分或插入新范围时，实际上可能会降低性能。这可能不是您想要的。

Answer 2

作为arootbeer has mentioned in his answer，以下代码不会创建字符串“ABC”的多个实例；相反，它实例化单个实例，并将对该实例的引用分配给dictionary中的每个KeyValuePair<int, string>

var dictionary = new Dictionary<int, string>();
dictionary[0] = "ABC";
dictionary[1] = "ABC";
dictionary[2] = "ABC";

// etc.

好的，在字符串文字的情况下，每个键范围只使用一个string实例。有没有不是这样的场景--也就是说，您将为范围内的每个键使用一个单独的string实例(当您谈到“内存过度消耗”时，我假设您关心的就是这个)？

老实说，我不这么认为。在某些情况下，可能会创建多个等价的string实例，而不需要使用interning，是的。但我无法想象这些场景会影响你在这里尝试做的事情。

我的推理是这样的:您希望将某些值分配给不同范围的键，对吗？因此，无论何时定义这种键-范围-值对，都会有一个值和多个键。单个部分使我怀疑您是否会有同一字符串的多个实例，除非它被定义为多个范围的值。

为了说明:是的，下面的代码将实例化两个相同的字符串：

string x = "ABC";

Console.Write("Type 'ABC' and press Enter: ");
string y = Console.ReadLine();

Console.WriteLine(Equals(x, y));
Console.WriteLine(ReferenceEquals(x, y));

上面的程序假设用户按照说明输入"ABC“，输出True，然后输出False。所以你可能会想，“啊，所以当一个字符串只在运行时提供时，它不会被占用！所以这可能是我的值可能被复制的地方！”

但是..。再说一次：我不这么认为，。这一切都回到了这样一个事实，即您将为一系列键分配单个值。假设您的值来自用户输入；那么您的代码将如下所示：

var dictionary = new Dictionary<int, string>();

int start, count;
GetRange(out start, out count);
string value = GetValue();

foreach (int key in Enumerable.Range(start, count))
{
    // Look, you're using the same string instance to assign
    // to each key... how could it be otherwise?
    dictionary[key] = value;
}

现在，如果您实际上更多地考虑LBushkin mentions in his answer--您可能有很大的范围，因此为该范围内的每个键定义一个KeyValuePair<int, string>是不切实际的(例如，如果您的范围是1-1000000)--那么我同意您最好使用某种基于二进制搜索的数据结构。如果这是你的方案，请说出来，我很乐意在这方面提供更多的想法。(或者你可以只看一下LBushkin已经发布的链接。)

Answer 3

arootbeer有一个很好的解决方案，但你可能会发现使用起来很混乱。

另一种选择是使用引用类型而不是字符串，以便指向相同的引用

class StringContainer { 
    public string Value { get; set; }
}

Dictionary<int, StringContainer> values;

var value1 = new StringContainer { Value = "ABC" };
values.Add(1, value1);
values.Add(2, value1);

它们都将指向相同的StringContainer实例

编辑:感谢大家的评论。此方法处理string以外的值类型，因此它可能不仅仅适用于给定的示例。此外，据我所知，字符串并不总是以您期望的方式从引用值中表现出来，但我可能错了。