c# - 数据结构，C# : ~O(1) lookup with range keys?

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 N) 查找技术)的数据结构。这是一个 link to a generic RangeDictionary for .NET在内部使用 OrderedList，并具有 O(log N) 性能。

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