在康威的《人生游戏》中更优雅地检查邻居

我在即将实施的《人生游戏》实施过程中计算邻居的方法非常重复，我想知道这样做是否可以更优雅地进行：

static int countNeighbours(Board b, int x, int y) {
    int count = 0;
    if (b.getTile(x - 1, y - 1)) {
        ++count;
    }
    if (b.getTile(x, y - 1)) {
        ++count;
    }
    if (b.getTile(x + 1, y - 1)) {
        ++count;
    }
    if (b.getTile(x + 1, y)) {
        ++count;
    }
    if (b.getTile(x + 1, y + 1)) {
        ++count;
    }
    if (b.getTile(x, y + 1)) {
        ++count;
    }
    if (b.getTile(x - 1, y + 1)) {
        ++count;
    }
    if (b.getTile(x - 1, y)) {
        ++count;
    }
    return count;
}

由于正式板应该是无限的，我不需要在此代码中进行越界检查-我假设板在这里是无限的-但我的板实现秘密地看起来像这样：

// TODO: make the board 'infinite'
public boolean getTile(int x, int y) {
    if (x < 0 || y < 0 || x > getWidth() - 1 || y > getHeight() -1) return false;
    return tiles[y][x];
}

public void setTile(int x, int y, boolean val) {
    if (x < 0 || y < 0 || x > getWidth() - 1 || y > getHeight() -1) return;
    tiles[y][x] = val;
}

（为节省您的时间，键入“您的代码将对（0,0）上的图块造成IndexOutOfBoundsException。”。此问题与static int countNeighbours(Board, int, int)的实现有关。）
< br顺便说一下，我对Java 6感到困惑。

该方法应该是board类的方法，而不是接受board的静态方法。

当然！我认为这很丑陋，但不知道如何改进。谢谢！ @IngoBürk

相关，但更多地关注性能而不是优雅：codereview.stackexchange.com/questions/42718/…

#1 楼

没错，还有另一种方法可以执行此操作，但是，首先，一些Java标准：<1衬里应该有括号。这是许多语言通用的代码风格，因为它更易于维护，并且减少了以后的错误。像这样的行：

if (x < 0 || y < 0 || x > getWidth() - 1 || y > getHeight() -1) return;

应为：

if (x < 0 || y < 0 || x > getWidth() - 1 || y > getHeight() -1) {
    return;
}

/>可以使用更简单的运算符时不要使用算术。返回到：

if (x < 0 || y < 0 || x > getWidth() - 1 || y > getHeight() -1) { ... }

可以简化为：

if (x < 0 || y < 0 || x >= getWidth() || y >= getHeight()) { ...}

在有意义的情况下使用普通布尔值（再次返回到...）：

if (x < 0 || y < 0 || x >= getWidth() || y >= getHeight()) { ...}

放入类似的函数（转换为使用&&代替）：

public boolean getTile(int x, int y) {
    return x >= 0 && y >= 0 && x < getWidth() && y < getHeight() && tile[y][x];
}

请注意，标准布尔短路评估如何确保x和y在输入之前有效。使用tile[y][x]。

好，关于该代码重复。解决这类问题的技巧是使用偏移量数组。考虑您的网格，它有8个邻居（相对y,x格式）：

-1,-1     -1,0    -1,+1

 0,-1     *us*     0,+1

+1,-1     +1,0    +1,+1

我们可以将这些邻居偏移量放入数组中：

private static final int[][] NEIGHBOURS = {
    {-1, -1}, {-1, 0}, {-1, +1},
    { 0, -1},          { 0, +1},
    {+1, -1}, {+1, 0}, {+1, +1}};

然后，您的检查方法变为：

