c# - 从 C# 中的数据结构中查找带有一些 epsilon 的 float ，搜索并插入 O(lg n) 时间

Question

在 C++ 中，我能够使用 std::map<double, T>这是其键的有序字典，但它是一棵红黑树，它为我提供了插入和搜索的 O(lg n)。我能够通过使用 std::lower_bound 来查找某个值是否存在于某个 epsilon 中。和 std::upper_bound在一起。

我在使用 C# 7+/.NET Core 时找不到相同的东西。有这种东西吗？

在伪代码中，我想做这样的事情

Map<float, T> map = ...
//         key    epsilon  newValue
map.Insert(0.5f,  0.1f,    someObj);  // No values in the map, inserts fine
map.Get(   0.45f, 0.1f);              // 0.45 +/- 0.1 contains 0.5, would return someObj
map.Get(   0.3f,  0.1f);              // 0.3 +/- 0.1 does not include 0.5, it is not found
map.Insert(0.55f, 0.1f, anotherObj);  // 0.55 +/- 0.1 includes 0.5, replace someObj
map.Insert(0.35f, 0.1f, anObj);       // 0.35 +/- 0.1 doesn't overlap, insert new value

我必须这样做的方法是滚动我自己的自平衡二叉搜索树，但如果存在这样的东西，我宁愿不重新发明轮子。

我一直在看SortedDictionary , 然而它的 Keys field 是一个集合，所以我不能在里面跳来跳去。 OrderedDictionary 同样的问题，除非我错过了什么。

我可能无法使用 SortedList，因为插入次数多于查找次数，而且由于随机顺序，我担心最终会得到很多 O( n) 插入时需要进行的交换。我假设我的输入是均匀分布的(由于我正在处理的数据，这很可能是这种情况)，这意味着如果它以这种方式实现，那么向中间和前面的插入会导致很多移动我认为确实如此......这平均会给我 n/2 次插入的成本并让我处于 O(n)。至少对于二叉搜索树，我得到了 O(lg n)。因此 good solution here可能不适用。

最重要的是，这是一个在代码非常热门的部分使用的算法。性能非常重要，选择速度不快的东西可能会严重损害应用程序的性能。我真的需要 O(lg n) 或一些我以前没有想到的新颖方法。

Answer 1

我的想法是结合两种数据结构，SortedSet 和正则映射。

SortedSet 具有 GetViewBetween 方法，具有预期的性能。 https://github.com/dotnet/corefx/pull/30921

注意:此方法的预期性能仅在 .NET Core 中得到满足，过去速度要慢得多:Why SortedSet<T>.GetViewBetween isn't O(log N)?

在此集合中，您只保留 float 键。此外，您还有一个从 float 到所需类型的映射。只有在检查 SortedSet 后，您才能在 map 上执行操作。

我意识到有一些粗糙的边缘(当一个间隔在 SortedSet 中给出一些条目时)，但我相信这等同于 cpp 实现。

希望这对您有所帮助，祝您实现顺利。