c++ - 平等测试功能

Question

下面是一个函数，旨在对一维 vector 中的相邻数字执行相等性测试。

此一维 vector 将具有表示 nxn 网格的值。 [ v 是 vector ]

当它们相等时返回 false。

例如考虑这个 3x3 网格:

i\j| 0 | 1 | 2
0  | 1 | 2 | 3
1  | 4 | 5 | 6
2  | 7 | 8 | 9

我编写的代码的问题是，并非网格中的所有数字都会有 4 个其他相邻数字并测试不存在的索引，例如当尝试比较网格中左上角数字上方的数字时(示例中的 1)可能会导致一些不准确的结果。

除此之外，我写的似乎不是最有效的方法。肯定有比列出 5 个新变量更简单的方法吗？

for( int i= 0; i < n ; i++ ){
    for( int j = 0; j < n; j++){
        int x = v[convert(i, j, n)];
        int c = v[convert(i-1, j, n)];
        int s = v[convert(i+1, j, n)];
        int b = v[convert(i, j+1, n)];
        int n = v[convert(i, j-1, n)];

        if (x == c || x == s || x == b || x == n ) {
            return false;
        }
    }
}

//another function used to convert 2d into 1D index
 int convert(int row, int col, int rowlen){
    return row*rowlen+col;
}

如有任何帮助，我将不胜感激。

Answer 1

如果您想要一种有效的方法来执行此操作，您应该考虑值的缓存位置、执行多少索引转换、执行多少边界测试以及需要多少比较。

首先要注意的是，当您已经与右侧和下方进行比较时，无需再与左侧和上方进行比较。这是因为左/上测试将在下一次迭代的右/下测试时发生。因此，立即将测试量减半。

第一个优化是将操作拆分为行测试和列测试:

// Test adjacency in rows
for (const int *rowptr = v, *end = v + n * n;
     rowptr != end;
     rowptr += n)
{
    for (int col = 1; col < n; col++) {
        if (rowptr[col-1] == rowptr[col]) return false;
    }
}

// Test adjacency in columns
for (const int *row0ptr = v, *row1ptr = v + n, *end = v + n * n;
     row1ptr != end;
     row0ptr = row1ptr, row1ptr += n)
{
    for (int col = 0; col < n; col++) {
        if (row0ptr[col] == row1ptr[col]) return false;
    }
}

为了避免两次遍历整个数组，您需要将它们组合起来，但它开始变得有点困惑。请注意这两个单独的 channel 当前如何具有不同的边界(行测试从第 1 列循环到第 n 列，而列测试从第 0 行循环到 n-1)。

只有当 n 非常大并且这段代码的速度绝对至关重要时，组合循环才有意义。这个想法是对整个数组执行单次传递，避免在第二次传递时出现 L1 缓存未命中等问题。

它看起来像这样:

const int *row0ptr = v, *row1ptr = v + n, *end = v + n * n
for ( ; row1ptr != end; row0ptr = row1ptr, row1ptr += n)
{
    // Test first column
    if (row0ptr[0] == row1ptr[0]) return false;

    // Test row0 and remaining columns
    for (int col = 1; col < n; col++) {
        if (row0ptr[col-1] == row0ptr[col]) return false;
        if (row0ptr[col] == row1ptr[col]) return false;
    }
}

// Test last row
for (int col = 1; col < n; col++) {
    if (row0ptr[col-1] == row0ptr[col]) return false;
}