降低计算邻居的复杂性（康威的生命游戏）

Question

我必须实施康威的生命游戏。一切正常，并且给定的测试正在通过。我唯一的问题是这种方法给出了复杂性错误，而运行 PMD 规则在我的文件上。我知道很多 if 语句是造成这种情况的原因，但在尝试将它们压缩成更小的组时，我不小心破坏了我的代码。

内容如下：

The method 'getNeighbourCount(int, int)' has a cyclomatic complexity of 21.

The method 'getNeighbourCount(int, int)' has an NPath complexity of 20736, current threshold is 200

优化此方法的最佳选择是什么？

public Integer getNeighbourCount(int x, int y) {
        // x = column (20), y = row (15)

        int countNeigbours = 0;
        if (x != 0 && y != 0 && isAlive(x - 1,y - 1)) {
            countNeigbours++;
        }

        if (x != 0 && isAlive(x - 1, y)) {
            countNeigbours++;
        }

        if (x != 0 && y != rows - 1 && isAlive(x - 1,y + 1)) {
            countNeigbours++;
        }
        if (y != 0 && isAlive(x,y - 1)) {
            countNeigbours++;
        }
        // check self
        if (y != rows - 1 && isAlive(x,y + 1)) {
            countNeigbours++;
        }

        if (x != columns - 1 && y != 0 && isAlive(x + 1,y - 1)) {
            countNeigbours++;
        }

        if (x != columns - 1 && isAlive(x + 1, y)) {
            countNeigbours++;
        }

        if (x != columns - 1 && y != rows - 1 && isAlive(x + 1,y + 1)) {
            countNeigbours++;
        }

        return countNeigbours;
}

isAlive returns 单元格是否被占用 (true) 或未被占用 (false) 的布尔值。

Answer 1

从您的当前位置循环“delta x”和“delta y”：

for (int dx : new int[]{-1, 0, 1}) {
  if (x + dx < 0 || x + dx >= columns) continue;

  for (int dy : new int[]{-1, 0, 1}) {
    if (y + dy < 0 || y + dy >= rows) continue;
    if (dx == 0 && dy == 0) continue;

    if (isAlive(x + dx, y + dy)) countNeighbours++;
  }
}

（当然，您不必使用数组和增强的 for 循环：您可以只使用 for (int dx = -1; dx <= 1; ++dx)，或者您喜欢的其他方式）

Answer 2

我不知道这是否会提供加速，但您可以尝试使用第二个数组来保存总和，并在设置或清除单个单元格时增加或减少这些值。这取代了许多 'isAlive' 检查以判断是否应打开或关闭单元格，并将单元格邻接计算减少到仅那些被切换的单元格，这应该比重复计算要少得多整个阵列。也就是说，对于大部分为空的网格，只有一小部分单元需要重新计算，比整个网格少很多。

此外，您可以尝试使用整行 isActive、minActive 和 maxActive 值。这将进一步减少循环次数，但会增加每次迭代的复杂性和成本。活动单元格的稀疏性将决定额外成本是否通过迭代次数的减少来平衡。

降低计算邻居的复杂性（康威的生命游戏）

Reduce complexity of counting neighbours (Conway's Game of Life)

java

optimization

cyclomatic-complexity