C++ `std::sort` 在不复制的情况下指向 2D 数据的指针

Question

我在二维数据的 C 样式数组中有大量数据（GiB 到 TiB）。它不是数组的数组，而是指向被解释为二维数据的数据的指针。它非常大，所以我不想将它复制到 std::vectors 或类似的地方。我无法控制数据的来源，它来自外部库。

我需要std::sort基于列中数据的数据行（不完全是词法排序，但概念相似）。

我已经弄清楚如何使用编译时已知的列数来完成此操作。例如：

#define COLUMNS 4
struct Row {
    double values[COLUMNS];
};

double* data = ...;
size_t n_rows = ...;
size_t n_cols = COLUMNS;

std::sort((Row*)data, ((Row*)data)+n_rows, comp);

我知道我可以为 COLUMNS 构建结构模板，而不是使用宏，而不是使用 comp 可以定义 operator< 而不是 Row 结构，但是这不会改变列数*的编译时性质。

我能想到的唯一解决方案是使用知道每一行步幅的自定义随机访问迭代器。但在我制作自己的迭代器之前（这对我来说总是有点令人生畏）我想确保没有其他方法。

*做出这些设计选择是因为我实际上是用 Cython 而不是 C++ 编写的，但这无关紧要，我不知道如何在没有自定义迭代器的情况下使用 C++ 执行此操作。我愿意用 C++ 编写解决方案，但更喜欢可以用 Cython 编写的选项（我可以转换）。

Answer 1

这可能会成功。将 Row 定义为指向行首的指针，如下所示：

struct Row {
   double* start;
   static int columns;

   Row(const Row& row) = default;

   // Overload operator= to copy your data.
   Row& operator=(const Row& rhs) {
      memcpy(start, rhs.start, columns*sizeof(double));
   }

   Row operator<(const Row& rhs) const {
      // your comparison function
   }
};

这样使用：

double* data = ...;
size_t n_rows = ...;
size_t n_cols = COLUMNS;
Row::columns = n_cols;

std::vector<Row> rows(n_rows);
for(int i=0;i<n_rows;++i) {
   rows[i].start = data + i*n_cols;
}
std::sort(rows.begin(), rows.end());

您需要创建一个 std::vector<Row>。希望你没有那么多行，所以这是一个性能问题。

Answer 2

下面的示例代码显示了在 O(n) 时间内到位的重新排序。您需要更改 pa[i]-a 将指针转换为索引以处理 a[].

的实际结构

#include <algorithm>
#include <iostream>

bool compare(const double *p0, const double *p1)
{
    return *p0 < *p1;
}

int main()
{
double a[8] = {8.0,6.0,1.0,7.0,5.0,3.0,4.0,2.0};
double *pa[8];
size_t i, j, k;
double ta;
    // create array of pointers to a[]
    for(i = 0; i < sizeof(a)/sizeof(a[0]); i++)
        pa[i] = &a[i];
    // sort array of pointers to a[]
    std::sort(pa, pa+sizeof(a)/sizeof(a[0]), compare);
    // reorder a[] and pa[] according to pa[] in O(n) time
    for(i = 0; i < sizeof(a)/sizeof(a[0]); i++){
        if(i != pa[i]-a){
            ta = a[i];
            k = i;
            while(i != (j = pa[k]-a)){
                a[k] = a[j];
                pa[k] = &a[k];
                k = j;
            }
            a[k] = ta;
            pa[k] = &a[k];
        }
    }
    for(i = 0; i < sizeof(a)/sizeof(a[0]); i++)
        std::cout << a[i] << ' ';
    std::cout << std::endl;
    return 0;
}

就地重新排序通过撤消根据 a[] 排序的 pa[] 中的 "cycles" 来实现。对于此示例代码，索引列表 0 到 7 后跟 pa[i]-a 列表（i = 0 到 7）导致：

0 1 2 3 4 5 6 7    (i)
2 7 5 6 4 1 3 0    (pa[i] - a)

这显示 pa[] 中的 "cycles" 根据 a[] 排序。从第（i）行的0开始，它下面的索引是2。看第i行的2，它下面的数字是5。5下面是1。1下面是7。7下面是a 0，完成那个循环。使用->记下下一个索引，本例中有3个循环：

{0->2->5->1->7->0} {3->6->3} {4->4}

重新排序的作用是撤销 a[] 和 pa[] 的循环。它在 pa[0] (i != pa[i]-a) 找到第一个循环。查看 a[]，您有 ta=a[0]、a[0]=a[2]、a[2] = a[5]、a[5]=a[1]、a[1]= a[7]，此时 i == 0 == pa[7]-a，循环的最后一部分，它设置 a[7] = ta。 pa[] 以相同的方式更新。下一个循环是ta=a[3]，a[3]=a[6]，a[6] = ta。最后一个循环，4->4 指向它自己，所以被跳过 (i == pa[i]-a)。这个的时间复杂度是 O(n).

YouTube 上有一个关于排列和循环表示法的视频（在本例中为 (0,2,5,1,7)(3,6)（(4) 被忽略，因为它就位）。您可以在网络上搜索 "permutation cycle" 以获取其他文章。

https://www.youtube.com/watch?v=MpKG6FmcIHk

C++ `std::sort` 在不复制的情况下指向 2D 数据的指针

C++ `std::sort` over pointer to 2D data without copying

c++

arrays

sorting

c++-standard-library