If THen ELse…

journal de bord d'un aspirant codeur

Article publié sur le blog d’Ippon Technologies le 23 juillet 2012

Article publié sur le blog d’Ippon Technologies le 22 mai 2012

Au cours d’un projet, je suis tombé récemment sur le bout de code suivant:

XmlNode xmlNode = itemBodyChildren.get(index);
if (xmlNode != null && xmlNode.getClass().getName() == referredClass.getName())
	return xmlNode;
else
	return null;

Ici il s’agit de vérifier si deux classes sont identiques en analysant leurs noms. Cette opération peut être réalisée de manière beaucoup plus simple: en effet, lorsqu’une classe est chargée pour la première fois, sa référence est conservée par le ClassLoader afin de pouvoir être réutilisée plus rapidement par la suite.

En conséquence, le programme suivant affichera toujours true:

Class a = Class.forName("Test");
Class b = Class.forName("Test");
System.out.println(a == b);

La code original aurait donc pu être écrit de la manière suivante:

XmlNode xmlNode = itemBodyChildren.get(index);
if (xmlNode != null && xmlNode.getClass() == referredClass)
	return xmlNode;
else
	return null;

Une dernière remarque pour finir: sans la persistance en mémoire des classes chargées par le ClassLoader, le code que j’ai exposé plus haut n’aurait pas été valide puisque son auteur a utilisé sans précaution la syntaxe == pour réaliser sa comparaison.

EDIT: pour les besoin d’un projet j’ai du développer une version de l’algorithme permettant de définir plusieurs points de départ et d’arrivée possible. Le résultat retourné correspond donc à la liste des points a parcourir (point de départ et destination inclus), telle que le chemin reliant ces deux points est le plus court parmi toutes les combinaisons existantes entre les différents points de depart et d’arrivée donnés. Les sources ainsi qu’un test unitaire sont disponibles ici.

Cela faisait un moment que je projetais de réaliser une implémentation soignée de l’algorithme de Dijkstra, c’est désormais chose faite.

Mon objectif était d’éviter d’avoir à choisir entre un implémentation parfaitement intelligible mais utilisant des structures de données particulières, des listes etc, et de l’autre une implémentations plus légère et optimisée mais peu compréhensible.

Au final je pense avoir trouvé le juste équilibre. Seul bémol: la recherche dans un graphe de grande taille nécessiterait de placer les points actifs dans une liste pour ne pas devoir parcourir tous les noeuds du graphe afin de sélectionner le prochain à analyser.

ps: Le graphe codé pour tester le fonctionnement de l’algo dans la main est tiré de wikipedia.

/**
 * Implementation de l'algorithme de Dijkstra. Attention: cette implementation
 * n'est pas thread-safe.
 * 
 */
public class Dijkstra implements Pathfinding {
 
	private int[][] graph;
 
	private int[] distanceFromStart;
 
	private boolean[] activesNodes;
 
	private int dim;
 
	private int[] precedences;
 
	private void activeAdjacents(final int node) {
		int distanceTo;
		for (int to = 0; to < this.dim; to++)
			if (this.isAdjacent(node, to) && (distanceTo = this.distanceFromStart[node] + this.graph[node][to]) < this.distanceFromStart[to])
				this.activeNode(node, to, distanceTo);
	}
 
	private void activeNode(final int from, final int node, final int distance) {
		this.distanceFromStart[node] = distance;
		this.precedences[node] = from;
		this.activesNodes[node] = true;
	}
 
	private List<Integer> buildPath(final int end) {
		final List<Integer> path = new ArrayList<Integer>();
		path.add(end);
 
		// utilisation d'une boucle do-while pour conserver le point de depart
		// et d'arrivee dans la liste même lorsque le point de depart correspond
		// au point d'arrivee
		int position = end;
		do {
			path.add(0, this.precedences[position]);
			position = path.get(0);
		} while (this.distanceFromStart[position] != 0);
 
		return path;
	}
 
	/**
	 * {@inheritDoc}
	 */
	@Override
	public List<Integer> getPath(final int[][] graph, final int start, final int end) {
		return this.getPath(graph, new int[] { start }, new int[] { end });
	}
 
