c++ - c++ 稀疏向量

Question

问题1）

我在 C++ 中有一个大的稀疏双精度向量，我需要从向量中有效地解析出非零元素的索引。我显然可以遍历长度并做到这一点，有更好的方法吗？

Answer 1

除非您对双打向量的构成有一些特殊的了解（例如，它已排序），否则您将获得最有效的循环。

当然，您可能应该考虑 eladidan 建议的结构变化。

Answer 2

我在 C++ 中有一个大的稀疏双精度向量，我需要从向量中有效地解析出非零元素的索引。我显然可以遍历长度并做到这一点，有更好的方法吗？

如果向量是真正稀疏的（n = o(N)其中n是非零元素的数量并且N是向量的大小），那么用std::map<int,double>or表示它std::unordered_map<int,double>可能是最好的。通过std::map方式，您可以在O(log(n)). 使用std::unordered_map查找操作需要的摊销时间为O(1). 在这两种情况下，非零元素的数量只是容器的大小。这两种方法也占用O(n)空间而不是O(N).

Answer 3

如果您无法更改数据的表示，则必须检查每个元素以过滤掉几乎等于零的元素。然而，这个任务是令人尴尬的并行，所以也许你可以将工作负载划分为一堆线程，以至少提高运行时间（尽管不是复杂性）。