| Séances
IFT611/729 |
Contenu
IFT611/729 |
Séances INF749 |
Contenu INF749 |
| S00 –
IFT611/729, 9 janvier |
Le mots de la semaine : introduction,
vocabulaire et bases. On s'entend sur
quelques termes et façons de faire qui nous suivront toute la session Au menu :
- Présentation du plan de cours
- Présentation du projet de session
et de quelques exemples tirés
de sessions antérieures
- Mise en place de certains éléments de vocabulaire, au sens pertinent
pour ce cours :
- Synchrone (sens faible)
- Synchrone (sens strict)
- Asynchrone
- Bloquant
- Non-bloquant
- Temps réel
- Contraintes de temps réel (CRIB :
constant, régulier, immédiat, bref)
- Discussion sur la distinction importante entre programmes en temps
réel et programmes rapides, du moins dans le cas des STR stricts, et sur les nuances dans le discours quant à la
question même de l'idée de temps réel, qui porte plusieurs
sens, affectant différemment les gens en fonction de leur domaine
d'expertise et de leur milieu de travail. Le tout dans le but de situer les un(e)s et les autres quant au contenu du
cours et quant au projet de session
qui vous est proposé
- Présentation du cours et des approches choisies pour y traiter des
sujets qui nous y tiennent à coeur
- Bref aparté sur la part du technique, la part du conceptuel et
l'organisation du cours
- Bref tableau de façons
de faire que nous utiliserons dans les exemples proposés en classe
et dans les notes de cours. Ceci inclut des exemples utilisant entre autres des foncteurs,
de la généricité par des
templates,
un algorithme standard (for_each()) et,
pour le plaisir, une
λ-expression
- Bref
comparatif de programmes bloquant et non-bloquant
- Bref
comparatif de programmes avec tâche s'exécutant à rythme régulier et à
rythme constant
Petit complément : j'ai rédigé
un petit comparatif de « performances » pour certaines opérations types
applicables à un tableau brut, alloué dynamiquement, et
à un vecteur standard.
Il s'avère que, lorsqu'il est bien utilisé,
le vecteur est presque toujours aussi rapide – ou plus rapide! –
que son substrat, le tableau brut, parce que le code sous-jacent est extrêmement
sophistiqué et parce que nous, programmeurs de tous les jours, ne prenons pas chaque fois le soin de manipuler nos tableaux comme le font en tout temps les concepteurs du vecteur standard.
Le dire, bien sûr, c'est une chose, mais le démontrer,
c'est mieux, alors jetez un coup d'oeil à ../../Sources/comparatif_vecteur_tableau.html si vous êtes intéressé(e).
De même, si vous êtes curieuse / curieux de comparer la vitesse à
l'exécution d'une fonction et d'un foncteur
à tâche équivalente, voir
../../Sources/Comparaison-Fonctions-Foncteurs.html
Dans les notes de cours, vous trouverez de la matière
en lien avec cette séance dans STR – Volume 00 (vocabulaire, donc les pages ≈5..35).
Truc important : bien que je ne l'aie pas mentionné
explicitement pendant la séance, ce cours mettra l'accent sur plusieurs
facettes de la conception et du développement de STR, dont :
- Le respect en tout temps des contraintes fixées
a priori. Nous en avons
discuté quelque peu en classe (itérer à rythme régulier ou constant,
s'exécuter de manière brève, démarrer immédiatement – faible latence)
- La
résilience. Un STR étant fréquemment un
système dont dépend l'intégrité des gens et du matériel, sa
résilience
tend à être une caractéristique plus que souhaitable
- La frugalité. Étant souvent destinés à opérer des systèmes embarqués ou
à s'exécuter sur du matériel plus... humble, mais aux caractéristiques
d'exécution plus prévisibles que ne le sont celles du matériel très
sophistiqué mis à notre disposition aujourd'hui, il n'est pas rare
qu'un STR doive occuper un espace réduit en mémoire
Ne vous étonnez donc pas de voir ces thématiques apparaître de manière
récurrente dans notre discours.
Le code écrit durant cette séance était :
//#include <iostream>
//#include <fstream>
//#include <algorithm>
//#include <vector>
//#include <list>
//#include <iterator>
//#include <random>
//using namespace std;
//
//int main() {
// vector<int> v{ 2,3,5,7,11,13,17,19,23,29 };
// auto pos = find(begin(v), end(v), 11);
// if (pos != end(v))
// cout << "Trouve a la position " << distance(begin(v), pos) << '\n';
// else
// cout << "Introuvable...\n";
// mt19937 prng{ random_device{}() };
// shuffle(begin(v), end(v), prng);
// for (int n : v)
// cout << n << ' ';
// cout << '\n';
// pos = find(begin(v), end(v), 11);
// if (pos != end(v))
// cout << "Trouve a la position " << distance(begin(v), pos) << '\n';
// else
// cout << "Introuvable...\n";
//}
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <list>
#include <iterator>
using namespace std;
// you shall not pay for what you do not use
// there shall be no room for a lower-level language
void aff(int n) {
cout << n << ' ';
}
class Aff {
ostream &os;
public:
Aff(ostream &os) : os{ os } {
}
template <class T>
void operator()(const T &obj) const {
os << obj << ' ';
}
};
int main() {
int tab[]{ 2,3,5,7,11,13,17,19,23,29 };
list<double> v{ -1.5, -2.5, -3.5, -4.5, -5.5 };
//for (int i = 0; i != N; ++i)
// cout << tab[i] << ' ';
//for (auto p = tab + 0; p != tab + N; ++p)
// aff(*p);
// It est int*
// Op est void(*)(int)
for_each(begin(tab), end(tab), aff); // [deb, fin)
cout << '\n';
// It est int*
// Op est Aff
for_each(begin(tab), end(tab), Aff{ cout });
cout << '\n';
/*
struct XXXX {
void operator()(int n) const { cout << n << ' '; }
} xxxx;
*/
for_each(begin(tab), end(tab), [](int n) { cout << n << ' '; });
cout << '\n';
// It est vector<int>::iterator
// Op est Aff
for_each(begin(v), end(v), Aff{ cout });
ofstream out{ "out.txt" };
auto afficher = [&out](const auto &x) { out << x << ' '; };
for_each(begin(tab), end(tab), afficher/*Aff{ out }*/);
out << '\n';
/*
struct YYYY {
ofstream &out;
YYYY(ofstream &out) : out { out } {
}
void operator()(int n) const {
out << n << ' ';
}
} yyyy;
*/
for_each(begin(tab), end(tab), [&out](int n) { out << n << ' '; });
/*
template <class It, class Op>
Op for_each(It deb, It fin, Op oper) {
for(; deb != fin; ++deb)
oper(*deb);
return oper;
}
*/
}
|
S00 – INF749,
6 janvier |
Le mots de la semaine : introduction,
vocabulaire et bases. On s'entend sur
quelques termes et façons de faire qui nous suivront toute la session Au menu :
- Présentation du plan de cours
- Présentation du projet de session
et de quelques exemples tirés
de sessions antérieures
- Mise en place de certains éléments de vocabulaire, au sens pertinent
pour ce cours :
- Synchrone (sens faible)
- Synchrone (sens strict)
- Asynchrone
- Bloquant
- Non-bloquant
- Temps réel
- Contraintes de temps réel (CRIB :
constant, régulier, immédiat, bref)
- Discussion sur la distinction importante entre programmes en temps
réel et programmes rapides, du moins dans le cas des STR stricts, et sur les nuances dans le discours quant à la
question même de l'idée de temps réel, qui porte plusieurs
sens, affectant différemment les gens en fonction de leur domaine
d'expertise et de leur milieu de travail. Le tout dans le but de situer les un(e)s et les autres quant au contenu du
cours et quant au projet de session
qui vous est proposé
- Présentation du cours et des approches choisies pour y traiter des
sujets qui nous y tiennent à coeur
- Bref aparté sur la part du technique, la part du conceptuel et
l'organisation du cours
- Bref tableau de façons
de faire que nous utiliserons dans les exemples proposés en classe
et dans les notes de cours. Ceci inclut des exemples utilisant entre autres des foncteurs,
de la généricité par des
templates,
un algorithme standard (for_each()) et,
pour le plaisir, une
λ-expression
- Bref
comparatif de programmes bloquant et non-bloquant
- Bref
comparatif de programmes avec tâche s'exécutant à rythme régulier et à
rythme constant
Petit complément : j'ai rédigé
un petit comparatif de « performances » pour certaines opérations types
applicables à un tableau brut, alloué dynamiquement, et
à un vecteur standard.
Il s'avère que, lorsqu'il est bien utilisé,
le vecteur est presque toujours aussi rapide – ou plus rapide! –
que son substrat, le tableau brut, parce que le code sous-jacent est extrêmement
sophistiqué et parce que nous, programmeurs de tous les jours, ne prenons pas chaque fois le soin de manipuler nos tableaux comme le font en tout temps les concepteurs du vecteur standard.
Le dire, bien sûr, c'est une chose, mais le démontrer,
c'est mieux, alors jetez un coup d'oeil à ../../Sources/comparatif_vecteur_tableau.html si vous êtes intéressé(e).
De même, si vous êtes curieuse / curieux de comparer la vitesse à
l'exécution d'une fonction et d'un foncteur
à tâche équivalente, voir
../../Sources/Comparaison-Fonctions-Foncteurs.html
Dans les notes de cours, vous trouverez de la matière
en lien avec cette séance dans STR – Volume 00 (vocabulaire, donc les pages ≈5..35).
Truc important : bien que je ne l'aie pas mentionné
explicitement pendant la séance, ce cours mettra l'accent sur plusieurs
facettes de la conception et du développement de STR, dont :
- Le respect en tout temps des contraintes fixées
a priori. Nous en avons
discuté quelque peu en classe (itérer à rythme régulier ou constant,
s'exécuter de manière brève, démarrer immédiatement – faible latence)
- La
résilience. Un STR étant fréquemment un
système dont dépend l'intégrité des gens et du matériel, sa
résilience
tend à être une caractéristique plus que souhaitable
- La frugalité. Étant souvent destinés à opérer des systèmes embarqués ou
à s'exécuter sur du matériel plus... humble, mais aux caractéristiques
d'exécution plus prévisibles que ne le sont celles du matériel très
sophistiqué mis à notre disposition aujourd'hui, il n'est pas rare
qu'un STR doive occuper un espace réduit en mémoire
Ne vous étonnez donc pas de voir ces thématiques apparaître de manière
récurrente dans notre discours.
Le code écrit durant cette séance était :
#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
#include <random>
using namespace std;
int main() {
vector<int> v{ 2,3,5,7,11,13,17,19,23,29 };
auto pos = find(begin(v), end(v), 11);
if (pos != end(v))
cout << "Trouve a la position " << distance(begin(v), pos) << '\n';
else
cout << "Introuvable\n";
mt19937 prng{ random_device{}() }; // magie pour cette semaine
shuffle(begin(v), end(v), prng);
for (int n : v) cout << n << ' ';
cout << '\n';
pos = find(begin(v), end(v), 11);
if (pos != end(v))
cout << "Trouve a la position " << distance(begin(v), pos) << '\n';
else
cout << "Introuvable\n";
}
//#include <iostream>
//#include <algorithm>
//#include <vector>
//#include <iterator>
//#include <fstream>
//#include <list>
//using namespace std;
//// You don't pay for what you don't use
//// There shall be no room for a lower-level language
//void aff(int n) {
// cout << n << ' ';
//}
//class Aff {
// ostream &os;
//public:
// Aff(ostream& os) : os{ os } {
// }
// template <class T>
// void operator()(const T &x) const {
// os << x << ' ';
// }
//};
//int main() {
// int tab[]{ 2,3,5,7,11,13,17,19,23,29 };
// list<double> v{ -1.5,-2.5,-3.5,-4.5,-5.5 };
// //for (int i = 0; i != N; ++i)
// // cout << tab[i] << ' ';
// //for (auto p = tab + 0; p != tab + N; ++p)
// // aff(*p);
//
// // It : int*
// // Op : void (*)(int)
// for_each(begin(tab), end(tab), aff);
// cout << '\n';
// // It : int*
// // Op : Aff
// // for_each(begin(tab), end(tab), Aff{ cout });
//
// /*
//
// struct XXXX {
// void operator()(int n) const { cout << n << ' '; }
// } xxxx;
//
// */
// for_each(begin(tab), end(tab), [](int n) { cout << n << ' '; });
// cout << '\n';
// // It : vector<int>::iterator
// // Op : Aff
// for_each(begin(v), end(v), Aff{ cout });
// ofstream out{ "out.txt" };
//
// // for_each(begin(v), end(v), Aff{ out });
// /*
//
// struct YYYY {
// ofstream &out;
// YYYY(ofstream &out) : out{ out } {
// }
// void operator()(double x) const {
// out << x << ' ';
// }
// } yyyy{ out };
// */
// for_each(begin(v), end(v), [&out](double x) { out << x << ' '; });
//
// auto afficher = [&out](const auto &x) { cout << x << ' '; };
// for_each(begin(v), end(v), afficher);
//
//}
///*
//
//template <class It, class Op>
// Op for_each(It deb, It fin, Op oper) {
// for(; deb != fin; ++deb)
// oper(*deb);
// return oper;
// }
//
//*/
|
| S01 –
IFT611/729, 16 janvier |
Le mots de la semaine : saines
pratiques et hygiène de programmation. On
établit des façons de faire, et on examine les nuances entre copie
(complexité typiquement linéaire, temps souvent indéterministe) et
mouvement (complexité typiquement constante, temps souvent déterministe),
tout en introduisant quelques
idiomes fort utiles. Au menu, d'une manière teintée par notre besoin d'avoir
une approche appropriée pour le développement de STR :
Mise en place d'un premier conteneur (un tableau d'entiers)
implémenté selon les conventions du langage C++,
en portant une attention particulière aux considérations de robustesse et
d'efficacité, incluant :
- Quelques
types internes et publics
- Quelques méthodes clés (size(),
empty(), capacity())
- Les accès aux itérateurs (begin() et
end(), en déclinaison const et non-const; cbegin()
et cend())
- Quelques constructeurs (défaut, paramétrique, copie)
- L'affectation (de copie) et
l'idiome d'affectation sécuritaire
- Le destructeur
-
L'opérateur [] dans ses déclinaisons
const et non-const
-
La méthode push_back() et
l'implémentation d'un algorithme de croissance (qui reste à faire)
-
Opérateurs d'égalité (==,
!=)
Munis des idées et techniques mises de l'avant dans cette séance,
vous devriez être en mesure de comprendre les exemples dans STR – Volume 01 (voir le code des cas sous étude).
Profitez de l'opportunité pour expérimenter avec ces propositions
de tests, pour les modifier, pour essayer de comprendre les métriques
que vous parviendrez à en tirer, etc.
Le code utilisé pour la classe Tableau suit
(notez que nous discuterons de
grow() à la séance
S02) :
#include <cstddef> // pour std::size_t
#include <algorithm>
class Tableau {
public:
using value_type = int;
using size_type = std::size_t;
using pointer = value_type*;
using const_pointer = const value_type*;
using reference = value_type&;
using const_reference = const value_type&;
private:
pointer elems {};
size_type nelems {},
cap {};
public:
[[nodiscard]] size_type size() const noexcept {
return nelems;
}
[[nodiscard]] size_type capacity() const noexcept {
return cap;
}
[[nodiscard]] bool empty() const noexcept {
return !size();
}
private:
[[nodiscard]] bool full() const noexcept {
return size() == capacity();
}
public:
using iterator = pointer;
using const_iterator = const_pointer;
[[nodiscard]] iterator begin() noexcept {
return elems;
}
[[nodiscard]] const_iterator begin() const noexcept {
return elems;
}
[[nodiscard]] const_iterator cbegin() const noexcept {
return begin();
}
[[nodiscard]] iterator end() noexcept {
return begin() + size();
}
[[nodiscard]] const_iterator end() const noexcept {
return begin() + size();
}
[[nodiscard]] const_iterator cend() const noexcept {
return end();
}
Tableau() = default;
Tableau(size_type n, const_reference init)
: elems{ new value_type[n] }, nelems{ n }, cap{ n } {
std::fill(begin(), end(), init);
}
Tableau(const Tableau &autre)
: elems{ new value_type[autre.size()] },
nelems{ autre.size() }, cap{ autre.size() } {
std::copy(autre.begin(), autre.end(), begin());
}
~Tableau() {
delete [] elems;
}
void swap(Tableau &autre) noexcept {
using std::swap;
swap(elems, autre.elems);
swap(nelems, autre.nelems);
swap(cap, autre.cap);
}
Tableau& operator=(const Tableau &autre) {
Tableau{ autre }.swap(*this);
return *this;
}
// ...
reference operator[](size_type n) noexcept {
return elems[n];
}
const_reference operator[](size_type n) const noexcept {
return elems[n];
}
void push_back(const_reference val) {
if (full()) grow();
elems[size()] = val;
++nelems;
}
private:
void grow() {
const size_type new_cap = capacity()? capacity() * 2 : 64; // hum
auto p = new value_type[new_cap];
std::copy(begin(), end(), p);
delete[] elems;
cap = new_cap;
elems = p;
}
};
Dans les notes de cours, comme mentionné dans
le paragraphe précédent, vous trouverez de la matière
en lien avec cette séance dans STR – Volume 01.
|
S01 – INF749,
13 janvier |
Le mots de la semaine : saines
pratiques et hygiène de programmation. On
établit des façons de faire, et on examine les nuances entre copie
(complexité typiquement linéaire, temps souvent indéterministe) et
mouvement (complexité typiquement constante, temps souvent déterministe),
tout en introduisant quelques
idiomes fort utiles. Au menu, d'une manière teintée par notre besoin d'avoir
une approche appropriée pour le développement de STR :
Mise en place d'un premier conteneur (un tableau d'entiers)
implémenté selon les conventions du langage C++,
en portant une attention particulière aux considérations de robustesse et
d'efficacité, incluant :
- Quelques
types internes et publics
- Quelques méthodes clés (size(),
empty(), capacity())
- Les accès aux itérateurs (begin() et
end(), en déclinaison const et non-const; cbegin()
et cend())
- Quelques constructeurs (défaut, paramétrique, copie)
- L'affectation (de copie) et
l'idiome d'affectation sécuritaire
- Le destructeur
-
L'opérateur [] dans ses déclinaisons
const et non-const
-
La méthode push_back() et
l'implémentation d'un algorithme de croissance (qui reste à faire)
-
Opérateurs d'égalité (==,
!=)
Munis des idées et techniques mises de l'avant dans cette séance,
vous devriez être en mesure de comprendre les exemples dans STR – Volume 01 (voir le code des cas sous étude).
Profitez de l'opportunité pour expérimenter avec ces propositions
de tests, pour les modifier, pour essayer de comprendre les métriques
que vous parviendrez à en tirer, etc.
Le code utilisé pour la classe Tableau suit
(notez que nous discuterons de
grow() à la séance
S02) :
#include <cstddef> // pour std::size_t
#include <algorithm>
class Tableau {
public:
using value_type = int;
using size_type = std::size_t;
using pointer = value_type*;
using const_pointer = const value_type*;
using reference = value_type&;
using const_reference = const value_type&;
private:
pointer elems {};
size_type nelems {},
cap {};
public:
[[nodiscard]] size_type size() const noexcept {
return nelems;
}
[[nodiscard]] size_type capacity() const noexcept {
return cap;
}
[[nodiscard]] bool empty() const noexcept {
return !size();
}
private:
[[nodiscard]] bool full() const noexcept {
return size() == capacity();
}
public:
using iterator = pointer;
using const_iterator = const_pointer;
[[nodiscard]] iterator begin() noexcept {
return elems;
}
[[nodiscard]] const_iterator begin() const noexcept {
return elems;
}
[[nodiscard]] const_iterator cbegin() const noexcept {
return begin();
}
[[nodiscard]] iterator end() noexcept {
return begin() + size();
}
[[nodiscard]] const_iterator end() const noexcept {
return begin() + size();
}
[[nodiscard]] const_iterator cend() const noexcept {
return end();
}
Tableau() = default;
Tableau(size_type n, const_reference init)
: elems{ new value_type[n] }, nelems{ n }, cap{ n } {
std::fill(begin(), end(), init);
}
Tableau(const Tableau &autre)
: elems{ new value_type[autre.size()] },
nelems{ autre.size() }, cap{ autre.size() } {
std::copy(autre.begin(), autre.end(), begin());
}
~Tableau() {
delete [] elems;
}
void swap(Tableau &autre) noexcept {
using std::swap;
swap(elems, autre.elems);
swap(nelems, autre.nelems);
swap(cap, autre.cap);
}
Tableau& operator=(const Tableau &autre) {
Tableau{ autre }.swap(*this);
return *this;
}
// ...
reference operator[](size_type n) noexcept {
return elems[n];
}
const_reference operator[](size_type n) const noexcept {
return elems[n];
}
void push_back(const_reference val) {
if (full()) grow();
elems[size()] = val;
++nelems;
}
private:
void grow() {
const size_type new_cap = capacity()? capacity() * 2 : 64; // hum
auto p = new value_type[new_cap];
std::copy(begin(), end(), p);
delete[] elems;
cap = new_cap;
elems = p;
}
};
Dans les notes de cours, comme mentionné dans
le paragraphe précédent, vous trouverez de la matière
en lien avec cette séance dans STR – Volume 01.
|
|
S02 – IFT611/729,
23 janvier |
Le mots de la semaine :
sélection à coût nul d'algorithmes. Premier contact avec les traits
et leurs applications. Au menu :
La classe Tableau avec constructeur et
affectation de mouvement suit, et il en va de même pour le test qui met
en relief l'impact du
mouvement sur la vitesse d'un programme :
#include <cstddef> // pour std::size_t
#include <algorithm>
class Tableau {
public:
using value_type = int;
using size_type = std::size_t;
using pointer = value_type*;
using const_pointer = const value_type*;
using reference = value_type&;
using const_reference = const value_type&;
private:
pointer elems {};
size_type nelems {},
cap {};
public:
[[nodiscard]] size_type size() const noexcept {
return nelems;
}
[[nodiscard]] size_type capacity() const noexcept {
return cap;
}
[[nodiscard]] bool empty() const noexcept {
return !size();
}
private:
[[nodiscard]] bool full() const noexcept {
return size() == capacity();
}
public:
using iterator = pointer;
using const_iterator = const_pointer;
[[nodiscard]] iterator begin() noexcept {
return elems;
}
[[nodiscard]] const_iterator begin() const noexcept {
return elems;
}
[[nodiscard]] const_iterator cbegin() const noexcept {
return begin();
}
[[nodiscard]] iterator end() noexcept {
return begin() + size();
}
[[nodiscard]] const_iterator end() const noexcept {
return begin() + size();
}
[[nodiscard]] const_iterator cend() const noexcept {
return end();
}
Tableau() = default;
Tableau(size_type n, const_reference init)
: cap{ n }, nelems{ n }, elems{ new value_type[n] } {
std::fill(begin(), end(), init);
}
Tableau(const Tableau &autre)
: elems{ new value_type[autre.size()] },
nelems{ autre.size() }, cap{ autre.size() } {
std::copy(autre.begin(), autre.end(), begin());
}
~Tableau() {
delete [] elems;
}
void swap(Tableau &autre) noexcept {
using std::swap;
swap(elems, autre.elems);
swap(nelems, autre.nelems);
swap(cap, autre.cap);
}
Tableau& operator=(const Tableau &autre) {
Tableau{ autre }.swap(*this);
return *this;
}
Tableau(Tableau &&autre) noexcept
: elems{ std::exchange(autre.elems, nullptr) },
nelems{ std::exchange(autre.nelems, 0) },
cap{ std::exchange(autre.cap, 0) } {
}
Tableau& operator=(Tableau &&autre) noexcept {
Tableau{ std::move(autre) }.swap(*this);
return *this;
}
reference operator[](size_type n) noexcept {
return elems[n];
}
const_reference operator[](size_type n) const noexcept {
return elems[n];
}
void push_back(const_reference val) {
if (full()) grow();
elems[size()] = val;
++nelems;
}
private:
void grow() {
const size_type new_cap = capacity()? capacity() * 2 : 128;
auto p = new value_type[new_cap];
std::copy(begin(), end(), p);
delete[] elems;
cap = new_cap;
elems = p;
}
public:
bool operator==(const Tableau &autre) const noexcept {
return size() == autre.size() &&
std::equal(begin(), end(), autre.begin());
}
bool operator!=(const Tableau &autre) const noexcept {
return !(*this == autre);
}
};
#include <vector>
#include <numeric>
#include <chrono>
#include <iostream>
#include <utility>
using namespace std;
using namespace std::chrono;
template <class F, class ... Args>
auto tester(F f, Args &&... args) {
auto pre = high_resolution_clock::now();
auto res = f(std::forward<Args>(args)...);
auto post = high_resolution_clock::now();
return pair{ res, post - pre };
}
vector<double> f(vector<double> v) {
transform(begin(v), end(v), begin(v), [](double x) { return sqrt(x); });
return v;
}
void g(vector<double> &v) {
transform(begin(v), end(v), begin(v), [](double x) { return sqrt(x); });
}
int main() {
enum { N = 10'000'000 };
vector<double> v(N);
iota(begin(v), end(v), 1.0);
auto [r0,dt0] = tester([v]() mutable {
v = f(v);
return v.back();
});
auto [r1,dt1] = tester([v]() mutable {
g(v);
return v.back();
});
auto [r2,dt2] = tester([v]() mutable {
v = f(std::move(v));
return v.back();
});
cout << "v = f(v) : " << duration_cast<microseconds>(dt0)
<< endl;
cout << "g(v) : " << duration_cast<microseconds>(dt1)
<< endl;
cout << "v = f(std::move(v)) : " << duration_cast<microseconds>(dt2)
<< endl;
}
Notez que notre examen d'implémentations génériques d'un tableau
suivra sous peu; nous avons quelques menus détails à explorer auparavant. Dans les notes de cours, vous trouverez de la matière
en lien avec cette séance dans STR
– Volume 00,
annexes 00 et 01,
mais vous en trouverez surtout dans les liens ci-dessus.
|
S02 – INF749,
20 janvier |
Le mots de la semaine :
sélection à coût nul d'algorithmes. Premier contact avec les traits
et leurs applications. Au menu :
La classe Tableau avec constructeur et
affectation de mouvement suit, et il en va de même pour le test qui met
en relief l'impact du
mouvement sur la vitesse d'un programme :
#include <cstddef> // pour std::size_t
#include <algorithm>
class Tableau {
public:
using value_type = int;
using size_type = std::size_t;
using pointer = value_type*;
using const_pointer = const value_type*;
using reference = value_type&;
using const_reference = const value_type&;
private:
pointer elems {};
size_type nelems {},
cap {};
public:
[[nodiscard]] size_type size() const noexcept {
return nelems;
}
[[nodiscard]] size_type capacity() const noexcept {
return cap;
}
[[nodiscard]] bool empty() const noexcept {
return !size();
}
private:
[[nodiscard]] bool full() const noexcept {
return size() == capacity();
}
public:
using iterator = pointer;
using const_iterator = const_pointer;
[[nodiscard]] iterator begin() noexcept {
return elems;
}
[[nodiscard]] const_iterator begin() const noexcept {
return elems;
}
[[nodiscard]] const_iterator cbegin() const noexcept {
return begin();
}
[[nodiscard]] iterator end() noexcept {
return begin() + size();
}
[[nodiscard]] const_iterator end() const noexcept {
return begin() + size();
}
[[nodiscard]] const_iterator cend() const noexcept {
return end();
}
Tableau() = default;
Tableau(size_type n, const_reference init)
: cap{ n }, nelems{ n }, elems{ new value_type[n] } {
std::fill(begin(), end(), init);
}
Tableau(const Tableau &autre)
: elems{ new value_type[autre.size()] },
nelems{ autre.size() }, cap{ autre.size() } {
std::copy(autre.begin(), autre.end(), begin());
}
~Tableau() {
delete [] elems;
}
void swap(Tableau &autre) noexcept {
using std::swap;
swap(elems, autre.elems);
swap(nelems, autre.nelems);
swap(cap, autre.cap);
}
Tableau& operator=(const Tableau &autre) {
Tableau{ autre }.swap(*this);
return *this;
}
Tableau(Tableau &&autre) noexcept
: elems{ std::exchange(autre.elems, nullptr) },
nelems{ std::exchange(autre.nelems, 0) },
cap{ std::exchange(autre.cap, 0) } {
}
Tableau& operator=(Tableau &&autre) noexcept {
Tableau{ std::move(autre) }.swap(*this);
return *this;
}
reference operator[](size_type n) noexcept {
return elems[n];
}
const_reference operator[](size_type n) const noexcept {
return elems[n];
}
void push_back(const_reference val) {
if (full()) grow();
elems[size()] = val;
++nelems;
}
private:
void grow() {
const size_type new_cap = capacity()? capacity() * 2 : 128;
auto p = new value_type[new_cap];
std::copy(begin(), end(), p);
delete[] elems;
cap = new_cap;
elems = p;
}
public:
bool operator==(const Tableau &autre) const noexcept {
return size() == autre.size() &&
std::equal(begin(), end(), autre.begin());
}
bool operator!=(const Tableau &autre) const noexcept {
return !(*this == autre);
}
};
#include <vector>
#include <numeric>
#include <chrono>
#include <iostream>
#include <utility>
using namespace std;
using namespace std::chrono;
template <class F, class ... Args>
auto tester(F f, Args &&... args) {
auto pre = high_resolution_clock::now();
auto res = f(std::forward<Args>(args)...);
auto post = high_resolution_clock::now();
return pair{ res, post - pre };
}
vector<double> f(vector<double> v) {
transform(begin(v), end(v), begin(v), [](double x) { return sqrt(x); });
return v;
}
void g(vector<double> &v) {
transform(begin(v), end(v), begin(v), [](double x) { return sqrt(x); });
}
int main() {
enum { N = 10'000'000 };
vector<double> v(N);
iota(begin(v), end(v), 1.0);
auto [r0,dt0] = tester([v]() mutable {
v = f(v);
return v.back();
});
auto [r1,dt1] = tester([v]() mutable {
g(v);
return v.back();
});
auto [r2,dt2] = tester([v]() mutable {
v = f(std::move(v));
return v.back();
});
cout << "v = f(v) : " << duration_cast<microseconds>(dt0)
<< endl;
cout << "g(v) : " << duration_cast<microseconds>(dt1)
<< endl;
cout << "v = f(std::move(v)) : " << duration_cast<microseconds>(dt2)
<< endl;
}
Notez que notre examen d'implémentations génériques d'un tableau
suivra sous peu; nous avons quelques menus détails à explorer auparavant. Dans les notes de cours, vous trouverez de la matière
en lien avec cette séance dans STR
– Volume 00,
annexes 00 et 01,
mais vous en trouverez surtout dans les liens ci-dessus.
|
| S03 –
IFT611/729, 30 janvier |
Le mots de la semaine :
sélection à coût nul d'algorithmes et résilience.
Notre exploration des traits
et de leurs applications se poursuit; nous revenons sur le tableau
d'entiers pour en faire un tableau générique, et nous examinons les
conséquences de ce geste sur la résilience de notre code.
- Q01
- Bref retour sur Q00
- Quelques mots sur cette
optimisation qu'on
nomme le
Function Inlining et nuances quant aux capacités des
compilateurs
- Idée de qualité d'implémentation (Quality of Implementation,
QoI)
- Enjeux comme le Whole Program Optimization ou le Link Time Optimization
- Quelques mots sur les
concepts
- Quelques mots sur la préconstruction
- Petite excursion dans le monde des itérateurs : catégories,
opérations, forces, faiblesses, usages
- Poursuite de l'examen des itérateurs, en lien avec la fonction
distance()
- Poursuite de l'examen des itérateurs et des traits, en lien avec le
calcul de la moyenne
Dans les notes de cours, vous trouverez de la matière
en lien avec cette séance dans STR
– Volume 00,
annexes 00 et 01,
mais vous en trouverez surtout dans les liens ci-dessus.
La fonction
distance() est un cas
d'espèce intéressant, tiré du standard lui-même,
qui exploite les traits et les catégories pour réaliser
une optimisation presque obscène. J'aime bien faire le tour de
cette approche, qui peut être appliquée à bien d'autres
trucs, avec des gens qui, comme vous, doivent écrire des programmes
dont les performances sont sans compromis.
Les plus curieuses et les plus curieux remarqueront que les fonctions
advance(),
next()
et
prev()
appliquent les mêmes techniques d'optimisation que sa cousine
distance().
J'ai utilisé la technique du tag dispatching, mais il existe
d'autres techniques pour y arriver :
#include <iterator>
using namespace std; // bof
//
// j'ai appelé la fonction distance_ pour éviter les
// conflits de nom avec std::distance
//
template <class It>
auto distance_(It debut, It fin, forward_iterator_tag) {
typename iterator_traits<It>::difference_type n{};
for(; debut != fin; ++debut)
++n;
return n;
}
template <class It>
auto distance_(It debut, It fin, random_access_iterator_tag) {
return fin - debut;
}
template <class It>
auto distance_(It debut, It fin) {
return distance_(
debut, fin, typename iterator_traits<
It
>::iterator_category{}
);
}
On pourrait appliquer d'autres mécanismes, par exemple
std::nable_if ou des
concepts.
Dans ce cas bien précis, le recours à
if constexpr pourrait être moins plaisant,
du fait qu'il n'y a pas de « cas par défaut » alors la question de ce qui devrait faire partie du else final
se poserait (il faudrait probablement combler ce cas – l'escamoter, vraiment avec un
static_assert ou
quelque chose de semblable). C'est normal : il existe une diversité d'outils pour une diversité de cas d'utilisation, après tout.
N'oubliez pas de livrer L00
aujourd'hui! |
S03 – INF749,
27 janvier |
Le mots de la semaine :
sélection à coût nul d'algorithmes et résilience.
Notre exploration des traits
et de leurs applications se poursuit; nous revenons sur le tableau
d'entiers pour en faire un tableau générique, et nous examinons les
conséquences de ce geste sur la résilience de notre code.
- Q01
- Bref retour sur Q00
- Quelques mots sur cette
optimisation qu'on
nomme le
Function Inlining et nuances quant aux capacités des
compilateurs
- Idée de qualité d'implémentation (Quality of Implementation,
QoI)
- Enjeux comme le Whole Program Optimization ou le Link Time Optimization
- Quelques mots sur les
concepts
- Quelques mots sur la préconstruction
- Petite excursion dans le monde des itérateurs : catégories,
opérations, forces, faiblesses, usages
- Poursuite de l'examen des itérateurs, en lien avec la fonction
distance()
- Poursuite de l'examen des itérateurs et des traits, en lien avec le
calcul de la moyenne
Dans les notes de cours, vous trouverez de la matière
en lien avec cette séance dans STR
– Volume 00,
annexes 00 et 01,
mais vous en trouverez surtout dans les liens ci-dessus.
La fonction
distance() est un cas
d'espèce intéressant, tiré du standard lui-même,
qui exploite les traits et les catégories pour réaliser
une optimisation presque obscène. J'aime bien faire le tour de
cette approche, qui peut être appliquée à bien d'autres
trucs, avec des gens qui, comme vous, doivent écrire des programmes
dont les performances sont sans compromis.
Les plus curieuses et les plus curieux remarqueront que les fonctions
advance(),
next()
et
prev()
appliquent les mêmes techniques d'optimisation que sa cousine
distance().
J'ai utilisé la technique du tag dispatching, mais il existe
d'autres techniques pour y arriver :
#include <iterator>
using namespace std; // bof
//
// j'ai appelé la fonction distance_ pour éviter les
// conflits de nom avec std::distance
//
template <class It>
auto distance_(It debut, It fin, forward_iterator_tag) {
typename iterator_traits<It>::difference_type n{};
for(; debut != fin; ++debut)
++n;
return n;
}
template <class It>
auto distance_(It debut, It fin, random_access_iterator_tag) {
return fin - debut;
}
template <class It>
auto distance_(It debut, It fin) {
return distance_(
debut, fin, typename iterator_traits<
It
>::iterator_category{}
);
}
On pourrait appliquer d'autres mécanismes, par exemple
std::nable_if ou des
concepts.
Dans ce cas bien précis, le recours à
if constexpr pourrait être moins plaisant,
du fait qu'il n'y a pas de « cas par défaut » alors la question de ce qui devrait faire partie du else final
se poserait (il faudrait probablement combler ce cas – l'escamoter, vraiment avec un
static_assert ou
quelque chose de semblable). C'est normal : il existe une diversité d'outils pour une diversité de cas d'utilisation, après tout.
N'oubliez pas de livrer L00
aujourd'hui! |
| S04 –
IFT611/729, 6 février |
Au menu :
|
S04 – INF749,
3 février |
Au menu :
|
| S05 –
IFT611/729, 13 février |
Au menu :
|
S05 – INF749,
10 février |
Au menu :
|
| S06 –
IFT611/729, 20 février |
Au menu :
|
S06 – INF749,
17 février |
Au menu :
|
| 27
février |
Cours suspendus dans le but de faire place aux examens périodiques pour
les cours qui en tiennent
|
24 février |
Cours suspendus dans le but de faire place aux examens périodiques pour
les cours qui en tiennent
|
|
6 mars |
Relâche. Reposez-vous un peu, vous en avez sûrement
besoin!
|
3 mars |
Relâche. Reposez-vous un peu, vous en avez sûrement
besoin!
|
|
S07 – IFT611/729,
13 mars |
Au menu :
N'oubliez pas de remettre le livrable L01! Attention : exceptionnellement, séance en ligne par Teams |
S07 – INF749,
10 mars |
Au menu :
N'oubliez pas de remettre le livrable L01! |
|
S08 –
IFT611/729, 20 mars |
Au menu :
Attention : exceptionnellement, séance en ligne par Teams |
S08 – INF749,
17 mars |
Au menu :
|
| S09 –
IFT611/729, 27 mars |
Au menu :
Attention : exceptionnellement, séance en ligne par Teams |
S09 – INF749,
24 mars |
Au menu :
|
| 3 avril |
Vendredi Saint, congé universitaire
|
S10 – INF749,
31 mars |
Au menu :
|
| S10 –
IFT611/729,
10 avril |
Au menu :
|
S11 – INF749,
7 avril |
Au menu :
N'oubliez pas de remettre le livrable L02! |
|
S11 –
IFT611/729,
17 avril |
Au menu :
N'oubliez pas de remettre le livrable L02! |
S12 – INF749,
14 avril |
Chic examen final plein d'amour
|
|
S12 –
IFT611/729,
?? avril |
Chic examen final plein d'amour, de xx h xx à
xx h xx au
Dx-xxxx
|
|
|
Les sections qui suivent proposent du code ou des exemples proposés en
classe, le tout dans le but de vous permettre d'étudier la chose, de critiquer,
de commenter, de questionner et d'expérimenter à loisir. Notez que certains des
exemples ci-dessous doivent être retouchés à la lueur de l'évolution du langage
C++.
Un appareil de type « photo radar » a pour rôle de
détecter le mouvement d'un véhicule dans un espace contrôlé et, si la vitesse
de déplacement du véhicule en question dépasse un certain seuil, de provoquer
une capture d'image qui sera analysée pour détecter un ensemble de
caractéristiques (couleur, marque, symboles sur la plaque d'immatriculation,
etc.).
En bref, un capteur physique (le radar) saisit les mouvements d'objets dans un espace et les signale à un module d'analyse de première ligne capable de reconnaître un déplacement suspect et de provoquer une demande de capture d'image de la part d'une caméra à haute définition. Une fois l'image capturée, celle-ci est transmise à un module analytique qui en sortira les principales caractéristiques recherchées, puis les intégrera à une base de données. Ensuite, un module produisant des contraventions en fonction des besoins pourra, de manière automatique, faire son travail.
