2

如果我有一个 64 长度的 java 数组 i[]，除了循环遍历整个数组之外，是否有一种快速的方法来确定该数组中的每个位置是否都是“满的”？我正在写一个黑白棋 AI，我需要知道整个数组是否已满。

4

4 回答 4

10

保留一个类型的标志变量long（64 位）并使用它通过设置或清除相关位来跟踪哪些数组条目是“满的”。（您需要将此与您的数组条目保持同步。）

如果您使用1每个位的值来表示相关单元格已满，您可以通过将标志变量与 进行比较来非常快速地判断整个数组是否已满-1L。

示例实现

int[] grid = new int[64];
long  full = 0L;

// place a piece at a certain grid position
grid[17] = 1;   // pretend 1 is the code for black
full |= 1L << 17;   // set bit 17 in our "full" tracker

// is the grid full?
if (full == -1L)
     // yes it is!
else
     // no it isn't

您可以更加狡猾，也可以使用标志变量来跟踪每个单元格的颜色，这样您就可以完全避免使用数组。一个变量跟踪给定单元格是否被占用，另一个变量跟踪颜色（例如，0 表示白色，1 表示黑色）。

long colour = 0L;
long full   = 0L;

// set position 17 to white
colour &= ~(1L << 17);    // clear the bit (white)
full   |=  (1L << 17);    // set it to occupied

// set position 42 to black
colour |=  (1L << 42);    // set the bit (black)
full   |=  (1L << 42);    // set it to occupied

// is position 25 occupied?
if ((full & (1L<<25)) != 0) {
    // yes, but what colour?
    if ((colour & (1L<<25)) != 0)
        // black
    else
        // white
}

// is the grid full?
if (full == -1L)
     // yes it is!
else
     // no it isn't
于 2012-04-19T09:35:53.063 回答
2

您可以单独保留许多“空”单元格，并在每次移动后对其进行更新。

但是我认为不需要这种优化：长度为 64 的循环必须非常快。请尝试查看这是否是一个真正的瓶颈，以及优化是否值得您努力。

于 2012-04-19T09:35:12.397 回答
0

您可以将两个 BitSet 用于黑白（或自由和非白色）。

于 2012-04-19T09:35:50.837 回答
0

Arrays.asList(i).contains(EMPTY)（可能您正在解释null为空）。

于 2012-04-19T09:37:12.920 回答