	/**
	 * {@inheritDoc}
	 */
	@Override
	public List<Integer> getPath(final int[][] graph, final int start, final int[] ends) {
		return this.getPath(graph, new int[] { start }, ends);
	}
 
	/**
	 * {@inheritDoc}
	 */
	@Override
	public List<Integer> getPath(final int[][] graph, final int[] starts, final int[] ends) {
		Arrays.sort(ends);
 
		// initialisation des variables necessaires a la resolution du probleme
		this.init(graph, starts);
 
		// calcul des distances par rapport au point de depart et recuperation
		// du point d'arrivee
		final int end = this.processDistances(ends);
 
		return (end != -1) ? this.buildPath(end) : null;
	}
 
	private void init(final int[][] graph, final int[] start) {
		this.graph = graph;
		this.dim = graph.length;
		this.activesNodes = new boolean[this.dim];
 
		this.precedences = new int[this.dim];
		Arrays.fill(this.precedences, -1);
 
		this.distanceFromStart = new int[this.dim];
		Arrays.fill(this.distanceFromStart, Integer.MAX_VALUE);
 
		for (final int value : start)
			this.activeNode(value, value, 0);
	}
 
	private boolean isAdjacent(final int from, final int to) {
		return this.graph[from][to] >= 0;
	}
 
	private int processDistances(final int[] ends) {
		// selectionne le prochain noeud a analyser (noeud courant)
		final int next = this.selectNextNode();
 
		// return -1 s'il n'y a plus de noeud a analyser, donc qu'il n'existe
		// pas de chemin satisfaisant la recherche
		if (next == -1)
			return -1;
 
		// retourne la position du noeud actuel s'il appartient au tableau des
		// destinations possibles
		if (Arrays.binarySearch(ends, next) >= 0)
			return next;
 
		// active les prochains noeuds a analyser a partir du noeud courant
		this.activeAdjacents(next);
 
		// desactive le noeud courant
		this.activesNodes[next] = false;
 
		// appel recursif de la methode pour traiter le prochain noeud
		return this.processDistances(ends);
	}
 
	private int selectNextNode() {
		int nextNode = -1;
		for (int node = 0; node < this.dim; node++)
			if (this.activesNodes[node] && (nextNode == -1 || this.distanceFromStart[node] < this.distanceFromStart[nextNode]))
				nextNode = node;
 
		return nextNode;
	}
}

Forcer le retour à la ligne automatique à l’intérieur du composant Text de Flex n’est pas ce qu’il y a de plus évident. Pour y parvenir, vous devez indiquer la largeur de votre composant Text, et mettre condenseWhite à true.

Merci à Kerkness.ca pour l’astuce.

Le problème de la répartition des tâches entre des agents en concurrence est un problème récurrent dans toute organisation.
Exemple: quatre personnes sont employées à temps partiel pour occuper un bureau 10 heures par semaine. Les heures d’ouverture du bureau doivent avoir lieu entre 9h et 19h du lundi au jeudi et entre 9h à 12h le vendredi. Une seule personne est nécessaire pour assurer le bon fonctionnement du bureau à une heure donnée, et les quatre employés ont des contraintes qui les empêchent de travailler à certaines heures de la journée.

Pour un être humain normalement constitué (autistes atteint du syndrome d’Asperger mis à part donc), trouver une organisation qui permet de satisfaire toutes ces contraintes relève du casse-tête. Et pas de chance, ce type de problème appartient au groupe des NP-complet; c’est à dire qu’il n’existe à l’heure actuel aucun algorithme permettant de trouver une solution optimale à un tel problème en un temps raisonnable. En revanche, il existe tout une classe d’algorithme permettant de trouver des solutions acceptables, et les algorithmes génétiques en font partie.

L’idée générale est la suivante (merci Wikipedia):

schema_wikipedia

Structure de données.
Une seule structure nous importe: celle permettant de représenter une solution. Il faut garder à l’esprit que les solutions sont destinées à être recombinées afin d’en générer de nouvelles. Il faut donc que notre structure soit la plus simple possible afin que les croisements et les mutations que nous appliquerons ne soient pas trop complexes à implémenter. L’idéal est de travailler sur une structure à une dimension, c’est à dire un tableau. Si nous reprenons l’exemple de la répartition des heures d’ouverture entre nos quatre employés, nous pouvons imaginer la modélisation suivante: les indices de notre tableau représentent les différentes heures et ses éléments indiquent les numéros des employés de permanence.

