首页 文章

当表示为对象的一维向量时，有效地旋转NxM矩阵（C）

提问于
浏览 次
2

到目前为止，我已经想出顺时针旋转NxM（N不一定等于M）矩阵的唯一方法（当它表示为一维向量，高度和宽度变量分别存储）如下：

struct matrix
{
  vector<int> data;
  int height;
  int width;

  void rotate_90()
  {
    vector<int> newdata(height*width);
    for(int index = 0; index < height*width; index++)
    {
      int x = index % width;
      int y = index/width; // integer division
      int nextindex = (x+1)*height - 1 - y;
      newdata[nextindex] = data[index];
    }
    data = newdata;
    int temp = height;
    height = width;
    width = temp;
  }
};

虽然这种方法确实有效，但我确信有一种更有效的方法（特别是在节省时间方面;空间不是问题） . 必须创建一个全新的向量然后用新的向量覆盖旧向量并不适合我 . 有更有效的解决方案吗？

请记住，我上面提供的仅仅是为了说明 . 我实际代码中的 data 向量使用对象而不是整数;使用int只是为了让它更容易测试 . 因此，像Eigen这样的线性代数库在这里无济于事 .

c++ algorithm matrix linear-algebra

1 回答

  • 6

    如果可能的话，我会尽量避免完全复制数据，只在访问元素时转换索引：

    struct matrix {
  vector<int> data;
  int height;
  int width;

  int& at(int x,int y) { return data(x + y*width); }

  struct rotated_view {
    matrix& base;
    rotated_matrix_view(matrix& base) : base(base) {}
    int& at(int x,int y) { return base.at(y,base.height-x-1); }
  }

  rotated_view rotated() { return rotated_view(*this); }
};

    请注意，根据您的访问模式，这可能会导致性能相当差 . 另一方面，逐列访问原始矩阵中的元素几乎与通过 rotated_matrix_view 逐行访问它们一样低效 . 如果你关心性能（当然你会这么做，否则你为什么会使用C;）我建议你尝试两者，索引转换和实际轮换，看看哪个更好 .

    回复于

相关问题