static int countNeighbours(Board b, int x, int y) {
    int cnt = 0;
    for (int[] offset : NEIGHBOURS) {
        if (b.getTile(x + offset[1], y + offset[0]) {
           cnt++;
        }
    }
    return cnt;
 }

\ $ \ begingroup \ $
为了提高可读性，我建议将b.getTile重命名为b.hasNeighbourAt（或类似名称）。名称getTile使该方法似乎返回一个称为Tile的东西。
\ $ \ endgroup \ $
–user25884
2014年9月7日在1:20

\ $ \ begingroup \ $
@Tony-getTile根据是否存在生命而不是在某个地方是否有邻居返回一个值。像isLifeAt（x，y）这样的名称可能会更好，但肯定没有hasNeighbourAt。
\ $ \ endgroup \ $
–rolfl
2014年9月8日在11:17

\ $ \ begingroup \ $
对，我当时想传递邻居的偏移量，而不是他们的坐标。（对我来说，在“邻居”中没有-u-！我是美国人。）这是一个简单的问题，因此您可能不想对其进行过度设计。尽管如此，最好还是从瓷砖的角度来思考。
\ $ \ endgroup \ $
–user25884
2014年9月8日15:23

\ $ \ begingroup \ $
原来我从未接受过这个答案。无论如何，谢谢，这非常有帮助。
\ $ \ endgroup \ $
– 11684
18年1月28日在23:03

#2 楼

首先，如果getTile方法的目的是检查某个位置是否有效，则将其称为isAlive。这样可以使代码更容易理解。

将有助于将可能的方向封装在enum中：

enum Direction {
    NORTHWEST(-1, -1),
    NORTH(0, -1),
    NORTHEAST(1, -1),
    EAST(1, 0),
    SOUTHEAST(1, 1),
    SOUTH(0, 1),
    SOUTHWEST(-1, 1),
    WEST(-1, 0),
    ;

    final int dx;
    final int dy;

    Direction(int dx, int dy) {
        this.dx = dx;
        this.dy = dy;
    }
}

可以通过更直观的方式简化enum的帮助：

static int countNeighbours(Board b, int x, int y) {
    int count = 0;
    for (Direction direction : Direction.values()) {
        if (b.isAlive(x + direction.dx, y + direction.dy)) {
            ++count;
        }
    }
    return count;
}

这可能会更好：countNeighbours知道关于countNeighbours类的太多内部细节（它具有Direction和dx字段）。我们可以通过提取职位的详细信息来获得更通用的解决方案，例如：

class Position {
    final int x;
    final int y;

    Position(int x, int y) {
        this.x = x;
        this.y = y;
    }

    Position getNeighbourAt(Direction direction) {
        return new Position(x + direction.dx, y + direction.dy);
    }
}

现在dy可以成为：

static int countNeighbours(Board b, Position position) {
    int count = 0;
    for (Direction direction : Direction.values()) {
        if (b.isAlive(position.getNeighbourAt(direction))) {
            ++count;
        }
    }
    return count;
}

这样做的好处是，countNeighbours的逻辑现在已经如此概括和抽象，以至于板的形状不再重要：它可以实现为地球仪或3D网格，仍然可以。 countNeighbours和Direction的内部实现完全隐藏在Position中，无需了解。这使您可以自由地以不同的方式实现这些功能，而无需再次更改countNeighbours。

\ $ \ begingroup \ $
我喜欢您的枚举，但是我感觉Position类会导致很多性能开销，因为原始代码仅将基元用于该位置。
\ $ \ endgroup \ $
–西蒙·福斯伯格
2014年9月7日于12:11

\ $ \ begingroup \ $
OP的标题确实要求“更优雅”的解决方案。我认为性能开销不是很重要。我在具有性能限制的编程竞赛中使用了这种模式，但似乎没有引起问题。为了使总体设计具有如此的清晰度和灵活性，我认为这样做是值得的。如果确实损害了性能，那么只有我们才能开始进行优化，以破坏良好的封装为代价。
\ $ \ endgroup \ $
– janos
2014年9月7日，12：26

#3 楼

您的代码

如果有很多if检查，最好以某种方式对它们进行排序。例如，首先所有x - 1 if，然后是所有x if，然后是x + 1 ifs：

static int countNeighbours(Board b, int x, int y) {
    int count = 0;
    if (b.getTile(x - 1, y - 1)) {
        ++count;
    }
    if (b.getTile(x - 1, y)) {
        ++count;
    }
    if (b.getTile(x - 1, y + 1)) {
        ++count;
    }
    if (b.getTile(x, y - 1)) {
        ++count;
    }
    if (b.getTile(x, y + 1)) {
        ++count;
    }
    if (b.getTile(x + 1, y - 1)) {
        ++count;
    }
    if (b.getTile(x + 1, y)) {
        ++count;
    }
    if (b.getTile(x + 1, y + 1)) {
        ++count;
    }
    return count;
}

这样，可以更轻松地查看要检查的内容，并且

更干净的代码

您总是可以使用两个for循环来代替：

int count = -1; // not counting ourselfs.
for (int xx = x - 1; xx <= x + 1; xx++) {
    for (int yy = y - 1; yy <= y + 1; yy++) {
        if (b.getTile(xx, yy))) {
            count++;
        }
    }
}
return count;

