时间戳

首页 > 解决方案 > 从 C# 中的数据结构中查找带有一些 epsilon 的浮点数，同时搜索和插入 O(lg n) 时间

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

问题描述

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

我在使用 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领域是一个集合，所以我不能在里面跳来跳去。同样的问题OrderedDictionary，除非我错过了什么。

我可能无法使用 SortedList，因为插入会比查找更多，并且由于随机顺序，我担心我最终会得到很多 O(n) 交换，需要在插入时完成. 我假设我的输入是均匀分布的（这很可能是因为我正在使用的数据），这意味着如果以这种方式实现它，向中间和前面的插入会导致很多变化我认为确实如此......这将使我平均花费 n/2 次插入并使我留在 O(n)。至少使用二叉搜索树，我得到 O(lg n)。因此，这里的好解决方案可能不适用。

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

标签： c#

解决方案

我的想法是结合两个数据结构，SortedSet 和一个常规映射。

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

注意：此方法的预期性能仅在 .NET 核心中得到满足，过去要慢得多：Why SortedSet<T>.GetViewBetween is not O(log N)?

在这个集合中，您只保留浮动键。此外，您还有一个从 float 到所需类型的 Map。只有在检查了 SortedSet 之后才能在地图上执行操作。

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

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

推荐阅读