不使用外部库的稀疏矢量实现建议

Question

我必须在当前项目中使用稀疏向量来处理某些事情.但是,由于我不负责该项目,我不能使用我想要的任何外部库.我只有STL和OpenCV可用.

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

我想要的是一个稀疏的向量(索引总是在一维,数据与这个问题无关).我想要的东西不是自己实现的项目,但可以用于超出示范目的(例如,我希望获得合适的速度而不是太多的内存开销)并且希望重新以后用过.我考虑的选项包括:

• 根据我的需要调整SparseMat的OpenCV实现
• 使用a std::map来存储值(或者可以创建一个非常简单的包装器,在索引零元素的情况下返回默认值)
• 使用std::vector< std::pair < int , data_type > >我可以将索引和数据存储在std::pair元素中的位置

对于作为稀疏向量的通用目的,这些解决方案中的任何一个是更好/更差吗？我知道每件事的每一种方法都有它起伏不定,但是我们非常赞赏有关选择哪种方法的建议.此外,如果有人认为他有更好的建议,推荐一种我没有考虑过的方法会更受欢迎.

---

我具体情况的用法如下:

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

尽管如此,正如我在原始问题中所写的那样,我想了解通用稀疏矢量实现的建议.

Answer 1

我相信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))如此,您可以使用已经完成的简单方法std::map.

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

首先,使用您自己建议的对向量.在创作过程中,push_back您只需获得O(1)表现.¹之后,您可以对矢量进行排序.点积将非常简单²:

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),但由于它不经常发生,因此不应成为问题.

¹除非你有几百万的这些载体,O(1)并O(log(n))为n ~= 500真的不应该做任何明显的差异.

²你绝对可以使用a map并使用迭代器来按照索引的顺序来做点积.如果std::map使用一个允许你到达下一个节点的线程树,性能将是相同的O(1).