从-1开始的另一种选择是检查这是否是当前平方：

if ((xx != x || yy != y) && b.getTile(xx, yy))) {
    count++;
}

您还可以采用完全不同的方法：

如果x和y在边界处，则返回3
初始邻居计数：8
检查x是否在边界处，如果是，则减去3
检查如果y在边界处，则减3
返回初始邻居计数

这肯定会更好。

尽管我不确定为什么你甚至需要这种方法来玩游戏吗？

如果您的棋盘是无限的，则该方法始终总是返回8。

\ $ \ begingroup \ $
不，算住邻居。抱歉，我应该这么说。 getTile（int，int）返回一个布尔值，指示该单元是否还活着。
\ $ \ endgroup \ $
– 11684
2014年9月6日在22:23

\ $ \ begingroup \ $
好吧，对活细胞进行计数更有意义^^我忽略了您的tile字段仅存储一个处于活动状态的布尔值。在那种情况下，我将其命名为countLivingNeighbours方法，这使该方法的实际作用更加清晰。
\ $ \ endgroup \ $
–蒂姆
2014年9月6日在22:34

\ $ \ begingroup \ $
int count = -1;使用双for循环方法听起来是个坏主意。如果当前图块为假，则应从零开始。
\ $ \ endgroup \ $
–西蒙·福斯伯格
2014年9月7日在12:09

#4 楼

使您的电路板稍大一些，以便获得一个未使用的边框。切勿检查边界上的牢房。这样您就可以省略测试，因为您永远不会越界。这样可以使代码更短，更快。

考虑将数据放置在1D数组中。它所需要的只是一个简单的坐标转换，例如

boolean isAlive(int x, int y) {
    return data[HEIGHT * x + y];
}

在现代CPU上，速度是有好处的，因为乘法比内存间接访问要快。它还使其他操作更简单，例如清除或复制数据。

\ $ \ begingroup \ $
这是Donald Knuth在提及过早优化时所谈论的内容。
\ $ \ endgroup \ $
– IngoBürk
2014年9月7日上午8:30

\ $ \ begingroup \ $
@IngoBürk如果不简化代码，这将是过早的优化。但是确实如此！
\ $ \ endgroup \ $
– maaartinus
2014年9月7日上午10:03

\ $ \ begingroup \ $
@IngoBürk我写了关于短路的文章，也写了“这也使其他操作更简单”。对于部分未使用的单元格，我部分同意您的观点，但是所有这些都可以封装成几行。这是一个古老的技巧，几乎在所有地方都使用，值得学习。
\ $ \ endgroup \ $
– maaartinus
2014年9月7日于10:31

\ $ \ begingroup \ $
我可以使用数组作为实现。随风飘浮的东西。我只是认为性能不是一个很好的论据，因为它是对尚未进行过研究以查看性能是否还存在问题的事物的微观优化。
\ $ \ endgroup \ $
– IngoBürk
2014年9月7日于11:08

\ $ \ begingroup \ $
@IngoBürk确实不是。这种方式更容易使用。实际上，任何来自C背景的人都可能习惯于此操作，因此完全不需要此答案中显示的翻译帮助器方法。
\ $ \ endgroup \ $
– krowe
2014年9月8日下午0:29

