Trier plusieurs tableaux en multi-threadings

Signaler
Messages postés
5
Date d'inscription
vendredi 21 août 2020
Statut
Membre
Dernière intervention
28 avril 2021
-
Messages postés
5
Date d'inscription
vendredi 21 août 2020
Statut
Membre
Dernière intervention
28 avril 2021
-
Bonjours,

Il y a quelques choses à la quelles je ne comprends pas.

Prenons un exemple : Nous avons une liste de 10 tableaux, dans chaque tableau, il y a des valeurs entières désordonnées à la quelles je souhaite trier (triage à bulles). De plus chaque tableau une taille qui augmente de 10 pour chaque table dans la liste.

Exemple :

(1) [2,8,3,1,9,3,8,10,3,20]
(2) [2,8,3,1,9,3,8,10,3,20,2,8,3,1,9,3,8,10,3,20]
(3) [2,8,3,1,9,3,8,10,3,20,2,8,3,1,9,3,8,10,3,20,2,8,3,1,9,3,8,10,3,20]
...

De ce fait, je souhaite trier de manière ordonnée chaque table avec des threads qui s'occupes de chaque tableau. Mais, il est impératif qu’un thread ne commence par un tableau tant que celui d'avant n'a pas fini, et ce, de manière ordonné.

Exemple :
Threads 1 fais la liste numéro 1
Threads 2 fais la liste numéro 2
Quand le 2 a fini il fait la liste numéro 3 seulement si le Thread 1 a fini sa liste.

Là où je ne comprends pas, c'est comment est-il possible de partager ces informations entre threads de manière logique.

Merci de votre compréhension,

4 réponses

Messages postés
16319
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
29 avril 2021
2 824
Bonjour,

Dans ton cas les threads ne servent à rien puisque tu ne les exécutes pas en parallèle, mais l'un après l'autre, tu pourrais très bien faite pareil sans les threads.
Quant à ta question de partager des informations entre les threads elle n'a pas de sens ici puisque le thread1 sera terminé avant que le thread2 ne commence, donc ils ne pourront jamais communiquer ensemble.
Messages postés
5
Date d'inscription
vendredi 21 août 2020
Statut
Membre
Dernière intervention
28 avril 2021

Bonjours,

Merci de m'avoir répondu !

J'aimerais que tu saches que l'utilisation du thread pour cette exemple me permet de gagner du temps lorsqu'il trie un tableau contenant par exemple 100 000 éléments. Lors de ce tri, il prendra forcément du temps et pendant ce moment-là, j'aimerais ajouter un second thread afin qu'il puisse déjà lancer tri du second tableau, etc.

Pour le partage d'information entre les threads, pour moi il est impératif que l'un ne vas pas s'occuper du tableau 4 alors que le tableau 1 ou 2 n'est pas fini, d'où la raison de communiquer entre eux.

Je ne sais pas si c'est clair ce que je veux dire. Peut-être que si je pouvais te montrer mon code afin que tu voies ou je veux en venir ?

Bien à toi,
Messages postés
16319
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
29 avril 2021
2 824
Ces deux phrases sont contradictoires :
"j'aimerais ajouter un second thread afin qu'il puisse déjà lancer tri du second tableau, etc."
"il est impératif que l'un ne vas pas s'occuper du tableau 4 alors que le tableau 1 ou 2 n'est pas fini"
Tu peux faire l'un, ou l'autre, mais pas les deux en même temps.
Messages postés
16319
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
29 avril 2021
2 824
"dans chaque tableau, il y a des valeurs entières désordonnées à la quelles je souhaite trier (triage à bulles)"

Le tri à bulles est l'un des plus mauvais algorithmes de tri qui existe avec une complexité en O(n²), ce qui signifie que pour n = 100 000 éléments, le temps de tri est de l'ordre de n² = 10 000 000 000 calculs.
En comparaison, le tri fusion, l'un des meilleurs, a une complexité en O(n.ln2(n)), ce qui signifie que pour n = 100 000 éléments, le temps de tri est de l'ordre de n.ln2(n) = 1 661 000 calculs, soit 6000 fois moins (en théorie).

