C++中COO格式稀疏矩阵的排序

vdzxcuhz  于 2022-11-27  发布在  其他
关注(0)|答案(3)|浏览(93)

我在程序中使用COO格式的稀疏矩阵。COO格式使用3个独立的向量来表示矩阵:rowindex、colindex和values。我需要先按rowindex再按colindex对矩阵排序。例如,如果向量包含:

rowindex = [1 2 2 1 0 2 0 1 0 2 1 2]
colindex   = [7 7 2 1 3 9 8 6 6 0 3 4]
values      = [0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 1.1 1.2]

(意味着矩阵中的元素[1,7]具有值0.1,元素[2,7]具有值0.2,元素[2,2]具有值0.3,等等)排序后的矩阵应该是:

rowindex = [0 0 0   1 1 1 1   2 2 2 2 2]
colindex  = [3 6 8   1 3 6 7   0 2 4 7 9] 
values     = [0.5 0.9 0.7 0.4 1.1 0.8 0.1 1.0 0.3 1.2 0.2 0.6]

我在期望的结果中留了一些更多的空间,以便(希望)更好地显示我想要实现的目标。
这是否可以通过某种方式实现:

  • 使用C++中可用的排序函数
  • 不使用额外的内存(例如额外的向量),因为我使用的稀疏矩阵非常大,几乎占用了所有内存
  • 而不必求助于将矩阵表示为结构体数组(我知道可以在其中使用sort()函数)。

我找到了一些关于对多个向量进行排序的答案,只对其中一个向量的值进行排序。它们不需要根据第二个向量对第一个向量中具有相同值的元素进行排序。

vsnjm48y

vsnjm48y1#

通常情况下,可以对COO中给出的稀疏矩阵进行排序,但不能对约束条件进行排序。

  • 使用C++中可用的排序函数:基本上是不可能的,因为std::libraries中现有的排序函数只能在一个范围内工作。即使把其他vectors放在 predicate 闭包中,并得出一些复杂的lambda函数,或者把所有的东西都放在Functor中,这也是没有意义的可行性。
  • 将需要额外的空间,将使解决方案可行和容易解决。
  • 与约束3相同。

所以,你需要制作comprimises。或者使用非标准的C++库。

55ooxyrt

55ooxyrt2#

在对这个问题进行了更多的思考之后,我决定采用另一种方法。不是从相应的文件中阅读整个稀疏矩阵,然后对它进行排序,而是在读取的同时对它进行排序。从文件中读取的每个元素都直接插入到正确的位置。对于感兴趣的人,执行排序的程序部分如下所示。在我测试的情况下,可以正常工作。

row = read value from file (zero-based indexing)
col = read value from file (zero-based indexing)
val = read value from file

/*
 * Identify the easy cases:
 *   - Insertion of the first element or
 *   - The new element must be inserted at the end of the vectors
 *
 * The second case could be handled by the 'else', but handling it this way
 * avoids more expensive searches by equal_range() and upper_bound().
 */
if ((rowindex.empty()) ||
     ((row >= rowindex[rowindex.size() - 1]) && (col >  colindex[colindex.size() - 1]))) {
        rowindex.push_back(row);
        colindex.push_back(col);
        values.push_back(val);
} else {
/*
 * Find the elements of the same row as the element being inserted into the matrix.
 *
 * If this is the first element in a specific row, the two iterators returned by equal_range()
 * point to the first element of the next larger row.
 *
 * If there are already other elements in the same row, the two iterators returned by equal_range()
 * point to the first element of the row and the first element of the next larger row.
 *
 * Using the iterators also calculate indices to the elements returned by equal_range().
 * These are used to index the corresponding elements in the other two vectors representing
 * the sparse matrix (colindex and values).
 */
    const auto p = equal_range(rowindex.begin(), rowindex.end(), row);
    const auto index_of_first = p.first  - rowindex.begin();
    const auto index_of_last  = p.second - rowindex.begin();

/*
 * Create iterators to point to the corresponding elements in colindex.
 */
    const auto first = next(colindex.begin(), index_of_first);
    const auto last  = next(colindex.begin(), index_of_last);

/*
 * Find the correct position where the new element must be inserted and perform the corresponding
 * insertions into the three vectors representing the sparse matrix.
 */
    auto col_pos_it = upper_bound(first, last, col);
    auto pos = col_pos_it - colindex.begin();
    colindex.insert(col_pos_it, col);

    auto row_pos_it = next(rowindex.begin(), pos);
    rowindex.insert(row_pos_it, row);

    auto val_pos_it = next(values.begin(), pos);
    values.insert(val_pos_it, value);
}
mgdq6dx1

mgdq6dx13#

C++23将添加std::ranges::views::zip,这样您就可以编写如下内容。

#include <algorithm>
#include <ranges>
#include <vector>
#include <iostream>

int main()
{
  std::vector colindex{ 1, 2, 2, 1, 0, 2, 0, 1, 0, 2, 1, 2 };
  std::vector rowindex{ 7, 7, 2, 1, 3, 9, 8, 6, 6, 0, 3, 4 };
  std::vector values{ 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0, 1.1, 1.2 };

  auto el_view{ std::views::zip(colindex, rowindex, values) };
  
  std::ranges::sort( el_view );

  for ( auto [r, c, v] : el_view )
    std::cout << r << ' ' << c << ' ' << v << '\n';
}

现场直播。

相关问题