Examen intermédiaire - solution
1 Index inversé
Comme dit dans l'énoncé, l'idée d'un index inversé est de pouvoir rapidement trouver l'ensemble des documents contenant un mot donné. Cela suggère immédiatement l'utilisation d'une table associative pour un tel index : les mots trouvés dans les différents documents sont utilisés comme clef, et à chacun de ces mots est associé l'ensemble des documents le contenant.
La méthode documentsWithWord est très courte puisqu'elle fait une simple recherche dans la table. Elle doit toutefois faire attention à produire un ensemble vide pour les mots inexistants plutôt que null, comme demandé.
La méthode addDocument parcourt les mots du document à ajouter à l'index et ajoute le document à l'ensemble associé à chacun d'entre-eux. Elle doit pour ce faire prendre garde à bien créer cet ensemble si le mot n'a pas encore été rencontré.
public class ConcreteInvertedIndex implements InvertedIndex {
private Map<String, Set<Document>> index = new HashMap<>();
private static final Set<Document> EMPTY_DOC_SET =
new HashSet<>();
public void addDocument(Document d) {
Iterator<String> it = d.wordsIterator();
while (it.hasNext()) {
String w = it.next();
if (! index.containsKey(w))
index.put(w, new HashSet<Document>());
index.get(w).add(d);
}
}
public Set<Document> documentsWithWord(String word) {
return index.containsKey(word)
? index.get(word)
: EMPTY_DOC_SET;
}
}
2 Pile par morceaux
Une propriété importante de la pile par morceaux est que tous les morceaux sauf éventuellement le dernier sont toujours pleins. Dès lors, si on connaît le nombre d'éléments stockés dans la pile, il est facile de déterminer l'index du morceaux et la position dans ce morceau de l'élément au sommet de la pile : l'index du morceau (chunkIndex dans le code) s'obtient par division (entière) du nombre d'éléments par la taille des morceaux, et la position de l'élément dans le morceau (elementIndex dans le code) en calculant le reste de cette division.
Une fois ces valeurs calculées, le travail est simple. Il faut juste penser à ajouter ou à supprimer un morceau lorsque la position de l'élément à ajouter ou supprimer vaut 0. De plus, comme demandé dans l'énoncé, il faut mettre à null les entrées inutilisées du morceau, ce qui se fait dans la méthode pop.
public class ChunkedStack<E> implements Stack<E> {
private final static int CHUNK_SIZE = 100;
private int size = 0;
private List<E[]> chunks = new ArrayList<>();
public int size() {
return size;
}
public void push(E newElem) {
final int chunkIndex = size / CHUNK_SIZE;
final int elementIndex = size % CHUNK_SIZE;
if (elementIndex == 0)
chunks.add((E[]) new Object[CHUNK_SIZE]);
chunks.get(chunkIndex)[elementIndex] = newElem;
++size;
}
public E pop() {
if (size == 0)
throw new java.util.EmptyStackException();
final int chunkIndex = (size - 1) / CHUNK_SIZE;
final int elementIndex = (size - 1) % CHUNK_SIZE;
final E element = chunks.get(chunkIndex)[elementIndex];
if (elementIndex == 0)
chunks.remove(chunkIndex);
else
chunks.get(chunkIndex)[elementIndex] = null;
--size;
return element;
}
}
3 Graphe orienté acyclique
3.1 Partie 1
La méthode hashCode doit simplement combiner, d'une manière ou d'une autre, les valeurs de hachage des deux nœuds reliés par l'arc. La méthode equalsEdge doit quant à elle comparer les nœuds de départ et d'arrivée des deux arcs.
public int hashCode() {
return fromNode.hashCode() + 31 * toNode.hashCode();
}
private boolean equalsEdge(Edge<N> that) {
return this.fromNode.equals(that.fromNode)
&& this.toNode.equals(that.toNode);
}
3.2 Partie 2
La seule petite difficulté de la méthode removeNode est de s'assurer que les arcs référençant le nœud à supprimer soient supprimées également. Cela se fait par un simple parcours de l'ensemble des arêtes, au moyen d'un itérateur afin d'avoir accès à la méthode remove.
public void removeNode(N n) {
Iterator<Edge<N>> edgeIt = edges.iterator();
while (edgeIt.hasNext()) {
Edge<N> edge = edgeIt.next();
if (n.equals(edge.fromNode) || n.equals(edge.toNode))
edgeIt.remove();
}
nodes.remove(n);
}
3.3 Partie 3
Le plus gros du code de la méthode addEdge vérifie que les arguments sont valides, en s'assurant d'une part que les deux nœuds font partie du graphe, et d'autre part que l'ajout de l'arc ne produit pas de cycle. Cette dernière vérification se fait très simplement en s'assurant, grâce à la méthode isReachable, que le nœud de départ n'est pas atteignable depuis le nœud d'arrivée.
public void addEdge(N f, N t) {
if (! (nodes.contains(f) && nodes.contains(t)))
throw new IllegalArgumentException();
if (isReachable(t, f))
throw new IllegalArgumentException();
edges.add(new Edge<N>(f, t));
}
3.4 Partie 4
La version naïve de la méthode isReachable détermine très simplement si le second nœud est atteignable depuis le premier :
- si les deux nœuds sont égaux, le second est (trivialement) atteignable depuis le premier,
- sinon, si le second est atteignable depuis un des successeurs du premier, alors il est atteignable depuis le premier (puisque les successeurs d'un nœud sont, par définition, atteignables depuis lui),
- sinon, le second nœud n'est pas atteignable depuis le premier.
Etant donné que le graphe est acyclique, la récursion termine toujours.
public boolean isReachable(N f, N t) {
if (f.equals(t))
return true;
for (N succ : successors(f)) {
if (isReachable(succ, t))
return true;
}
return false;
}
3.5 Partie 5
La méthode isReachable ci-dessus parcourt tous les chemins sans se soucier de savoir si un nœud a déjà été visité. Dès lors, lorsqu'elle essaie de déterminer si le nœud 7 est atteignable depuis le nœud 1, elle parcourt tous les chemins partant du nœud 1, qui sont au nombre de quatre :
- \([1\rightarrow 2, 2\rightarrow 4, 4\rightarrow 5, 5\rightarrow 6]\)
- \([1\rightarrow 2, 2\rightarrow 4, 4\rightarrow 6]\)
- \([1\rightarrow 3, 3\rightarrow 4, 4\rightarrow 5, 5\rightarrow 6]\)
- \([1\rightarrow 3, 3\rightarrow 4, 4\rightarrow 6]\)
Le nœud 6 est donc visité 4 fois.
3.6 Partie 6
Pour éviter de visiter tous les chemins, la version améliorée de la méthode isReachable peut simplement se souvenir de tous les nœuds visités et éviter de revisiter les nœuds.
Naturellement, cela se fait en utilisant un ensemble de nœuds, initialement vide, et qui est passé lors des appels récursifs, ce qui nécessite la création d'une fonction auxilliaire.
public boolean isReachable(N f, N t) {
return isReachable(f, t, new HashSet<N>());
}
private boolean isReachable(N f, N t, Set<N> visited) {
if (f.equals(t))
return true;
for (N succ : successors(f)) {
if (!visited.contains(succ)) {
visited.add(succ);
if (isReachable(succ, t, visited))
return true;
}
}
return false;
}
A noter que la méthode add de l'interface Set retourne vrai si la valeur ajoutée n'était pas déjà présente dans l'ensemble. Il est donc possible de simplifier le code ainsi :
public boolean isReachable(N f, N t) {
return isReachable(f, t, new HashSet<N>());
}
private boolean isReachable(N f, N t, Set<N> visited) {
if (f.equals(t))
return true;
for (N succ : successors(f)) {
if (visited.add(succ) && isReachable(succ, t, visited))
return true;
}
return false;
}