Java dispose déjà de méthodes de tris prêtes à l'emploi, y compris des versions multi-threads.
Exemple de temps de traitements, sur ma machine, pour des tableaux de 100 000 éléments :
  • BubbleSorter termine en 5 minutes 47 secondes (moyenne sur 10 tableaux différents)
  • Arrays.sort termine en 6.4 millisecondes (moyenne sur 1000 tableaux différents)
  • Arrays.parallelSort termine en 3.5 millisecondes (moyenne sur 1000 tableaux différents)

En pratique, le tri à bulles maison est donc 100 000 fois plus lent que le meilleur tri de Java.
Du coup, ton problème pourrait juste se résoudre en changeant l'algorithme de tri...
Messages postés
5
Date d'inscription
vendredi 21 août 2020
Statut
Membre
Dernière intervention
28 avril 2021

Encore merci de la patience que tu m'accordes.

J'aimerais que tu saches que cela n'a pas pour but de choisir le meilleur tri ou encore de savoir celle qui prend le moins de temps. Prend cela comme un exercice personnel afin d'avoir une meilleure compréhension des Threads :)

Je sais que j'ai du mal à te montrer l'intérêt de cela, mais je vais te montrer mon code java :

package model;

import util.Observable;
import java.util.ArrayList;
import java.util.List;

/**
 * La classe me permet de coordonnées les threads afin que je puisse lui passer
 * différents tableaux pour qu'il puisse trier.
 *
 * @author Force
 */
public class Sort extends Observable {

    private final List<ThreadSort> threadsSort = new ArrayList<>();
    private final List<int[]> tablesSort = new ArrayList<>();
    private final int SIZEMAX, SIZEINCREASE, NBTHREADS;
    private final String TYPESORT;
    private ThreadSort actualThread;

    /**
     * Le constructeur me permet de crée un nombre de tableaux définis dans une
     * liste.
     *
     * @param sizeMax ELle me permet de connaitre la taille maximum que doit
     * contenir un tableau
     * @param sizeIncrease Ceci servira d'incrémation afin d'arrier à la taille
     * maximum possible de crée.
     * @param nbThreads Le nombre de Threads que je peux utiliser durant les
     * tries.
     * @param typeSort Le type de trie qui sera mis en place lorsque l'on
     * triera.
     */
    public Sort(int sizeMax, int sizeIncrease, int nbThreads, String typeSort) {
        this.SIZEMAX = sizeMax;
        this.SIZEINCREASE = sizeIncrease;
        this.NBTHREADS = nbThreads;
        this.TYPESORT = typeSort;
        createTablesSort();
    }

    /**
     * La méthode permet de crée un tableau contenant des valeurs randoms.
     *
     * @param sizeTable Elle permet de connaitre la taille du tableau à définir.
     * @return Elle retourne un tableau d'entier contenant des valeurs randoms.
     */
    private int[] tableSortRandom(int sizeTable) {
        int[] randomTab = new int[sizeTable];

        for (int i = 0; i < sizeTable; ++i) {
            randomTab[i] = 0 + (int) (Math.random() * ((sizeTable + 0) + 1));
        }
        return randomTab;
    }

    /**
     * La méthode permet de crée un nombre X de tableaux, qui sera contenue dans
     * la liste, incrémanter par le SIZEINCREASE jusqu'à arriver au SIZEMAX.
     */
    private void createTablesSort(){
        for (int i = 0; i < SIZEMAX; i += SIZEINCREASE) {
            tablesSort.add(tableSortRandom(i));
        }
    }

    /**
     * La méthode permet de lancer un ou plusieurs Threads afin trier tous les
     * tableaux disponible.
     */
    public void sortMultiThreads(){
        
        for (int indexTab = 0; indexTab < tablesSort.size(); ++indexTab) {
            indexTab = createThreads(indexTab);
            multiThreads();
        }
    }

