Differences

This shows you the differences between two versions of the page.

--- in204:tds:sujets:td8:part3 [2020/11/02 17:56]
bmonsuez [Question n°2]
+++ in204:tds:sujets:td8:part3 [2022/11/18 10:49] (current)
@@ Line 1: / Line 1: @@
-====== Exécution asynchrone ======
+====== Partie III – Algorithmes génériques======
-[[in204:tds:sujets:td8|TD8]]
+Dans la conclusion du cours, nous affirmons qu’un intérêt du polymorphisme, c’est de pouvoir écrire un algorithme « générique », c’est à dire un algorithme qui pourra fonctionner pour des objets représentant des données de plusieurs types.
-===== Références=====
+Nous considérons un algorithme de tri très simple qui fonctionne sur des entiers :
-[[http://en.cppreference.com/w/cpp/thread/async|std::async]] [[http://en.cppreference.com/w/cpp/thread/future|std::future]]
-===== Question n°1 =====
-Nous considérons la fonction suivante qui calcule les décimales de « e ».
 <code cpp>
-std::string computeE(int numberOfDigits)
+void insertion_sort(std::vector<int>& anArray)
 {
-	int sizeOfTable = numberOfDigits + 9;
+	for (int i = 0; i < anArray.size(); i++)
-	int* table = (int*)_alloca(sizeOfTable * sizeof(numberOfDigits));
-	table[0] = 0;
-	table[1] = 2;
-	for (int i = sizeOfTable - 1; i > 0; i--) {
-		table[i] = 1;
-	}
-	std::ostringstream output;
-	int x = 0;
-	table[1] = 2;
-	for (; sizeOfTable > 9; sizeOfTable -- )
 	{
-		for (int i = sizeOfTable - 1; i > 0; i--)
+		for (int j = i + 1; j < anArray.size(); j++)
 		{
-			table[i] = x % i;
+			if (anArray[i] > anArray[j])
-			x = 10 * table[i - 1] + x / i;
+				std::swap(anArray[i], anArray[j]);
 		}
-		output << x;
 	}
-	return output.str();
 }
 </code>
-Implanter la fonction et vérifier que celle-ci fonctionne correctement.
+Cet algorithme fonctionne uniquement pour des entiers. Nous nous proposons de transformer cette fonction afin qu’elle puisse aussi bien trier des entiers mais aussi des réels ou des complexes.
+===== Question n° 1=====
+Pour ce faire, nous concevons une classe « abstraite » ayant comme nom « Base » qui expose les fonctions nécessaires à l’écriture de l’algorithme de tri.
+Nous souhaitons utiliser l’algorithme avec la signature suivante :
+<code cpp>
+void insertion_sort(std::vector<Base*>& anArray)
+</code>
+Quelles sont les méthodes virtuelles que la classe abstraite doit exposer ?
 <hidden Correction>
+La classe doit exposée une méthode permettant de déterminer si un élément est plus grand que l'autre. Il peut s'agit soit d'une méthode testant si un élément est plus grand que l'autre :
 <code cpp>
-#include<sstream>
+class Base
-#include<iostream>
+{
+public:
+    virtual bool isGreater(const Base&) const = 0;
+        // Retourne true si l'objet courant est plus grand.
+    ...
+};
+</code>
-std::string computeE(int numberOfDigits)
+Nous pouvons ajouter éventuellement des méthodes complémentaires comme :
+<code cpp>
+    virtual bool isGreaterOrEqual(const Base&) const = 0;
+    virtual bool isLess(const Base&) const = 0;
+    virtual bool isLessOrEqual(const Base&) const = 0;
+    virtual bool isEqual(const Base&) const = 0;
+    virtual bool isNotEqual(const Base&) const = 0;
+</code>
+Voire éventuellement une fonction ''compareTo'':
+<code cpp>
+    virtual int compareTo(const Base&) const = 0;
+       // retourne -1 si l'instance courante est plus petite que l'instance passée en paramètre
+       // retourne 0 si elles sont égales
+       // retourne 1 si l'instance courante est plus grande que l'instance passée en paramètre.
+</code>
+</hidden>
+===== Question n° 2=====
+==== Question n° 2.1====
+Ajouter à la classe de base ''Base'' une méthode purement virtuelle ''print()'' qui affiche le contenu de la classe sur la console.
+<hidden Correction>
+Il suffit d'ajouter la méthode suivante:
+<code cpp>
+class Base
 {
-	int sizeOfTable = numberOfDigits + 9;
+    ...
-	int* table = (int*)_alloca(sizeOfTable * sizeof(numberOfDigits));
+public:
-	table[0] = 0;
+    ...
-	table[1] = 2;
+    virtual void print() const = 0;
-	for (int i = sizeOfTable - 1; i > 0; i--) {
-		table[i] = 1;
+}
-	}
+</code>
+</hidden>
-	std::ostringstream output;
+==== Question n° 2.2 ====
-	int x = 0;
-	table[1] = 2;
+Créer une fonction ''print(std::vector<Base*> anArray)'' qui prend un tableau en paramètre et affiche l’ensemble des éléments contenus dans le tableau sur la console.
-	for (; sizeOfTable > 9; sizeOfTable--)
-	{
-		for (int i = sizeOfTable - 1; i > 0; i--)
+<hidden Correction>
-		{
-			table[i] = x % i;
+Il suffit d'énumérer les éléments dans le tableau ou dans le containeur.
-			x = 10 * table[i - 1] + x / i;
-		}
+Nous pouvons faire une version orientée tableau qui ressemblera à cette version.
-		output << x;
-	}
+void print(std::vector<Base*> anArray)
-	return output.str();
+{
+    std::cout << "[";
+    int lastIndex = anArray.size()-1;
+    if(lastIndex >= 0)
+    {
+        for(int i = 0; i < lastIndex; i++)
+        {
+            anArray[i]->print();
+            std::cout << ", ";
+        }
+        anArray[lastIndex]->print();
+    }
+    std::cout << "]";
 }
-int main()
+Si nous souhaitons être un peu plus "C++" dans l'esprit, nous accéderons par des itérateurs.
+<code cpp>
+template<typename iterator>
+void print(iterator theStart, iterator theEnd)
 {
-	std::string value = computeE(100);
+    std::cout << "[";
-	std::cout << "e with " << 100 << " decimals\n" << value << std::endl;
+    if (theStart != theEnd)
+    {
+        *theStart->print();
+        theStart++;
+        while (theStart != theEnd)
+        {
+            std::cout << ", ";
+            *theStart->print();
+        }
+        std::cout << "]";
+    }
 }
 </code>
 </hidden>
-===== Question n°2 =====
-Nous constatons que calculer 10000 ou 20000 décimales de e, cela prend du temps. Nous souhaitons transformer cela en une fonction asynchrone à l’aide de la fonction [[http://en.cppreference.com/w/cpp/thread/async|std::async]].
+===== Question n° 3 =====
-Ecrire le code transformant la précédente fonction en une fonction asynchrone en utilisant la fonction [[http://en.cppreference.com/w/cpp/thread/async|std::async]].
+===== Question n° 3.1 ====
-Au lieu d'appeller directement la fonction  ''computeE'', nous appellons la fonction ''computeE'' au travers d'un appel à la fonction ''std::async'' qui va exécuter la fonction ''computeE'' de manière asynchone et retourner un objet de type ''std::future<string>'' qui va permettre de savoir si le résultat et disponible et aussi d'avoir la valeur du résultat quand celui-ci sera disponible.
+Créer une classe Entier qui dérive de la classe « abstraite » ''Base'' et qui contient un champ ''m_value'' ayant comme type le type ''int''.
 <hidden Correction>
+En plus de contenir le champ entier ''m_value'', la classe doit définir le constructeur par défaut, le constructeur de conversion d'une valeur de type ''int'' vers l'objet ''Entier'' ainsi que la conversion d'un objet ''Entier'' vers une valeur de type ''int''.
 <code cpp>
-void display(std::future<std::string>& aFutureValue, int theDecimals)
+class Entier : public Base
 {
-	aFutureValue.wait();
+private:
-	std::cout << "e with " << theDecimals << " decimals\n" << aFutureValue.get() << std::endl;
+    int m_value;
+public:
+    Entier() : m_value(0) {}
+    Entier(int aValue): m_value(aValue) {}
+    operator int() { return m_value; }
+    void print() const { std::cout << m_value; }
+    bool isGreater(const Base& unEntier) const
+    {
+        return m_value > dynamic_cast<const Entier&>(unEntier).m_value;
+    }
+};
+</code>
+En plus, il faut définir les fonctions ''print'' et ''isGreater''. La fonction ''print'' se contente d'afficher le contenu de l'entier sur la console, la fonction ''isGreater'' est plus complexe. En effet, l'argument a comme type un type ''Base'' et non pas un type ''Entier''. Il va falloir convertir ce type vers un type ''Entier'' qui est un type hérité, c'est pour cela que nous faisons un ''dynamic_cast<const Entier&>(unEntier)'' qui va essayer de convertir si le paramètre ''unEntier'' hérite bien de ''Entier'' ou est un ''Entier''. Sinon, un exception ''std::bad_cast'' sera lancé si la conversion n'est pas possible.
+</hidden>
+==== Question n° 3.2 ====
+Créer une fonction qui crée un tableau de ''theNumberOfValues'' entiers de type Entier
+<code cpp>
+std::vector<Base*> create_integer_array(
+	size_t theNumberOfValues)
+</code>
+qui crée un tableau de ''theNumberOfValues'' valeurs commençant par la valeur ''0'' et se terminant à la valeur ''theNumberOfValues-1''.
+<hidden Correction>
+<code cpp>
+std::vector<Base*> create_integer_array(size_t theNumberOfValues)
+{
+    std::vector<Base*> result;
+    result.resize(theNumberOfValues);
+    for (int i = 0; i < theNumberOfValues; i++)
+        result[i] = new Entier(i);
+    return result;
 }
+</code>
-int main()
+</hidden>
+==== Question n° 3.3 ====
+Créer une fonction qui crée un tableau de ''theNumberOfValues'' entiers de type ''Entier'' dont les éléments sont des nombres aléatoires compris entre ''theMinValue'' et ''theMaxValue''.
+Cette fonction peut s’implanter comme suit.
+<code cpp>
+std::vector<Base*> create_random_integer_array(
+	size_t theNumberOfValues, int theMinValue, int theMaxValue)
 {
-	std::future<std::string> eWidth20000 = std::async(std::launch::async, &computeE, 20000);
+	std::random_device rd;
-	std::future<std::string> eWidth100000 = std::async(std::launch::async, &computeE, 100000);
+	std::mt19937 gen(rd());
-	display(eWidth20000, 20000);
+	std::uniform_int_distribution<> distr(theMinValue, theMaxValue);
-	display(eWidth100000, 100000);
+	std::vector<Base*> array(theNumberOfValues);
+	for (size_t i = 0; i < theNumberOfValues; i++)
+		array[i] = new Entier(distr(gen));
+	return array;
 }
 </code>
+<hidden Correction>
+La fonction initialise un générateur de nombre aléatoire ainsi qu'une distribution uniforme
+pour des entiers entre ''theMinValue'' et ''theMaxValue''. Elle utilise ensuite ce générateur
+couplé à la distribution pour initialiser les ''theNumberOfValues'' éléments du tableau.
 </hidden>
+===== Question n°4 =====
+Modifier la fonction de tri ''insertion_sort(std::vector<int>& anArray)'' afin de ne plus travailler sur des entiers mais sur des objets dérivant de la classe « abstraite » ''Base'' :
+<code cpp>
+void insertion_sort(std::vector<Base*>& anArray)
+</code>
+Tester la fonction avec le tableau d’entiers que vous avez créé à la question n°3.3.
+<hidden Correction>
+La seule ligne à modifier est relative à la comparaison, au lieu d'utiliser l'opérateur de comparaison ''>'', nous
+faisons un appel à la méthode ''isGreater'', ce qui donne le code suivant :
+<code cpp>
+void insertion_sort(std::vector<Base*>& anArray)
+{
+    for (int i = 0; i < anArray.size(); i++)
+    {
+        for (int j = i + 1; j < anArray.size(); j++)
+        {
+            if (anArray[i]->isGreater(*anArray[j]))
+                std::swap(anArray[i], anArray[j]);
+        }
+    }
+}
+</code>
+Pour tester, nous allons écrire la fonction suivante :
+<code cpp>
+void testTriEntier()
+{
+	std::vector<Base*> entiers = create_random_integer_array(10, -100, 100);
+	print(entiers);
+	std::cout << std::endl;
+	insertion_sort(entiers);
+	print(entiers);
+	std::cout << std::endl;
+}
+</code>
+</hidden>
+===== Question n° 5 =====
+Nous souhaitons étendre le code à une classe de réel.
+==== Question n° 5.1 ====
+Ecrire une nouvelles classe ''Reel'' qui dérive de ''Base'' et qui contient un champ  ''m_value'' de type ''double''.
+==== Question n° 5.2 ====
+Créer une fonction qui crée un tableau de ''theNumberOfValues'' objets de type ''Reel'' dont les éléments sont des nombres aléatoires compris entre ''theMinValue'' et ''theMaxValue''.
+Cette fonction peut s’implanter comme suit.
+<code cpp>
+std::vector<Base*> create_random_double_array(
+	size_t theNumberOfValues, double theMinValue, double theMaxValue)
+{
+	std::random_device rd;
+	std::mt19937 gen(rd());
+	std::uniform_real_distribution<> distr(theMinValue, theMaxValue);
+	std::vector<Base*> array(theNumberOfValues);
+	for (size_t i = 0; i < theNumberOfValues; i++)
+		array[i] = new Reel(distr(gen));
+	return array;
+}
+</code>
+Vérifier que l’algorithme de tri fonctionne aussi pour cette nouvelle nouvelle classe.
+<hidden Correction>
+Par analogie à la classe ''Entier'', nous créons la classe réel comme suit :
+<code cpp>
+class Reel : public Base
+{
+private:
+    double m_value;
+public:
+    Reel() : m_value(0) {}
+    Reel(double aValue) : m_value(aValue) {}
+    operator double() { return m_value; }
+    void print() const { std::cout << m_value; }
+    bool isGreater(const Base& unReel) const
+    {
+        return m_value > dynamic_cast<const Reel&>(unReel).m_value;
+    }
+};
+</code>
+Pour tester, nous utiliserons une fonction similaire à la fonction suivante:
+<code cpp>
+void testTriReel()
+{
+	std::vector<Base*> reels = create_random_double_array(10, -1, 1);
+	print(reels);
+	std::cout << std::endl;
+	insertion_sort(reels);
+	print(reels);
+	std::cout << std::endl;
+}
+</code>
+</hidden>
-=====  Question n°3 =====
-Lancer deux calculs asynchrones, l’un calculant les 1000 premières décimales, l’autre les 10000 premières décimales et affichés les résultats dès que ceux-ci sont disponibles.

Cours

User Tools

Site Tools

Differences

Page Tools