Évaluation d’une solution (calcul du fitness).
Sans doute la partie la plus délicate, d’autant qu’il s’agit de prendre en compte différents critères d’efficacité. Toujours d’après l’exemple que j’ai exposé plus haut, nous savons que nous devons prendre en compte les contraintes suivantes:

  1. chaque employé doit travailler 10 heures dans la semaine.
  2. on a besoin que d’un employé par heure.
  3. certains employés ne peuvent pas travailler certaines heures de la journée.
  4. ouverture entre 9h et 19h du lundi au jeudi et entre 9h à 12h le vendredi.

Les contraintes 2 et 4 seront de toute façon respectées du fait de la structure de données que nous avons utilisé, nous pouvons donc les laisser de côté. Par contre il pourrait être intéressant de respecter les contraintes supplémentaires suivantes:

  1. il est préférable d’éviter les alternances bureau ouvert / bureau fermé dans la même journée.
  2. il est préférable que les heures de chaque employé soient regroupées pour leur éviter de nombreux aller-retour.

Si nous classons ces contraintes par ordre d’importance, nous avons:

  1. respect des heures impossibles à effectuer.
  2. quota des 10 heures.
  3. période de fermeture entre deux périodes d’ouverture dans la même journée.
  4. regroupement des heures pour un même employé.

Pour chaque solution, notre fonction d’évaluation devra comptabiliser les infractions de chacune de ces contraintes et appliquer un coefficient aux valeur ainsi calculées avant de les additionner. La pertinence d’une solution variera donc en sens inverse du résultat retourné par cette fonction.

L’application des coefficients est importante: c’est grâce à elle que notre algorithme saura qu’une solution affectant une heure de travail à un employé pourtant indisponible à ce moment là sera moins bonne qu’une autre solution qui fera fermer le bureau entre 14h et 15h le mardi par exemple. Les coefficients que j’ai utilisé sont calculés à l’aide de la formule: 100nombre de contraintes à prendre en compte (donc 4) – degrés d’importance de la contrainte (compris entre 1 et 4).

Sélection, croisement et mutation.
Internet fourmille de solutions toutes différentes les unes des autres. Leur implémentation ne pose aucun problème donc je ne les détaillerais pas ici. Pour cette article j’ai implémenté une sélection par rang, une mutation de type swap et un croisement tout personnel: deux parents donnent un enfant et chaque gêne des parents à une probabilité de 0.5 d’être attribué à l’enfant.

Architecture.
Les algorithmes génétiques peuvent être utilisés pour résoudre de très nombreux problèmes; l’idéal serait donc de pouvoir réutiliser les algorithmes que nous avons écrit. Il faut donc décrire les interfaces de chacune des structures et opérations réalisées (structure de donnée de type chromosome, évaluation, sélection, croisement et mutation). Seules la fonction d’évaluation ainsi que la structure chromosome devraient être modifiées pour que notre système puisse s’attaquer à d’autres problèmes.

Darwin: 1 – créationnisme: 0
Une population de départ générée aléatoirement, des sélections plus ou moins arbitraires, des croisements et des mutations qui se décident à coup de random… tout porte à croire que la mise en oeuvre d’un tel dispositif ne pourra jamais aboutir à une solution acceptable. Et comme une image vaut mieux que mille mots:

graphe

Les fitness moyen et optimal décroissent très rapidement (la taille de la population de départ est de 800 individus), cela signifie que les solutions générées sont de plus en plus pertinentes. Arrivé à la génération 25 on ne note plus de changement important (le fitness se stabilise autour de 20). Un fitness de 20 signifie que toutes les contraintes ont été respectées, et que les employés feront en moyenne des séances de travail de 2 heures.

Je mets en ligne une classe permettant de dissimuler de l’information au sein d’images BMP, en modifiant les bits de poids faible des couleurs qui composent l’image. Ça faisait longtemps qu’elle traînait dans mon workspace mais je n’avais jamais trouvé le temps de la dépoussiérer et de la commenter. C’est désormais chose faîte. La méthode de dissimulation utilisée est loin d’être au top de ce qui se fait de mieux aujourd’hui, mais c’est toujours amusant à utiliser.

