1

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

  1. 我在数组中寻找一个键。
  2. 如果我找到密钥，我将添加到存储在该密钥中的值。
  3. 如果我没有找到密钥，我会找到下一个最高和下一个最低的密钥。
  4. 如果两个邻居中的较近者足够接近，那么我会使用该键值对进行累加。
  5. 否则我添加一个新的键值对。

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

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

推荐什么数据结构？Wikipedia 提到了一些，例如 Trie、Judy 数组等。

（几年前我实现了一些类似 Trie 的东西，但那是在 java 中实现的，花了我一周的时间来实现，而且很棘手。我时间紧迫。）

更新：

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

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

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

我需要进行性能测试，看看它是否足够快。但即使没有，具有相同合约的另一个集合也是 FindNextHighestKey 和 FindNextLowestKey 的可接受替代方案。

更新 2：

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

4

2 回答 2

1

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

于 2013-01-11T15:02:50.793 回答
1

我发现了这个问题，这让我明白了SortedSet<T>。

如果您可以处理 O(log(n)) 以进行插入、删除和查找，那么这可能是您应该保留密钥的地方。

根据您的新要求...为什么不在使用前按粒度将双精度映射到稀疏键并使用 a Dictionary<double, T>？如果您希望在运行时更改粒度，这将不起作用，但其他方法也不会真正起作用。

于 2013-01-11T15:11:52.003 回答