使用stl排序将表排序到位

Question

我有一个巨大的表(约50Gb)(i,j,k)格式(来自稀疏矩阵)存储为

uint32_t * idx1, * idx2;
float * vals;
uint32_t tablesize;

并且我想用给定的比较函数对它进行排序,该函数是idx1和idx2的函数.可以使用std :: sort来完成吗？

具体地,通过将​​i放置在idx2中的idx1,j和v中的相应条目中的v来存储稀疏矩阵中具有值v的每个非零条目(i,j).我想根据(i1,j1,v1)<=(i2,j2,v2)对这些条目进行排序,如果

(i1 < i2) || (i1==i2 && j1 <= j2)

我已经能够在非标准数据类型上使用std :: sort的例子假设被比较的每个项目是一个类的单个实例; 这里每个项目由不同数组中的三个值表示.

Answer 1

如果您必须继续使用现有的数据结构（本质上是std::tuple三个数据std::vector结构），那么使用boost::zip_iterator似乎是正确的选择。Azip_iterator将三个迭代器（两个迭代器用于索引，一个用于值）视为单个元组，并且您可以使用自定义比较函数对象就地对数据进行排序。唉，boost::zip_iterator不能与 一起使用std::sort，如本问答中所述，因为它无法写入。

这意味着您必须编写自己的 zip_iterator 类，该类可以与std::sort. 请注意，这不是一个简单的练习，请参阅此问答和/或本文。

std::vector对 a进行排序要容易得多std::tuple。我下面的尝试使用std::tuple两个索引和一个值，并将这些条目存储到std::vector. 对于排序，我使用 C++14 通用 lambda 将两个索引转发到较小的元组中，并operator<使用std::tuple.

#include <algorithm>
#include <iostream>
#include <tuple>
#include <vector>

using index = uint32_t;
using value = float;
using sparse_entry = std::tuple<index, index, value>;
using sparse_matrix = std::vector<sparse_entry>;

int main()
{
    // sparse 3x3 matrix
    auto m = sparse_matrix { 
        std::make_tuple( 1, 1, -2.2), 
        std::make_tuple( 1, 0, 42  ), 
        std::make_tuple( 0, 2,  3.4), 
        std::make_tuple( 0, 1,  1.7) 
    };    

    // sort by row-index, then column-index
    std::sort(begin(m), end(m), [](auto const& L, auto const& R) {
        return 
            std::forward_as_tuple(std::get<0>(L), std::get<1>(L)) <
            std::forward_as_tuple(std::get<0>(R), std::get<1>(R))
        ;
    });

    for (auto const& elem : m)
        std::cout << "{ " << std::get<0>(elem) << ", " << std::get<1>(elem) << ", " << std::get<2>(elem) << "}, \n";
}

活生生的例子。

如果您的应用程序可以使用这种转换后的数据布局（并且可能存在缓存性能原因而不能使用），那么上面的代码将根据您的需要进行排序。

注意：正如@Casey提到的，您也可以使用std::tie代替std::forward_as_tuple，但是当您更改sparse_entry为成熟的用户定义类并使用按值返回的getter时，这可能会困扰您。