Les serveurs MySQL de Free sont bridés: le moteur InnoDB n’est pas activé et vous n’avez pas les droits nécessaires pour verrouiller des tables avec l’appel LOCK TABLES normalement disponible avec MyISAM. Comment faire dans ce cas pour gérer la concurrence? En utilisant la fonction GET_LOCK(str, timeout). L’argument str identifie le verrou (on peut ainsi simuler l’utilisation de multiples verrous) et timeout indique le délai d’expiration de la requête de blocage.

Cette fonction permet d’établir des sections critiques dans votre code, cela implique donc que la bonne gestion de la concurrence ne relève plus du SGBD mais qu’elle est désormais de votre responsabilité. Avec cette méthode vous pouvez facilement verrouiller des tables indépendamment les une des autres, ainsi que des lignes (l’identifiant d’un verrou de ligne correspondra alors à la concaténation du nom de la table et de l’identifiant de la ligne).

xkcd

Original (xkcd)

Il y a quelques temps j’ai dû interviewer des candidats pour un poste de d’ingénieur Java. L’une des questions que je leur posais était « que pouvez vous me dire à propos des références faibles? ». Je n’attendais pas de détails techniques. J’aurais probablement été satisfait par un « hum… est ce que ça n’aurait pas à voir avec le ramasse-miettes? ». À la place, j’ai été surpris de voir que sur les 20 ingénieurs postulants, tous ayant au moins 5 ans d’expérience dans le développement Java et de bonnes qualifications, seulement deux savaient que les références faibles existaient, et un seul parmi ces deux avait une connaissance pratique du sujet. [...] J’ignore pourquoi cette connaissance est aussi peu répandue, dans la mesure où les références faibles sont incontournables depuis la sortie de Java 1.2, il y a 7 ans de cela.

Source: Understanding Weak References de Ethan Nicholas

Introduction 2 en 1: à la fois instructive tout en présentant l’intérêt d’excuser par avance l’ignorance de l’auteur de ce blog. Je ne vais pas rappeler ici l’intérêt du ramasse-miettes (garbage collector) ainsi que le concept de compteur de références: vous pourrez retrouver ces informations dans l’introduction de l’article que j’avais écrit sur le fonctionnement du garbage collector d’ActionScript. En effet, les fondamentaux étant les mêmes en ce qui concerne son fonctionnement, les pratiques induisant des fuites mémoire sont également identiques: elles concernent principalement la gestion des écouteurs ainsi que celle des tables de hachage.

Les références faibles.
Des références faibles peuvent être créées à l’aide des classes WeakReference et SoftReference. Toutes deux héritent de la classe Reference et s’utilisent de la même manière. Ainsi, pour manipuler une WeakReference vous devez procéder de la manière suivante:

// donnée à faiblement référencer 
Object o1 = new Object();
 
// création de la référence faible
WeakReference ref = new WeakReference(o1);
 
// récupération de la valeur faiblement référencée
Object o2 = ref.get();
 
boolean isEqual = o1 == o2; // isEqual = true

Une fois créé, on peut accéder à l’objet faiblement référencé à l’aide de la méthode get(). Dans le cas de l’utilisation d’une WeakReference, cette méthode renverra:

  • une référence vers l’objet si et seulement si la dernière vérification du garbage collector a révélé qu’il existe au moins une référence forte menant à lui.
  • sinon null.

En revanche, dans le cas d’une SoftReference, la méthode renverra:

  • null si et seulement si la mémoire allouée pour la machine virtuelle sature et qu’il n’existe plus de références fortes pointant vers l’objet faiblement référencé.
  • sinon la référence.

Cette différence nous indique dans quel cas utiliser l’une ou l’autre des références faibles:

  • On utilisera la classe SoftReference lorsque les données qui ne sont plus fortement référencées sont malgré tout susceptibles d’être utilisées plus tard, et que l’on souhaite donc les conserver autant que possible. Cette exigence serait tout à fait justifiée dans le cas d’un système mettant en cache des images: tant que la mémoire n’est pas saturée, il peut être intéressant de conserver des images qui ne sont plus utilisées car rien n’indique que l’utilisateur ne souhaitera pas les manipuler à nouveau. En faisant cela on économise le temps des accès sur le disque dur sans remettre en question la stabilité de l’application.
  • On utilisera la classe WeakReference dans les situations où les données qui ne sont plus fortement référencées peuvent être supprimées de la mémoire sans attendre.

