6

在我当前的项目中，我必须对一些事情使用稀疏向量。但是，由于我不负责这个项目，所以我不能使用我想要的任何外部库。我只有 STL 和 OpenCV 可用。

我已经查看了几个 stackoverflow 回答的问题，但它们要么专注于特定方法，而是在专门处理稀疏向量时比较有限数量的方法 (2) 和外部库。实现稀疏矩阵也有一些很好的想法。

我想要的是一个稀疏向量（索引总是一维的，数据与这个问题无关）。我想要的东西不会是一个单独的项目来实现，但可以用于不仅仅是演示目的（例如，我想达到一个不错的速度而不是太多的内存开销），并希望重新 -以后用。我考虑过的选项包括：

  • 根据我的需要调整SparseMat的OpenCV实现
  • 使用 astd::map来存储值（或者可能制作一个非常简单的包装器，在索引零元素的情况下将返回默认值）
  • 使用我可以在元素std::vector< std::pair < int , data_type > >中存储索引和数据的地方std::pair

对于作为稀疏向量的通用用途，这些解决方案中的任何一个是否更好/更差？我知道每件事的每一种方法都有其起伏，但非常感谢关于选择哪种方法的有争议的建议。此外，如果有人认为他有更好的建议，推荐一种我没有考虑过的方法将非常受欢迎。

在我的具体情况下的用法如下：

  • 向量在创建后很可能不会被修改（现在我认为没有任何必要，但我不能保证 100% 它不会出现）
  • 预计最常见的操作是两个这样的向量的点积（因此，或多或少地以线性顺序方式访问元素）
  • 我现在可以预见的唯一查找是（也许）检查天气某个元素是否为零元素
  • 预计会有大约 500 个非零元素
  • 简而言之，大多数时候稀疏向量将用作向量（多维点）的数学概念，而无需单独检查每个坐标

尽管如此，正如我在最初的问题中所写的那样，我想要关于通用稀疏向量实现的建议。

4

2 回答 2

6

我相信std::map会给你最好的结果。SpareseMat，我不知道，但在你提到的另外两种方法中，std::map会给你O(log(n))查找以及O(log(n))插入和删除。然而，vector需要搜索其所有数据（因此它具有O(n)查找功能）。它有O(1)插入，但有O(n)移除。我的猜测是你会有很多查找，所以很可能std::map对你更好。

根据您的应用程序，您可能希望vector在结构的初始创建期间使用该方法，然后map在开始使用它时将其转换为两全其美（但通常情况并非如此，例如在以下情况下你有重复的索引）。

除此之外hash，它应该给你O(1)一切，但实际上可能不会，查找O(log(n))是你所希望的最好的。您可能会想出一个可以二进制搜索的向量，或者基于通过比较搜索数据的任何其他方法，但最终它们都会O(log(n))如此，所以您不妨使用 easy-already-done std::map。

更新：根据您问题的更新，这表明向量在创建后很可能不会被修改，并且最常见的操作预计是点积，我建议如下：

首先，使用您自己建议的成对向量。在创建过程中，push_back您只需简单地获得O(1)性能。1之后，您可以对向量进行排序。点积将非常简单2：

int dot = 0;
unsigned int index_v1 = 0, index_v2 = 0;
while (index_v1 < v1.size() && index_v2 < v2.size())
    if (v1[index_v1].first == v2[index_v2].first)
        dot += v1[index_v1++].second * v2[index_v2++].second;
    else if (v1[index_v1].first < v2[index_v2].first)
        ++index_v1;
    else
        ++index_v2;

检查某个元素是否为零元素将是一个简单的二进制搜索，检查是否可以找到该元素（O(log(n))性能）。

鉴于您将使用此结构作为一个点，我相信将其保留为向量会更好。您可能希望稍后进行叉积或其他几何运算。

关于您可能需要不时在向量中插入一些东西的事实，那么您必须将它插入到位（因此向量保持排序）。性能会是O(n)，但由于它不经常发生，所以它不应该是一个问题。

1除非你有数以百万计的这些向量，O(1)并且O(log(n))forn ~= 500不应该真正产生任何明显的差异。

2您当然也可以使用 amap并在其上使用迭代器按索引顺序进行点积。std::map如果使用可以让您到达下一个节点的线程树，性能将相同O(1)。

于 2012-05-29T10:12:22.850 回答
3

吻

从最简单的解决方案开始，即包装std::map<size_t, YourData>成特定的稀疏向量结构：

template <typename V>
class SparseVector {
public:

private:
    std::map<size_t, V> specificValues;
    V defaultValue;
};

这map将在所有用例（查找/插入/更新）中提供良好的默认性能，并且使用自定义类意味着如果您需要更改为另一个实现，则无需更改客户端源，只需重新编译即可。

于 2012-05-29T10:20:35.910 回答