Discussion :

[Mako 5013]

Bonjour,

Je rencontre un petit soucis au niveau de l'architecture à adopter pour résoudre un problème.

Les données sont les suivantes :

Je dois résoudre un problème de rangement de boîtes (un peu à la manière du sac-à-dos). J'ai une liste de boîtes à faire rentrer dans un conteneur, et je veux une configuration me permettant cela. Le nombre de boîtes en question n'étant "pas trop grand", je veux dans un premier temps tester toutes les possibilités.

Les boîtes sont regroupées suivant leur taille, et je me retrouve donc par exemple à devoir placer 5 boîtes du type A, 3 boîtes du type B, etc. Le problème est en 3D (ce qui explique aussi que je préfère commencer par la force brute plutôt que par des méthodes heurisitiques...).

Je procède actuellement de la sorte :
- je prends un type de boîte encore restant, et qui rentre dans l'espace restant ;
- je place le maximum de boîtes de ce type dans mon conteneur et je mets à jour ce qu'il me reste à placer ;
- avec ce qu'il me reste, je créé une nouvelle disposition pour chaque type de boîtes encore restant que je peux faire entrer dans le conteneur.

J'aurais souhaité gérer cela avec des threads (le problème me semblant adéquat pour cela), c'est-à-dire créer un nouveau thread à chaque nouvelle disposition.

Le problème (enfin...) que je rencontre, c'est comment gérer cela "proprement". En effet, au départ, je ne sais pas combien de threads je vais devoir créer (combien de dispositions possibles je vais tester), et du coup, je ne sais pas trop comment savoir que tous mes threads ont terminés leur traitement (pour signifier à l'algorithme que c'est terminé, et que l'on peut rechercher une solution viable parmis celles proposées). En outre, je ne suis pas sûr que ma création de threads soient spécialement bien faites (c'est la première fois que je travaille avec des Executor).

Un extrait (simplifié) du code actuel :

Code Algorithme.java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
public class Algorithme {
 
/** Liste des rangements possibles */
private static List<Rangement> listeRangement = new ArrayList<Rangement>();
 
/** Nombre de threads ayant termines leur tache */
private static int nombreThreadsTermines = 0;
 
/** Manager des threads */
private static ExecutorService threadManager = Executors
			.newFixedThreadPool(4);
// 4 est totalement arbitraire...
 
/** Lance la resolution du probleme */
public static Rangement resolution() {
     // Va lancer un thread pour chaque type de boîte possedant au moins une occurence, et qui rentre dans le conteneur
     // Un tel thread est lance de la sorte
     Rangement rangement = new Rangement(.....);
     lancerNouveauThread(rangement);
 
    // Une fois la premiere serie de threads lances, j'aimerais pouvoir dire
    // "j'attends d'avoir explorer toutes les possibilites pour continuer"
}
 
/**
 * Lance un nouveau thread avec le rangement specifie.
 * 
 * @param _rangement
 *            Rangement le rangement a lancer dans un nouveau thread.
 */
protected static void lancerNouveauThread(Rangement _rangement) {
     ajouterRangement(_rangement);
     threadManager.execute(_rangement);
}
 
/**
 * Ajoute un rangement a l'algorithme.
 * 
 * @param _rangement
 *            Rangement a ajouter.
 */
public static synchronized void ajouterRangement(Rangement _rangement) {
     listeRangement.add(_rangement);
     System.out.println("Ajout du thread n°"+_rangement.getIdentifiant());
}
}

Et la classe Rangement (correspondant à une disposition des boîtes) :

Code Rangement.java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
public class Rangement implements Runnable {
 
     public void run() {
 
     // On range les boîtes tel que c'etait prevu lors de la creation du thread
 
     // On fait la meme chose que dans l'algorithme : on lance un nouveau thread
     // pour chaque type de boîte possedant au moins une occurence, et qui rentre dans le conteneur
     Rangement rangement = new Rangement(.....);
     Algorithme.lancerThread(rangement);
     }
}

J'espère avoir été assez clair...
Je reprécise donc que ce qui m'intéresse ici, c'est la gestion du pool de thread, et non pas l'algorithme en lui-même.

Merci aux courageux qui ont lu jusqu'ici

Mako.

[deathness]

N'étant pas un expert dedans je ne vais pas vraiment te conseiller sur la gestion du pool.

En revanche pourquoi traiter le problème avec des Threads? Il me semble que tu vas perdre pas mal de ressources à devoir synchroniser tes conteneurs.
Des Threads ne sont vraiment utiles que lorsque tu as des tâches parallélisables et véritablement indépendantes.

A moins que j'ai loupé quelque chose, il serait bien plus efficient et simple de faire un algo monoThread.

[Mako 5013]

A moins que j'ai loupé quelque chose, il serait bien plus efficient et simple de faire un algo monoThread.

Au départ, c'est ce que j'ai fait.

En revanche pourquoi traiter le problème avec des Threads? Il me semble que tu vas perdre pas mal de ressources à devoir synchroniser tes conteneurs.

Je ne synchronise pas mes conteneurs, ni les données du problème, étant donné que ces derniers évoluent de manière indépendante et incompatible. Petit exemple :

J'ai 1 boîte A et 1 boîte B. Mon algorithme va me créer initialement deux rangements différents. Le premier aura rangé la boîte A, et il lui restera B, et l'inverse pour le second. Les deux rangements ne présentent donc pas les mêmes caractéristiques : ils ont chacun un conteneur et une liste de boîtes restant à ranger, mais ce ne sont pas les mêmes ! Je gère cela en dupliquant mes objets (justement pour éviter de tout partager).

Pour ce qui est de l'utilité de la chose :
- je pensais (à tord peut-être...) que c'était un cas approprié ;
- je voulais me faire un peu la main sur les threads dans un cadre autre que l'exercice de style ;

(le projet qui est derrière tout ça n'est pas professionnel, et je cherche autant à apprendre des choses en le faisant qu'à le réaliser)

Bref, si c'est vraiment trop tiré par les cheveux, je laisse tomber, et j'amuserais avec des threads une autre fois, mais sinon, je suis toujours preneur de conseils.

Mako.

[Mako 5013]

Bonjour,

Avec le recul, je pense que deathness est dans le vrai, et que mon problème n'est pas adapté à un traitement multi-thread.

Je suis donc revenu à la solution de départ (mono-thread), et j'attendrais d'avoir un cas plus adéquat pour tester le multi-threading.

Je passe donc la discussion en "résolue".

Mako.