Java: Recherche dans un tableau d'objets, pour 2 valeurs d'objet spécifiques

Question

Je réalise un projet en Java qui inclut des coordonnées (x, y). J'ai créé une classe de cellule qui a des entiers protégés X & Y; Lors de l'initialisation, je fais une boucle for qui définit un tableau de cellule en multipliant le X & Y donné par l'utilisateur, disons si X = 10 et Y = 10, je crée un tableau de cellules [100].

Cependant, comment puis-je effectuer une recherche rapide dans la matrice, sans effectuer de boucle for et en vérifiant chaque valeur individuellement?

Dire que je suis à la recherche de l'objet qui contient X = 5 & y = 3. Je sais que je peux passer par une boucle à la recherche d'objet avec des valeurs x et y, mais je me demandais s'il y a un façon de faire une recherche binaire et de trouver "un peu plus vite" l'objet [i] qui contient X = 5 et Y = 5.

Merci beaucoup.

Answer 1

la façon de le faire est d'organiser les objets cellulaires dans le tableau d'une manière pour qu'il y ait une application simple à partir d'un X, coordonnée y à l'index de la cellule dans la tableau.

Par exemple, laisse supposer que X et Y aller de 1 à 10. Supposons que nous arrangeons ensuite les cellules de sorte que:

array[0] = Cell(1, 1); 
array[1] = Cell(1, 2); 
... 
array[9] = Cell(1, 10); 
array[10] = Cell(2, 1); 
array[11] = Cell(2, 2); 
... 
array[99] = Cell(10, 10); 

Il devrait être facile de voir que nous pouvons calculer l'indice de la cellule (i, j) dans le tableau et aller chercher la cellule comme suit:

public Cell getCell(Cell[] array, int i, int j) { 
    int index = (10 * (i - 1)) + (j - 1); 
    return array[index]; 
} 

Telle est l'approche que les langages de programmation qui prennent en charge les types de tableaux N dimensions utilisent généralement pour les mettre en œuvre.

Cela peut être modifié trivialement pour traiter les cas où:

• 10 constante est quelque chose d'autre
• la matrice n'est pas carrée,
• la matrice a plus de deux dimensions
• index exécuter de 0 à N - 1 au lieu de 1 à N
• etcetera

Il existe plusieurs autres façons de représenter des matrices 2D dans Java. Le plus simple consiste simplement à utiliser un Cell[][] cells qui vous permet d'accéder aux cellules comme (par exemple) cells[i-1][j-1]. Des représentations plus compliquées peuvent être conçues qui utilisent moins d'espace si la matrice est clairsemée (c'est-à-dire que des cellules sont manquantes) au prix de code plus complexe et de temps d'accès plus lents.

Answer 2

Il semble que (si vous voulez utiliser la recherche binaire, de toute façon) vous définissez l'élément 0 à la cellule avec x = 0, y = 0; élément 1-x = 0, y = 1, etc. Dans ce cas, vous devriez être en mesure de calculer trivialement l'indice exact d'une cellule donnée:

// contains the Cell with x = desiredX, y = desiredY 
yourArray[desiredX * X + desiredY]; 

Si c'est ce que vous faites, cependant, il serait probablement plus simple de faire un tableau à 2 dimensions:

yourArray = new Cell[X][Y]; 
... 
yourArray[desiredX][desiredY]; 

Answer 3

les deux réponses ci-dessus montrent la méthode triviale pour obtenir rapidement l'index de tableau.Je voudrais proposer un hashmaps à usage alternatif avec des paires clé/valeur. la valeur pourrait être des objets. accéder aux éléments hashmap en temps constant ..