Mutable int ? (passage par référence)

Résolu/Fermé
mikis69 Messages postés 168 Date d'inscription mardi 26 novembre 2013 Statut Membre Dernière intervention 11 février 2019 - Modifié le 24 mars 2017 à 00:43
mikis69 Messages postés 168 Date d'inscription mardi 26 novembre 2013 Statut Membre Dernière intervention 11 février 2019 - 7 avril 2017 à 00:35
Bonjour à toutes et à tous,

Je suis actuellement confronté à un petit problème auquel j'ai trouvé une solution qui me convient mais ce n'est pas parce qu'elle me convient qu'elle est correcte. Je voudrai donc votre avis à ce propos :

Je dois construire un arbre des suffixes selon la méthode de Ukkonen et donc avoir une construction de cet arbre en O(n).
Une bonne explication a été écrite à ce lien : https://stackoverflow.com/questions/9452701/ukkonens-suffix-tree-algorithm-in-plain-english

Je ne vais pas parler ici de l'arbre des suffixes mais de ce qui me tracasse..

En gros, on a
- un mot de taille n
- une variable # qui représente la position courante dans le mot
- une boucle for(int i = 0; i < n; i++)
- # qui vaut i

et à chaque passage dans le for on créé un noeud : new Node(0, #)

Le soucis est qu'en java, si je déclare '#' comme un int et que je crée le noeud de cette manière new Node(0, #), je vais récupérer la valeur # à l'étape courante, donc j'aurai 5 noeuds avec

- noeud 1 : fin = 1
- noeud 2 : fin = 2
- noeud 3 : fin = 3
...

Or ce que je veux c'est que cette variable # continue de s'incrémenter automatiquement dans les noeuds où elle est référencée. De cette manière à la fin de la boucle, on aura tous les noeuds avec leur position de début mais la position de fin qui sera égale à 5 (et je ne peux pas la mettre directement à 5 la valeur de fin car j'ai besoin de dire qu'à l'itération i, on finit au caractère i du mot).

J'ai donc trouvé cette solution : utilisé le type AtomicInteger pour représenter la variable # et donc on passerait cet objet en créant le noeud et on aurait


public Node(int debut, AtomicInteger fin) {

}

public int getFin() {
return fin.intValue();
}


Avec ce type pour représenter # j'aurai :

- noeud 1 : fin = n
- noeud 2 : fin = n
....

Qu'en pensez-vous ? Y a t-il d'autre alternative que de passer par un objet qui est mutable ?

Merci pour vos réponses,

Mikis
A voir également:

2 réponses

KX Messages postés 16752 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 août 2024 3 019
Modifié le 24 mars 2017 à 07:11
Bonjour,

AtomicInteger
fait le job bien qu'il ne sert pas à ça normalement. Tu aurais aussi pu faire un
int[] tab = new int[1];
et changer la valeur de
tab[0]
.

Cependant je pense que la bonne pratique est de mettre l'entier comme attribut de la classe courante.

int k;

public Node(int debut) {
    k = debut;
}

public int getFin() {
   return k;
}

À voir ce que ça donne dans le contexte.
La confiance n'exclut pas le contrôle
0
mikis69 Messages postés 168 Date d'inscription mardi 26 novembre 2013 Statut Membre Dernière intervention 11 février 2019
24 mars 2017 à 12:06
Si je fais ma classe Node de cette manière

int debut;
int fin;

public Node(int debut, int fin) {
    this.debut = debut;
    this.fin = fin;
}

public int getFin() {
    return fin;
}


La valeur fin ne changera jamais car elle a juste la valeur du int (à l'instant courant) lors de sa construction. Or si je passe la référence de l'objet AtomicInteger, j'ai la valeur finale (n) lorsque je fais un

AtomicInteger fin;

...

public int getFin() {
   return fin.intValue();
}


Maintenant à savoir si c'est un bonne solution ou pas.. ?
0
KX Messages postés 16752 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 août 2024 3 019
24 mars 2017 à 18:42
"La valeur fin ne changera jamais car elle a juste la valeur du int (à l'instant courant) lors de sa construction"
Rien ne t'empêches de changer la valeur du int k; au fur et à mesure, de même que tu changes la valeur de ton AtomicInteger.

Par contre si tu arrives à ce genre de question c'est peut être que ce n'est pas à l'objet Node de porter cette information de fin, mais qu'elle est à récupérer ailleurs.

Est ce que tu pourrais donner un code plus complet pour revoir éventuellement la structure de bade que tu utilises ?
0
mikis69 Messages postés 168 Date d'inscription mardi 26 novembre 2013 Statut Membre Dernière intervention 11 février 2019 > KX Messages postés 16752 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 août 2024
24 mars 2017 à 20:03
En fait c'est une structure en arbre donc on a une racine (un noeud root) qui a des noeuds fils.
Donc on fait comme je l'ai dit dans le premier poste, on a un mot de longueur n et il faut construire l'arbre des suffixes en O(n). On peut donc faire une seule boucle for(int i = 0; i < n; i++).
Si la valeur fin ne se met pas à jour automatiquement (comme avec le AtomicInteger), alors je devrai faire par exemple :

for(int i = 0; i < n; i++) {
   for(Node n : root.getFils()) {
         n.updateFin(i);
   }
}


Mais ici alors je ne suis plus en O(n) si à chaque itération je dois manuellement mettre à jour la valeur de fin de chaque fils.

L'objet Node est obligé de savoir quand il finit (à l'itération i) normalement.. Mais je me demande si cette information est vraiment nécessaire dans la classe Node puisque tout le traitement (normalement) se fait dans la classe SuffixTree (du coup, je me demande si je vais pas utiliser le 'i' à proprement dit à la place)

Je n'ai pas encore le code car j'essaie de comprendre correctement l'algorithme proposé par Ukkonen avant de me mettre à l'implémenter. Je me renseigne simplement pour savoir si c'est correct d'utiliser le AtomicInteger.

Merci pour ta réponse en tout cas ^^
0
KX Messages postés 16752 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 août 2024 3 019
24 mars 2017 à 21:04
Peut-être pourrais-tu utiliser une classe interne.

Exemple :

public class Arbre {
    int debut, fin;
    // ...

    public class Node {
        // ...
    }
}

Dans ce cas, tu crées d'abord un objet Arbre, qui porte les valeurs début/fin.
Puis tu créés des objets Node qui appartiennent à cet arbre, et partagent donc toutes les valeurs de l'Arbre.

Arbre arbre = new Arbre();
Node node = arbre.new Node();
0
mikis69 Messages postés 168 Date d'inscription mardi 26 novembre 2013 Statut Membre Dernière intervention 11 février 2019
25 mars 2017 à 00:18
J'ai effectivement vu une implémentation qui utilise cette structure avec des classes internes mais mes professeurs m'ont toujours découragé à les utiliser, je ne voulais donc pas "recopier" cette manière de faire..

Mais pourquoi pas utiliser cette manière, je n'y suis pas familier mais je peux essayer :)

Je finis de comprendre l'algorithme et après je me met à l'implémentation (J'ai mis le lien dans le premier poste pour plus d'information, si ce que j'ai expliqué n'était pas clair au cas où ^^)

Je reviendrai ici lorsque j'aurai plus d'info sur l'implémentation !

Merci en tout cas pour l'idée
0
mikis69 Messages postés 168 Date d'inscription mardi 26 novembre 2013 Statut Membre Dernière intervention 11 février 2019
7 avril 2017 à 00:35
Finalement KX, tu avais raison !

L'attribut fin pour la classe Node n'avait pas lieu d'être car nous n'en avons pas besoin pour construire l'arbre des suffixes. Enfin si, nous en avons besoin mais pas sous la forme d'un mutable int. Nous en avons besoin simplement lorsque l'on crée un noeud interne qui aura un fin fixe (sauf si on sépare ce même noeud mais dans ce cas, un simple setFin(int fin) est suffisant)

Je suis désolé du retard pour la réponse, mais beaucoup de boulot avec l'école, du coup, j'ai seulement eu fini l'implémentation de l'arbre maintenant ^^

Je te remercie :)

Mikis
0