Attention: dans la mesure où la référence de l’objet est susceptible d’être supprimée à tout moment, vous ne pouvez pas vous contenter de vérifier son existence à l’aide du test:

if(ref.get() != null) {
	// traitement
}

En effet, rien ne vous garantit que le garbage collector n’interviendra pas juste après votre vérification, pendant le traitement, en supprimant l’objet de la mémoire. Vous devez donc procéder comme suit afin de créer une référence forte empêchant toute intervention du GC par la suite:

Object o = ref.get();
if(o != null) {
	// traitement
}

Retrouver les références inutiles.
Il faut bien comprendre que ce sont les données référencées qui sont susceptible d’être supprimées, et en aucun cas les objets WeakReference et SoftReference utilisés. Ainsi dans l’exemple suivant:

String s1 = "s1";
String s2 = "s2";
 
ArrayList<WeakReference<String>> array = new ArrayList<WeakReference<String>>();
array.add(new WeakReference(s1));
array.add(new WeakReference(s2));
 
s2 = null;

à la fin de la manipulation, l’objet array contiendra toujours 2 éléments de type WeakReference. En revanche, array.get(1).get() renverra null et non un String contenant la valeur « s2″. Il nous reste donc à voir comment supprimer de la mémoire les WeakReference et SoftReference devenus inutiles.

Nettoyage des WeakReference/SoftReference inutiles.
Pour cela vous avez deux solutions:

  • la première consiste à parcourir régulièrement l’ensemble des références faibles dont vous disposez pour voir lesquelles d’entre elles peuvent être supprimées de la mémoire. Cette solution ne présente pas d’inconvénient si vous n’avez à parcourir qu’un faible nombre de données.
  • dans le cas contraire vous aurez l’utilité de la classe ReferenceQueue. Il s’agit en fait d’une liste que l’on placera dans le constructeur de nos références faibles. A chaque fois que le contenu d’une référence sera supprimée de la mémoire, une instance de cette même référence sera placé dans la liste. Vous pourrez donc suivre facilement le nombre de références faibles inutiles et procéder à leur nettoyage quand bon vous semblera.

Utilité des références faibles.
Les écouteurs d’évènements.
En Java, les écouteurs s’enregistrent auprès des diffuseurs d’évènements pour être averti lorsqu’une action a été déclenchée. Cela signifie que les diffuseurs possèdent tous une liste des écouteurs qu’ils doivent notifier; et c’est justement cette liste qui peut être à l’origine de fuites mémoire si le programmeur oublie de supprimer les écouteurs dont il n’a plus l’utilité. Mais, contrairement à ActionScript, Java n’offre pas pas la possibilité de demander, lors de l’enregistrement des écouteurs, l’utilisation de références faibles. Nous n’avons dans ce cas précis pas d’autre choix que d’utiliser les méthodes removeListener.
En revanche, rien ne vous empêche d’implémenter un système prenant en compte les références faibles lorsque vous programmez vos propres diffuseurs d’évènements.

Tables de hachage.
Il peut arriver que vous souhaitiez associer des données supplémentaires à des objets que vous ne pouvez pas étendre. L’utilisation d’une table de hachage se révèle alors intéressante, à la condition toutefois que vous pensiez à supprimer au fur et à mesure les clés que vous n’utilisez plus, ou bien que vous utilisiez une WeakHashMap qui fera le travail toute seule. En effet, la classe WeakHashMap encapsule elle même toutes les clés que vous lui passé dans des WeakReference, et pourra donc purger régulièrement les références dont le contenu est null.
Attention, la WeakHashMap ne peut en aucun cas servir de cache, car se sont les clés et non les données qui sont faiblement référencées. Ceci étant dit, rien en vous empêche de créer votre propre table de hachage dont les données seraient faiblement référencées.

Autre source: ici.