c - 计算网格上连接组的相邻空点的有效方法

Question

连通组是指网格上水平或垂直相邻的一组相等值的顶点。

例如，在这个网格上，其中 . 是一个空点，有 4 个相连的组。

X O O .      X       O O
. X O X  ->       X    O  X
X X O X         X X    O  X

您还可以看到每个组都有 1 个连接空点。

我正在尝试计算给定网格和指向组顶点的坐标的这些连接空点的数量。

如果输入是，

. . X X X O O . 
X X . X . X O X 
. X X X X X O X 
X X . O O X . X 

(0, 2)

输出应为 7，因为包含位于 (0, 2)(行、列)处的顶点的大组已连接 7空点。

如果您熟悉围棋(围棋)游戏，那么连接的空点换句话说就是自由。该操作是围棋棋局分析例程的核心，必须快速完成。

以下是我的尝试。在涉及大量分支和递归的许多方面，它的效率非常低。我正在跟踪 4 个可能的方向，并在出现空白时增加计数，并在已完成计数的顶点上做一个标记，以免计数两次。

您能否阐明如何有效地解决这个问题？

一般算法改进和特定于 x86-AVX2 的优化都是受欢迎的。

typedef __attribute__((vector_size(32))) char vec8_c;

enum {H = 4, W = 8};

static int count_();
static int count__();

static int count(vec8_c x, int i, int j) {
    vec8_c m = {0};
    return count_((char *)&x, (char *)&m, i, j, i * W + j);
}

static int count_(char *x, char *m, int i, int j, int idx) {
    m[idx] = 1;
    int r = 0;
    if (j - 1 >= 0) {
        r += count__(x, m, i, j - 1, idx - 1, idx);
    }
    if (j + 1 < W) {
        r += count__(x, m, i, j + 1, idx + 1, idx);
    }
    if (i - 1 >= 0) {
        r += count__(x, m, i - 1, j, idx - W, idx);
    }
    if (i + 1 < H) {
        r += count__(x, m, i + 1, j, idx + W, idx);
    }
    return r;
}

static int count__(char *x, char *m, int i, int j, int idx, int idx_) {
    if (!m[idx]) {
        if (!x[idx]) {
            m[idx] = 1;
            return 1;
        } else if (x[idx] == x[idx_]) {
            return count_(x, m, i, j, idx);
        }
    }
    return 0;
}

Run online .

Answer 1

根据描述，我会将问题转换为交集/并集；

• 根据连接的组件制作掩码 C
• 用空像素制作掩模E
• 通过连接 C 的移位版本来制作更大的掩码 M M = C<<1 | C^^1 | C >> 1 | C^^-1
• 返回 PopCount(M & E)

这种方法应该很容易矢量化，甚至自动矢量化。

当 C 足够大时，使用 SIMD 寄存器在 16x8 的 block 中工作，其中每个位代表掩码中的一个 bool 值。然后可以将整个 block 向上/向下移动 alignr/左/右 _mm_slli_epi16/_mm_srli_epi16或 AVX2/-512 中的等效项，不幸的是，跨银行转移的成本有点高。

对于特定输入:

. . X X X O O . -> C = 0 0 1 1 1 0 0 0  E = 1 1 0 0 0 0 0 1
X X . X . X O X        1 1 0 1 0 1 0 0      0 0 1 0 1 0 0 0
. X X X X X O X        0 1 1 1 1 1 0 0      1 0 0 0 0 0 0 0
X X . O O X . X        1 1 0 0 0 1 0 0      0 0 1 0 0 0 1 0

那么掩码 M 将是 C 向左、右、上、下移动的并集

M =   0  0  0  1  1  1  0  0  0  0
      0 |1  1  1  1  1  1  0  0| 0  <-- you only need the
      1 |1  1  1  1  1  1  1  0| 0      inner / 'valid' area
      0 |1  1  1  1  1  1  1  0| 0
      1 |1  1  1  1  1  1  1  0| 0
      0  1  1  0  0  0  1  0  0  0

M.*E =    1   1   0   0   0   0   0   0
          0   0   1   0   1   0   0   0
          1   0   0   0   0   0   0   0
          0   0   1   0   0   0   1   0,  sum == 7