Quelle est la manière la plus rapide et la plus concise/correcte d'implémenter cette classe de modèle soutenue par des valeurs dans un tableau à deux dimensions?

Question

Je résolu ce problème à l'aide d'un graphique, mais malheureusement maintenant je suis coincé à devoir utiliser un tableau 2d et je poser des questions sur la meilleure façon d'aller à ce sujet:

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 
    } 

} 

J'ai un contrôleur/événement classe de gestionnaire:

public class Handler implements EventHandler { 

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

    // ... other stuff 
    } 
} 

Voici ce que chaque méthode fera:

• Data.generateRandom() va générer une valeur aléatoire à un endroit aléatoire dans le tableau 2d int si la re existe une valeur dans la structure qui n'est pas initialisée ou une valeur qui est égale à zéro
• Si il n'y a pas de place disponible dans la structure, l'état de la structure est final (c.-à-d. au sens littéral, et non pas la déclaration Java)

Voilà ce que je me demande:

Quelle est la façon la plus efficace de vérifier si la carte est pleine? En utilisant un graphique, j'ai pu vérifier si la carte était pleine sur O (1) et obtenir un emplacement disponible mais aussi aléatoire sur le pire cas O (n^2 - 1), dans le meilleur des cas O (1). Évidemment, maintenant, avec une amélioration de tableau n^2 est difficile, donc je me concentre maintenant sur la vitesse d'exécution et LOC. Est-ce que le meilleur moyen de le faire maintenant pour vérifier l'ensemble de tableau 2D en utilisant des flux comme:

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

Answer 1

(1) Vous pouvez certainement utiliser un flux parallèle à exécuter en toute sécurité en lecture seule des opérations sur le tableau. Vous pouvez également faire un appel anyMatch puisque vous vous en souciez seulement (pour la vérification isFull) s'il existe un espace qui n'a pas été initialisé. Cela pourrait ressembler à ceci:

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

Cependant, c'est toujours une solution n^2. Ce que vous pourriez faire, cependant, est de garder un compteur du nombre d'espaces possibles que vous décrémenter lorsque vous initialisez un espace pour la première fois. Ensuite, le contrôle isFull sera toujours à temps constant (vous comparez simplement un 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; 
    } 
} 

Maintenant, ceci est ma compréhension que chaque fois que vous appelez generateRandom vous prenez un espace aléatoire (y compris ceux qui sont déjà initialisés). Si vous êtes supposé choisir UNIQUEMENT un espace aléatoire non initialisé chaque fois qu'il est appelé, alors vous feriez mieux de conserver une structure de données auxiliaire de tous les emplacements de grille possibles afin que vous puissiez facilement trouver l'espace ouvert aléatoire suivant et dire si le la structure est pleine.

(2) Quelle méthode de notification est appropriée pour permettre aux autres classes de connaître le tableau est maintenant immuable? C'est un peu difficile à dire car cela dépend du cas d'utilisation et de l'architecture du reste du système dans lequel il est utilisé. S'il s'agit d'une application MVC avec une utilisation intensive des notifications entre le modèle de données et un contrôleur, alors observateur/modèle observable a beaucoup de sens. Mais si votre application ne l'utilise nulle part ailleurs, alors peut-être que simplement avoir les classes qui se soucient de vérifier la méthode isFull aurait plus de sens.

(3) Java est efficace pour créer et libérer des objets de courte durée. Cependant, comme les tableaux peuvent être assez volumineux, je dirais qu'allouer un nouvel objet tableau (et copier les données) sur chaque fois que vous modifiez le tableau semble ... inefficace au mieux.Java a la capacité de faire quelques types fonctionnels de programmation (en particulier avec l'inclusion de lambdas dans Java 8) mais seulement en utilisant des objets immuables et un style purement fonctionnel est un peu comme le trou rond de la cheville carrée de Java.