#5 楼

创建一个Point类，而不是到处都有对int x, int y。它更干净，更OO。

您必须处理边界条件。基本上有两种方法：将板子扩大到比其应有的大，以便您有一个看不见的“缓冲区”边框，其中的元素始终处于非活动状态。然后，您可以简化getTile，因为它在获取超出范围的元素（即“缓冲区”边界中的元素）时会分解。您必须修改主循环，这样它才永远不会尝试在“缓冲区”边界中设置值。
当前使用的方法必须确保不尝试获取邻居，即超出范围（getTile）。

已经有两个发布的答案正确地建议您可以使用enum而不是一系列if来使代码更简洁。我想提出一个不同的解决方案。不一定更好，但是您应该探索所有可能的解决方案。

您可以预先计算边缘点的邻居，但可以计算内部点的邻居。您不希望将所有内部点的预先计算的邻居存储在一块巨大的板上，因为这会占用过多的内存。

public Collection<Point> getNeighbors(Point point) {
    Collection<Point> neighbors = edgePointsNeighbors.get(point);
    if (neighbors != null) { // point is on the edge
       return neighbors;
    } else { // point is an inner point
       return point.compute8Neighbors();
    }
}

其中edgePointsNeighbors是预先计算的Map<Point, Collection<Point>>。 Point类应该是不可变的，如果将其用作映射键，则正确实现了hashCode和equals。

最后，我只想对可以实现周期性边界条件的效果做出或多或少的评论。有人可能会争辩说，周期性边界条件比硬边界更接近无限板。在上面的方法中，您只需要更改edgePointsNeighbors的预计算邻居即可。边缘上的所有点现在也将有8个邻居，但这些邻居将交叉。例如，Point(0, 0)的邻居将包括Point(0, 1)，Point(n - 1, n - 1)，Point(0, n - 1)等。

#6 楼

rolfl的答案很好，我只想补充一点，这里的内容是枚举的一个很好的用例。如果您定义一个枚举，如：

public enum Direction {
   N(-1,0),
   E(1,0),
   S(1,0),
   W(-1,0),
   NE(-1,1),
   SE(1,1),
   SW(1,-1),
   NW(-1,-1);

   public final int dx;
   public final int dy;

   Direction(int dx, int dy) {
       this.dx = dx;
       this.dy = dy;
   }
}

，则可以执行以下操作：

