<分区>
我需要一个容器来存储稀疏矩阵。矩阵的大小约为 20,000*3,000,000。但是有空隙，所以实际的矩阵大概是20000*500000。并且只占用了实际矩阵的 1%。
我需要保留索引，类似于二维数组。但是二维数组无法将整个数据集放入内存。我找到了具有 mapped_matrix、compressed_matrix、coordinate_matrix 的 boost 库。
我想知道有什么区别？无法从 their documentation 中找出答案.
是否还有其他标准库具有稀疏矩阵容器并且可以使用索引访问？
最佳答案
我发现了这个:
sparse_matrix:此类型是 std::map > 的实现。因此，元素的插入需要 O(log(M)+log(K)) 操作加上存储分配，这应该是(摊销的)常数时间。缺点是遍历所有元素、某些间接级别(指针)和非连续存储的速度较慢。
compressed_matrix:这种类型是压缩行存储的一种实现，该存储从 Netlib (www.netlib.org) 中获知，被 FORTRAN 线性代数库广泛使用。简而言之:我们有一个值 vector 、一个与该值对应的列索引 vector 和一个每行开始的指针 vector 。如果必须将值和列索引移动一个位置，则插入一个元素需要 O(log(M)+log(K)) 操作加上 O(M*K) 存储操作。按 push_back(i,j,value) 顺序添加元素是常数时间。增加一个 existend 元素只需要 O(log(M)+log(K)) 操作。优点是元素遍历非常快，这为线性代数例程提供了最佳性能。
coordinate_matrix:此类型是使用三个 vector 实现的三元组 (i,j,value) 列表。因此，您可以通过 insert(i,j,value) 以随机顺序插入元素，其作用类似于 A(i,j) += value。这实际上不同于其他矩阵类型的插入操作。您付出的代价是在访问每个元素之前进行 sort() 操作，并且如果您多次插入多个元素，则需要额外的存储空间。 sort() 对所有元素进行排序，并将一个元素的多次插入合并为一个。因此，根据方法的不同，元素的插入是常数时间加上最后一个 sort() 以进行 O(M*K log(MK)) 操作。 (根据 Stroustrup，“C++”:std::sort() 具有平均 O(nlog(n))，最坏情况 O(nn)，std::stable_sort() 具有 O( n*log(n)log(n)) 加上 O(nlog(n)) 存储。)对于这种类型的线性代数运算通常比压缩矩阵慢。
引用:http://www.guwi17.de/ublas/matrix_sparse_usage.html
如果您在阅读他们的文档时遇到同样的问题，希望这对您有所帮助。
关于C++ 稀疏矩阵容器，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35284783/