java - 实现由二维数组中的值支持的模型类的最快、最简洁/正确的方法是什么？

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 /事件处理程序类:

public class Handler implements EventHandler {

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

    // ... other stuff
  }
}

以下是每种方法的作用:

• 如果结构中存在未初始化的值或存在等于 0 的值，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 检查)是否存在任何一个尚未初始化的空间。可能看起来像这样:

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

但是，这仍然是一个 n^2 解决方案。不过，您可以做的是保留一个计数器，记录第一次初始化空间时可能减少的空间数量。那么 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时，您都会获取一个随机空间(包括已经初始化的空间)。如果您应该在每次调用时只选择一个随机的未初始化空间，那么您最好保留所有可能的网格位置的辅助数据结构，以便您可以轻松找到下一个随机开放空间并判断是否结构已满。

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

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