    /**
     * La méthode permet de prendre tous les threads et de regarder chacune 
     * pour récuper le résulat des opérations et du temps qu'il a pris.
     */
    private void multiThreads(){
        while (!threadsSort.isEmpty()) {
            for (int k = 0; k < threadsSort.size(); ++k) {
                if (!threadsSort.get(k).getStatut()) {
                    actualThread = threadsSort.get(k);
                    this.notifyObservers();
                    threadsSort.remove(k);
                }
            }
        }
    }

    /**
     *  La méthode permet de crées différentes threads pour chaque tableaux de 
     *  la liste selon le nombre threads que l'on dispose.
     */
    private int createThreads(int i) {
        for (int j=0; j<NBTHREADS && i<tablesSort.size(); ++j) {
            threadsSort.add(new ThreadSort(tablesSort.get(i),
                    TYPESORT));
            new Thread(threadsSort.get(j)).start();
            ++i;
        }
        return i;
    }

    /**
     * La méthode permet de connaitre le thread actuel pour connaitre 
     * l'information selon l'instant T.
     * 
     * @return Retourne le thread actuel que l'on souhaite observer.
     */
    public ThreadSort getActualSort(){
        return actualThread;
    }
}



------------------------


package model;

/**
 * La classe permet de crée un Runnable qui me permet de faire un tri d'un 
 * tableau selon le type de tri que l'on veut voir.
 *
 * @author Force
 */
public class ThreadSort implements Runnable {

    private int time, operation;
    private final int[] tableSort;
    private final String TYPESORT;
    private boolean status = true;

    /**
     * Le constructeur me permet de crée un Runnable me permettant de faire un 
     * tri d'un tableau selon le type de tri que l'on veut voir.
     *
     * @param tableSort Le tableau que l'on souhaite trier.
     * @param typeSort Le type de trie a effectuer lorsqu'il va trier.
     */
    public ThreadSort(int[] tableSort, String typeSort) {
        this.TYPESORT = typeSort;
        this.tableSort = tableSort;
    }

    @Override
    public void run(){
            long timeStart = System.currentTimeMillis();

            if ("Bubble".equals(TYPESORT)) {
                operation = new BubbleSort().sort(tableSort);
            } else {
                operation = new MergeSort().sort(tableSort);
            }

            time = (int) (System.currentTimeMillis() - timeStart);
            status = false;
    }

    /**
     * Permet de connaitre le temps que le threads à du mettre pour effectuer 
     * un tri.
     *
     * @return Retourne un entier.
     */
    public int getTime(){
        return time;
    }

    /**
     * Permet de connaitre le nombre d'opération effectué lorsqu'il a fini un 
     * tri.
     *
     * @return Retourne un entier.
     */
    public int getOperation(){
        return operation;
    }
    
    public boolean getStatut(){
        return status;
    }
}



----------------------


package view;

import model.Sort;
import util.Observer;

/**
 * La classe permet d'actualiser toutes les opérations qui se passe dans 
 * la classe Sort(). (Dans le futur cette classe prendra du JavaFX).
 *
 * @author Force
 */
public class ViewController implements Observer {

    private final Sort sort;
    
    /**
     * Le constructeur permet de crée une classe Sort() pour pouvoir trier des 
     * tables afin de connaitre le temps d'éxecutions et le nombre d'opérations.
     */
    public ViewController(){
        sort = new Sort(1000, 100, 3, "Merge");
        sort.addObserver(this);
        sort.sortMultiThreads();
    }
    
    @Override
    public void update(){
        System.out.println("Time : "+sort.getActualSort().getTime()
                +", Operation : "+sort.getActualSort().getOperation());
    }
}


Comme tu peux le voir dans la classe Sort() à la méthode sortMultiThreads(), je n'arrive pas à correctement crée une succession logique sans que l'un marche sur l'autre. :/