c++ - 通过迭代旋转重新排序算法

Question

考虑一个包含 N 个样本的数据集，其中每个样本都由 head 元素和后跟 tail 元素组成。我想执行稳定的重新排序，这样 N tails 在顶部组合在一起，N heads 在底部组合在一起。

例如数据集:

 -1  -2  -3   1   2   3   4   5
 -4  -5  -6   6   7   8   9  10
 -7  -8  -9  11  12  13  14  15
-10 -11 -12  16  17  18  19  20

有 N = 4 个样本，head = 3(负整数)，tail = 5(正整数)。所需的转换将产生:

  1   2   3   4   5   6   7   8
  9  10  11  12  13  14  15  16
 17  18  19  20  -1  -2  -3  -4
 -5  -6  -7  -8  -9 -10 -11 -12

我实现了一个基于重复应用旋转的解决方案。旋转是由 C++ 算法实现的 std::rotate :

std::rotate(first, n_first, last) swaps the elements in the range [first, last) in such a way that the element n_first becomes the first element of the new range and n_first - 1 becomes the last element.

我的实现(如下所示)提供了正确的解决方案，并且对我的问题表现良好。但是，它需要执行 N 次旋转，其中每次旋转的复杂度从 O(head + tail) 增加到 O(N * tail + head).

您知道复杂度更高的算法吗？。

我的代码如下:

#include <algorithm>
#include <vector>
#include <iostream>
#include <iomanip>

template <typename I> // I models Forward Iterator
I reorder(I f, I l, std::size_t head_size, std::size_t tail_size)
{
  std::size_t k = 1;
  auto m = std::next(f, head_size);
  auto t = std::next(m, tail_size);
  while (t != l) {
    f = std::rotate(f, m, std::next(m, tail_size));
    m = std::next(f, ++k * head_size);
    t = std::next(m, tail_size);
  };
  return std::rotate(f, m, t);
}

template <typename C>
void show(const char* message, const C& c)
{
  std::size_t shown { 0 };
  std::cout << message << "\n";
  for (auto && ci : c)
    std::cout << std::setw(3) << ci
              << (++shown % 8 == 0 ? "\n" : " ");
}

int main()
{
  std::vector<int> v {
    -1,  -2,  -3,  1,  2,  3,  4,  5,
    -4,  -5,  -6,  6,  7,  8,  9, 10,
    -7,  -8,  -9, 11, 12, 13, 14, 15,
   -10, -11, -12, 16, 17, 18, 19, 20 };

  std::size_t head_size { 3 };
  std::size_t tail_size { 5 };

  show("before reorder", v);

  reorder(v.begin(), v.end(), head_size, tail_size);

  show("after reorder", v);

  return 0;
}

编译运行:

$ clang++ example.cpp -std=c++14
before reorder
 -1  -2  -3   1   2   3   4   5
 -4  -5  -6   6   7   8   9  10
 -7  -8  -9  11  12  13  14  15
-10 -11 -12  16  17  18  19  20
after reorder
  1   2   3   4   5   6   7   8
  9  10  11  12  13  14  15  16
 17  18  19  20  -1  -2  -3  -4
 -5  -6  -7  -8  -9 -10 -11 -12

问题域的详细信息

我正在读取图像，其中每一行 前面都有像素元数据，后面是原始像素，如下所示:

[metadata] [pixels...]
[metadata] [pixels...]
[ many more of these]
[metadata] [pixels...]

我需要将所有像素打包在一起并将它们传递给 OpenGL，但我还需要维护程序可访问的元数据。所以，我这样做:

 [all the pixels] [all the metadata]

并将 [all the pixels] 传递到我的显卡，同时在 CPU 中保留对 [all the metadata] 的句柄。

编辑

感谢您的回复 - 我最终实现了一个不依赖于重新排序的替代解决方案。然而，重点仍然是:你能改进“就地”数据集重新排序的算法吗？它类似于就地矩阵转置。

Answer 1

一个非常快速的解决方案是创建另一个矩阵并将元素直接放置在它们所属的位置。

例如，假设您有 n 行，t 尾和 h 头。第一行 (1, 1) 的第一个尾部将变为 ( (h * n+1)/(h+t), (h * n+1)%(h+t))。我会让你制定一般情况 (i,j) 到 (k,l)。无论如何，这是一个涉及整数除法和模数的计算。