使用stl排序在适当位置排序表 [英] sorting table in place using stl sort

问题描述

我有一个以（i，j，k）格式（来自稀疏矩阵）的巨大表格（大约50Gb）存储为<​​/ p>

I have a HUGE table (about 50Gb) in (i,j,k) format (from a sparse matrix) stored as

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

，我想用一个给定的比较函数idx2。这可以使用std :: sort吗？

and I'd like to sort it in place with a given comparison function that's a function of idx1 and idx2. Can this be done using std::sort?

具体来说，通过将i放在idx1，j在idx2中，并将v放在对应的条目中来存储稀疏矩阵中具有值v的每个非零项（i，j）在vals。然后，如果

Specifically, each nonzero entry (i,j) with value v in the sparse matrix is stored by placing i in idx1, j in idx2, and v in the corresponding entry in vals. I'd like to then sort these entries according to (i1, j1, v1) <= (i2, j2, v2) if

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

能够在非标准数据类型上使用std :: sort假设每个被比较的项目是一个类的单个实例;

The examples I've been able to scrounge up of using std::sort on nonstandard datatypes assume that each item being compared is a single instance of a class; here each item is represented by three values in different arrays.

推荐答案

如果您必须继续使用现有的数据结构基本上是三个 std :: vector 的 std :: tuple ，使用 boost :: zip_iterator 会 成为你的方式。 zip_iterator 将三个迭代器（两个对应索引，一个对应一个值）视为单个元组，您可以使用自定义比较函数对象对数据进行就地排序。唉， boost :: zip_iterator 不能与 std :: sort 一起使用，如this Q& A ，因为它无法写入。

If you have to keep using your existing data structure, which is essentially a std::tuple of three std::vectors, using boost::zip_iterator would seem to be the way to go. A zip_iterator treats three iterators (two to indices and one to a value) as a single tuple, and you can use a custom comparison function object to sort your data in-place. Alas, boost::zip_iterator can't be used with std::sort, as explained in this Q&A, because it can't be written into.

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

This means that you would have to write your own zip_iterator class that can be used with std::sort. Note that it is not a trivial exercise, see this Q&A and/or this paper.

std :: vector std :: tuple 。下面的尝试使用两个索引的 std :: tuple 和一个值，并将这些条目存储到 std :: vector 。对于排序，我使用一个C ++ 14通用lambda，将两个索引转发到一个更小的元组，并使用库 operator<比较字符串（即首先在行索引，然后在列索引） ; of std :: tuple 。

It is a lot easier to sort a std::vector of a std::tuple. My attempt below uses a std::tuple of two indices and a value, and stores those entries into a std::vector. For the sorting, I use a C++14 generic lambda that forwards the two indices into a smaller tuple and compares those lexicographically (i.e. first on row-index, then on column-index) using the library operator< of 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";
}

活动示例 。

如果您的应用程序可以使用此转换后的数据布局

If your application can use this transformed data layout (and there maybe cache-performance reasons why it can't), then the above code will do the sorting as you want it.

注意。 ：as @Casey提到，你也可以使用 std :: tie 而不是 std :: forward_as_tuple ，但是当你将 sparse_entry 更改为一个完整的用户定义类，并且getter返回值的时候，你会咬你。

NOTE: as @Casey mentions, you can also use std::tie instead of std::forward_as_tuple, but that can bite you when you change sparse_entry into a full-fledged user-defined class with getters returning by-value.

这篇关于使用stl排序在适当位置排序表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！