什么数据结构（或实现它的 C++ 库）最适合高效的高维直方图？
）中计算类似于直方图的东西。即使具有较大的线性 bin 大小，总的 bin 也会太多。但是，我事先知道，在完成计算后，只有一小部分 bin 会保持非零值（尽管很难估计是哪一个）。
因此，我需要一个支持非常快速索引和快速更新的“稀疏数组”。稀疏数组有许多可能的表示。
为了节省很多基准测试，我想知道哪个（或更好：哪个特定的 C++ 实现）将为这项任务执行“最好的”。
高效高维直方图的数据结构
计算科学
稀疏矩阵
高维
2021-12-04 09:20:38
1个回答
如果 bin 的索引是整数的一些，一种可能可行的方法是为 bin 索引提供哈希函数并使用C++ 标准模板库中的. 对于串行性能，很难击败经过良好调整的哈希表实现。unordered_map
你当然需要一个好的散列函数。表示 bin 索引的简单方法是使用std::array<size_t, d>; 不幸的是，数组没有内置的散列函数，因此您必须专门std::hash针对您的用例。您可以组合两个数字的哈希值，m并n通过计算p * hash(m) + hash(n)wherep是一个大素数。将它迭代地应用于整个数组应该会给你一个很好的散列函数。您也可以使用boost::hash_combineor boost::hash_range，但 boost 是一个很大的依赖项。在任何情况下，您都可能希望对实际输入进行一些基准测试，以确保没有很多哈希冲突。
哈希表仅用于存储目的就可以正常工作，但如果您需要更复杂的空间查询，它就不够用了。例如，给定一个非空 bin，您可能希望找到个最近的非空 bin。传统的数据结构（如 kd 树或八叉树）在高维数据上的表现非常糟糕。我没有使用它们，所以我无法评论它们的效率，但是应该优雅地处理高维输入的 X-trees 和 PK-trees。
其它你可能感兴趣的问题