我在程序中使用了COO格式的稀疏矩阵。COO格式使用3个单独的向量来表示矩阵:rowindex、colindex和values。我需要先用rowinindex然后用colindex来排序矩阵。例如，如果vector包含:
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()函数)。
我找到的一些关于对多个向量排序的答案，只对其中一个向量的值进行排序。它们不要求根据第二个向量对第一个向量中具有相同值的元素进行排序。
通常可以对COO中给出的稀疏矩阵进行排序。但不受你的约束。
-
使用c++中可用的排序函数:基本上不可能，因为
std::libraries中现有的排序函数只能在一个范围内工作。即使将其他vectors放在谓词闭包中，并提出一些复杂的lambda函数，或者将所有内容都放在Functor中，也没有意义。 -
需要额外的空间，使解决方案可行且易于解决。
-
与约束相同
因此，您需要做出妥协。或者使用非标准c++库。
在仔细考虑了这个问题之后，我决定走一条不同的路。现在，我不再从相应的文件中读取整个稀疏矩阵，然后对其进行排序，而是在读取时对其进行排序。从文件中读取的每个元素都直接插入到正确的位置。对于感兴趣的人，下面是执行排序的程序部分。
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);
}
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';
}
生活。