在C++中处理大矩阵

4
我在C++中使用大型的double矩阵。我需要从这些矩阵中获取行或列,并将它们传递给函数。最快的方法是什么?
  1. 一种方法是编写一个函数,该函数作为std :: vector返回所需行或列的副本。
  2. 另一种方法是将整个内容作为引用传递,并修改函数以能够读取所需的值。
还有其他选择吗?你推荐哪种? 顺便问一下,你建议我如何存储矩阵类中的数据?我现在正在使用std :: vector >。 编辑 我必须提到这些矩阵可能具有多个维度。因此,在此处使用boost或arma :: mat不行。虽然我在库的其他部分中使用了armadillo。

5
使用vector<vector>不是很好的选择 - 可以使用单个向量并提供运算符E operator()(row,column) - user2249683
如果您的矩阵是一个vector<vector<double>>,那么您可以传递对行的引用(即vector<double>&)。 - 463035818_is_not_a_number
我还没有尝试过,但是boost 1.58有一个线性代数库,其中包括密集和稀疏矩阵实现。 - odedsh
4
这实际上取决于函数正在执行什么操作以及矩阵的大小。例如,如果该函数多次访问某一列的元素,则复制该列可能是最好的选择,因为它会有更好的缓存使用效果。在考虑性能时,您需要测量实际使用情况。 - Vaughn Cato
Armadillo有一个Cube类,可以像“3D矩阵”一样处理。 - mtall
5个回答

3
如果需要使用超过2个维度的变量,可以查看boost's multidimensional array library。它拥有高效(无需复制)的“views”,您可以使用这些视图引用完整矩阵的低维“切片”。 对于这种情况下什么是“最快”的细节取决于您正在做什么以及访问模式/工作集“足迹”如何适应硬件的各个级别的缓存和内存延迟;实际上,值得将更多内容复制到更紧凑的表示中,以获得更多的缓存一致性访问,而不是进行稀疏分散的访问,这只会浪费大量缓存行。另外,Morton-order 访问方案可以将“坏轴”效应分摊到所有轴上。然而,只有在自己的代码和用例上进行基准测试才能真正回答这个问题。 (请注意,对于二维数组,我不会使用Boost.MultiArray-在线性代数/图像处理应用中有更快,更好的选择-但对于三个或更多维度,值得考虑。)

2
我会使用像http://arma.sourceforge.net/这样的库。因为你不仅可以得到存储矩阵的方法,还有可以对其进行操作的函数。

Armadillo(上述库)是一个不错的选择 - 特别是如果您需要与MATLAB交互。Eigen3也非常强大,而且是仅有头文件的,这可能很方便。 - user888379

2
高效(多)线性代数是一个令人惊讶的深入领域;没有通用的简单答案。主要的挑战是数据局部性:计算机的内存硬件被优化为访问连续的内存区域,可能无法操作除缓存行之外的任何东西(即使它可以,效率也会降低)。 缓存行的大小不同,但通常为64或128字节。 因此,将矩阵中的数据布局得能够在多个方向上高效访问是一个非平凡的挑战;对于更高秩的张量来说更是如此。 此外,最佳选择可能严重依赖于您对矩阵的具体使用方式。 您的问题真的不能以问答形式令人满意地回答。 但至少可以让您开始研究,以下是两个值得研究的关键词: 块矩阵 快速转置算法 您可能会更好地使用库而不是尝试自己编写;例如blitz++。(免责声明:我没有使用过blitz++)

1

vector<vector<...>>的分配、释放和访问速度都很慢,因为它有多个解除引用(不适合缓存)。

我建议只在你的行或列大小不相同时(锯齿状数组)使用它。

对于“正常”的矩阵,你可以选择类似以下的东西:

template <class T, size_t nDim> struct tensor {
    size_t dims[nDim];
    vector<T> vect;
};

重载operator(size_t i, size_t j, etc.)以访问元素。

operator()将必须进行索引计算(您必须在行主序或列主序之间进行选择)。对于nDim > 2,它变得有些复杂,可以从缓存一些索引计算中获益。

要返回行或列,您可以定义子类型。

template <class T, size_t nDim> struct row /*or column*/ {
    tensor<T, nDim> & tensor;
    size_t iStart;
    size_t stride;
}
然后定义一个operator(size_t i),它将返回tensor.vect[iStart + i*stride] stride的值取决于它是行还是列以及您的(行主或列主)顺序选择。 对于其中一个子类型,stride将为1。请注意,对于此子类型,迭代可能会快得多,因为它将具有良好的缓存友好性。对于其他子类型,不幸的是,迭代可能会相当慢,并且您无法做太多事情来改变它。 请参阅其他SO问题,了解为什么按行然后按列迭代与按列然后按行迭代可能会有巨大的性能差异。

0

我建议您通过引用传递它,因为复制可能会根据大小而变得缓慢。如果您想要扩展和收缩容器的能力,std::vector是可以的。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,