实现此模型 class 由二维数组中的值支持的最快且最 concise/correct 的方法是什么？

Question

我用图表解决了这个问题，但不幸的是现在我不得不使用二维数组，我对解决这个问题的最佳方法有疑问：

public class Data {

  int[][] structure;

  public data(int x, int y){
    structure = new int[x][y]
  }

  public <<TBD>> generateRandom() {
     // This is what my question is about
  }

}

我有一个 controller/event 处理程序 class:

public class Handler implements EventHandler {

  @Override
  public void onEvent(Event<T> e) {
    this.dataInstance.generateRandom();

    // ... other stuff
  }
}

以下是每种方法的作用：

Data.generateRandom() 将在 2d int 数组中的随机位置生成一个随机值，如果结构中存在未初始化的值或存在等于零的值
如果结构中没有可用位置，则结构的状态为最终状态（即字面意义上的，而不是Java声明）

这就是我想知道的：

检查看板是否已满的最有效方法是什么？使用图表，我能够在 O(1) 上检查电路板是否已满，并在最坏情况下 O(n^2 - 1)、最佳情况下 O(1) 上获得可用但也是随机的位置。显然现在用数组改进 n^2 很困难，所以我现在只关注执行速度和 LOC。现在最快的方法是使用如下流检查整个二维数组：

Arrays.stream(board).flatMapToInt(tile -> tile.getX()).map(x -> x > 0).count() > board.getWidth() * board.getHeight()

Answer 1

(1) 你绝对可以使用并行流来安全地对数组执行只读操作。您也可以执行 anyMatch 调用，因为您只关心（对于 isFull 检查）是否存在任何未初始化的 space。可能看起来像这样：

Arrays.stream(structure)
      .parallel()
      .anyMatch(i -> i == 0)

然而，这仍然是 n^2 解。不过，您可以做的是保留一个计数器，记录您在第一次初始化 space 时可能减少的 space 的数量。然后 isFull 检查将始终是常数时间（您只是将 int 与 0 进行比较）。

public class Data {

    private int numUninitialized;
    private int[][] structure;

    public Data(int x, int y) {
        if (x <= 0 || y <= 0) {
            throw new IllegalArgumentException("You can't create a Data object with an argument that isn't a positive integer.");
        }
        structure = new int[x][y];
        int numUninitialized = x * y;
    }

    public void generateRandom() {
        if (isFull()) {
            // do whatever you want when the array is full
        } else {
            // Calculate the random space you want to set a value for
            int x = ThreadLocalRandom.current().nextInt(structure.length);
            int y = ThreadLocalRandom.current().nextInt(structure[0].length);
            if (structure[x][y] == 0) {
                // A new, uninitialized space
                numUninitialized--;
            }
            // Populate the space with a random value
            structure[x][y] = ThreadLocalRandom.current().nextInt(Integer.MIN_VALUE, Integer.MAX_VALUE);
        }
    }

    public boolean isFull() {
        return 0 == numUninitialized;
    }
}

现在，根据我的理解，每次调用 generateRandom 时都会随机取一个 space（包括已经初始化的）。如果你应该在每次调用时只选择一个随机未初始化的 space，那么你最好保存所有可能的网格位置的辅助数据结构，以便你可以轻松找到下一个随机打开 space 并判断结构是否已满。

(2) 什么通知方法适合让其他类知道数组现在是不可变的？这很难说，因为它取决于用例和正在使用的系统其余部分的体系结构。如果这是一个 MVC 应用程序，在数据模型和控制器之间大量使用通知，那么observer/observable 模式很有意义。但是，如果您的应用程序没有在其他任何地方使用它，那么也许只是让类关心检查 isFull 方法会更有意义。

(3) Java 在创建和释放短期对象方面非常有效。但是，由于数组可能非常大，我会说每次更改数组时都分配一个新的数组对象（并复制数据）似乎......充其量是低效的。 Java 有能力进行一些函数式编程（尤其是在 Java 8 中包含 lambda），但仅使用不可变对象和纯函数式风格有点像 Java的方钉。

实现此模型 class 由二维数组中的值支持的最快且最 concise/correct 的方法是什么？

What is the fastest and most concise/correct way to implement this model class backed by values in a 2-dimensional array?

java

arrays

performance

big-o