c# - 需要在插入时快速的关联数组，找到最近的键，并按键顺序迭代

Question

我正在执行类似于 N 维卷积的操作，但在我继续操作时会合并彼此接近的值，以节省内存和时间。

1. 我在数组中寻找一个键。
2. 如果我找到了键，我会添加到存储在该键中的值。
3. 如果找不到 key ，我会找到下一个最高和下一个最低的 key 。
4. 如果两个邻居中距离最近的那个足够近，那么我就用那个键值对累加。
5. 否则我添加一个新的键值对。

key 是 double 的。它总是积极的，永远不会是无限的。 (我专门处理零。)我希望值的范围从几美分到高达 1000 亿。舍入粗糙度将随着算法的进行而改变，以将最大数组大小保持在 10,000 和 1,000,000 之间。 (只有测试才能揭示速度、内存和准确性之间权衡的最佳点。)由于值的范围与数组大小的关系，直接寻址是不切实际的；我需要稀疏存储。

天真的方法是使用 List 并执行 BinarySearch 来查找键或插入点，然后从那里继续。这可以快速找到最近的键，可以按键顺序迭代，但插入很糟糕。 (我不需要执行删除!外循环中的每次迭代都会从头开始创建一个新列表。)

推荐什么数据结构？维基百科提到了一些，像 Trie，Judy 数组等。

(我几年前实现了一些类似 Trie 的东西，具有相似的特征，但那是在 java 中，我花了一个星期的时间来实现，而且很棘手。我时间紧迫。)

更新:

SortedSet 的建议让我修改了我的需求。虽然找到下一个最低和下一个最高键是我完成任务的方式，但 SortedSet.GetViewBetween 以不同的方式处理事情。因为我只想看看是否有足够接近的值可以聚合，并且我有一定的舍入粒度 G，所以我可以使用

询问所有感兴趣的元素

var possibilities = mySet.GetViewBetween(x - G, x + G)

如果那个集合是空的，我需要添加。如果不是，它可能是一个小集合，我会遍历它。

我需要执行性能测试以查看它是否足够快。但即使不是这样，具有相同协定的另一个集合也是 FindNextHighestKey 和 FindNextLowestKey 的可接受替代方案。

更新 2:

我决定使用普通字典，并使用自定义舍入函数将键强制放入桶中。按排序顺序迭代项目并不重要，通过使用这个舍入函数，我可以找到“足够接近”的值来聚合。我不会在一次迭代中改变粒度；每次和一个新的维度卷积完我都会调整它。每次迭代我都会创建一个新数组来保存该遍的结果。

Answer 1

如果您的 key 是唯一的，您可以查看 Dictionary<TKey,TValue>或 SortedDictionary<TKey,TValue>