for (Direction dir : Direction.values()) {
    if (b.getTile(x + dir.dx, y + dir.dy) {
           cnt++;
    }
}

如果检查邻居就是您所需要的，这将不是一个巨大的改进。但是，它有可能使许多API变得更好。您可以引入带有签名的方法，例如：

public boolean isNeighborAlive(int x, int y, Direction which);

或者通过引入Vector2D类型使其更通用，该类型可能与Direction枚举非常相似；它会有公共静态的final字段，该字段包含指向北，南等的实例：

public final class Vector2D {
    public static final Vector2D N = new Vector2D(-1,0);
    // etc.

}

那么您可以使用以下方法来使用api：

public boolean isNeighborAlive(Vector2D point, Vector2D offset);

会产生类似如下的循环：

for (Vector2D offset : Vector2D.directions()) {
    cnt += b.isNeighborAlive(current, offset)? 1 : 0;
}

（您也可以使用将两个向量相加的方法，这可能会更干净，但也会产生更多的垃圾。

#7 楼

生活游戏的过渡功能是Bool ^ 9-> Bool的功能。这是一个有限且很小的函数。如果您进行了预先计算，则无需进行任何计算：只需遍历电路板，然后在该点上用函数的值替换每个单元格即可。

如果您喜欢这种想法，您可能会喜欢预先计算Bool ^ 16-> Bool ^ 4，它虽然较大，但仍然足够小以保留在RAM中，然后您可以以4倍的速度通过开发板，以2x2的单元矩阵填充每次迭代。

\ $ \ begingroup \ $
您忘记提及OP如何从当前的工作方式中获取Bool ^ 9的内容了……此外，尽管它们可以带来令人印象深刻的性能提升，但我的问题涉及像这样的高度特定的优化是它们使以后扩展或推广算法变得很麻烦-例如以支持更大的社区或其他州/自治区-并且使将来的读者（包括/主要是您将来的自我）更难以理解代码。 OP要求提供更精美的代码，而不必提供更快速/加密的代码。：P仍然可能对某人的确切情况有用。
\ $ \ endgroup \ $
– underscore_d
18/12/2在23:03

\ $ \ begingroup \ $
我认为查询表不仅速度更快，而且更短，更优雅。该代码可以轻松扩展到更大的社区，而真正需要更改的只是转换函数的编码。如果您还想将其抽象为不同颜色的单元格等，也可以轻松对其进行编码。
\ $ \ endgroup \ $
– Mayer Goldberg
19 Mar 7 '19 at 22:17

\ $ \ begingroup \ $
可能我当时对LUT的想法还不够。 ;）我一直在尝试Life的实现，其中包含一些额外的功能，并且最终可能想要在其上尝试LUT。我目前尚不清楚边界在哪里变得有用，即在哪里为过渡功能交易更具表现力的代码会变得有益。但是显然那可能更多是个人问题，毕竟我不是一个数学家。 :)我过去曾在4 MHz Z80上完成过QuadLife，所以我对更多异国情调的LUT并不陌生，尽管现在对我来说这很神奇！
\ $ \ endgroup \ $
– underscore_d
19年3月11日在14:11

#8 楼

您还可以通过让您的单元格始终包含其邻居数来计算邻居。当一个单元变为“活动”时，它将更新所有周围的单元，而当一个“死亡”时，它将减少所有周围的单元。

执行此操作基本上需要相同的代码，但取决于您是否获得值的数量或更频繁地进行更改可能会更快，因为更改仅在图块实际更改时发生，然后才在其周围的那个3x3点发生。

\ $ \ begingroup \ $
我喜欢这个主意，但是它不适合我当前的算法，因为我为每个“框架”构造了一块新板，而不是更换同一块板。这将使实例化新板变得非常繁琐。
\ $ \ endgroup \ $
– 11684
2014年9月8日上午10:58

\ $ \ begingroup \ $
为了提高性能，可以使用字节代替int（布尔也应占用1个字节）。
\ $ \ endgroup \ $
–龙胆K
15-10-16在10:38

#9 楼

就个人而言，如果我不想过多重构代码（因为项目太小或任何情况），我会选择：

static int countNeighbours(Board b, int x, int y) {
    return (b.getTile(x - 1, y - 1))   ? 1 : 0
           + (b.getTile(x, y - 1))     ? 1 : 0
           + (b.getTile(x + 1, y - 1)) ? 1 : 0
           + (b.getTile(x + 1, y))     ? 1 : 0
           + (b.getTile(x + 1, y + 1)) ? 1 : 0
           + (b.getTile(x, y + 1))     ? 1 : 0
           + (b.getTile(x - 1, y + 1)) ? 1 : 0
           + (b.getTile(x - 1, y))     ? 1 : 0;
}

并将getTile重命名为isAlive之类的名称。最终结果应类似于：

static int countNeighbours(Board b, int x, int y) {
    return (b.isAlive(x - 1, y - 1))   ? 1 : 0
           + (b.isAlive(x, y - 1))     ? 1 : 0
           + (b.isAlive(x + 1, y - 1)) ? 1 : 0
           + (b.isAlive(x + 1, y))     ? 1 : 0
           + (b.isAlive(x + 1, y + 1)) ? 1 : 0
           + (b.isAlive(x, y + 1))     ? 1 : 0
           + (b.isAlive(x - 1, y + 1)) ? 1 : 0
           + (b.isAlive(x - 1, y))     ? 1 : 0;
}

否则，我将使用@Janos或@rolfl的版本。

编程黑洞网