2

我有一项任务是优化一段 C 代码（一种我很喜欢的语言），旨在模拟图像中的旋转像素：

void naive_rotate(int dim, pixel *src, pixel *dst) {
    int i, j;
    for (i = 0; i < dim; i++)
        for (j = 0; j < dim; j++)
            dst[RIDX(dim-1-j, i, dim)] = src[RIDX(i, j, dim)];
}

和pixel的RIDX定义如下：

typedef struct {
    unsigned short red;
    unsigned short green;
    unsigned short blue;
} pixel;

#define RIDX(i,j,n) ((i)*(n)+(j))

作业说明包含注释，“你的任务是重写此代码，使其使用代码移动、循环展开和阻塞等技术尽可能快地运行。”

我想我对如何解决这个问题有一些想法。但是，我尝试循环展开：

void rotate_unroll(int dim, pixel *src, pixel *dst) {
    int i, j;
    for (i = 0; i < dim; i++) {
        for (j = 0; j < dim; j+=4) {
            dst[RIDX(dim-1-j, i, dim)] = src[RIDX(i, j, dim)];
            dst[RIDX(dim-1-(j+1), i, dim)] = src[RIDX(i, j+1, dim)];
            dst[RIDX(dim-1-(j+2), i, dim)] = src[RIDX(i, j+2, dim)];
            dst[RIDX(dim-1-(j+3), i, dim)] = src[RIDX(i, j+3, dim)];
        }
    }
}

和代码运动（或至少重新组织 RIDX 并将一些计算移出内部循环）：

void rotate_motion(int dim, pixel *src, pixel *dst) {
    int i, j;
    int dimsquared = dim * dim;
    for (i = 0; i < dim; i++) {
        int dst_temp = dimsquared - dim + i;
        int src_temp = i * dim;
        for (j = 0; j < dim; j++) {
            dst[dst_temp - (dim * j)] = src[src_temp + j];
        }
    }
}
//   dst[RIDX(dim-1-j, i, dim)] 
// = dst[(dim-1-j)dim + i] 
// = dst[(dim * dim) - dim - (dim)j + i]
//   src[RIDX(i, j, dim)]
// = src[(dim)i + j]

似乎没有工作；与作业打包在一起的计时器声称我的解决方案对程序的 CPE 没有任何影响。我怀疑我可能错误地使用了这两种方法，并且非常感谢任何正确方向的指导。（这是一个家庭作业，所以我不是要求一个完整的解决方案，只是一些指示。）

我的另一个想法是尝试添加一个累加器——类似于以下内容：

void rotate_acc(int dim, pixel *src, pixel *dst) {
    int i, j;
    pixel temp = dst;
    for (i = 0; i < dim; i++) {
        for (j = 0; j < dim; j++) {
            temp[RIDX(dim-1-j, i, dim)] = src[RIDX(i, j, dim)];
        }
    }
    dst = temp;
}

但是我的语法在那里非常错误，我不确定如何构建相关结构的临时版本。

任何帮助深表感谢。谢谢！

4

2 回答 2

1

您需要对 C 中的指针有透彻的了解。简单地说：指针表示数据在内存中存储的地址（在您的情况下为像素结构）。

在您的代码中，该函数rotate_acc将像素指针作为参数：pixel *dst. 一开始你可能会说pixel *tmp = dst，但请记住，这就是所谓的浅拷贝——只复制地址，而不是它指向的数据——因此，如果你通过说修改 tmp tmp->red = 0，它将修改原始数据也

如果你需要一个深拷贝，你需要说pixel tmp = *dst

于 2013-02-01T04:18:30.030 回答
0

尝试这个：

void naive_rotate(int dim, pixel *src, pixel *dst) {
    int dimSq = dim * dim;
    int dstdIxStart = dimSq - dim;
    int endIdx = dimSq - 2 * dim - 2;
    int dstIdx = dimSq - dim;
    for (int i = 0; int < endIdx; ++i)
    {
       dst[dstIdx--] = src[i];
       if (0 == dstIdx)
       {
          dstdIxStart -= dim;
          dstIdx = dstdIxStart;
       }
    }
}

您将不得不仔细检查数学，但我希望您明白这一点。

它删除了所有的乘法。此外，src按顺序访问它对缓存也有好处。

于 2013-02-01T04:42:36.673 回答