Quand ne pas utiliser les algorithmes STL. Définir l'exemple

Camarades, bonsoir! Vous avez si froidement démonté la première édition du livre " C ++ 17 STL. Standard Template Library " de notre part et vous continuez à analyser la seconde, que nous avons finalement décidé de vous présenter ici un point de vue alternatif. L'auteur de l'article d'aujourd'hui est Ivan Čukić, qui est également propriétaire du livre Functional Programming in C ++ , qui est en cours de préparation pour une publication chez Manning Publishing House. Nous vous proposons d'évaluer ses pensées sceptiques, son code et ses calculs

Préambule

Je voulais nommer cet article «Sur la méchanceté des algorithmes STL» afin de tester mes propres compétences en provoquant des clics. Mais ensuite, il a décidé qu'il valait mieux écrire un article pour le public cible, et non pas écrire un tel article où ceux qui souhaitent discuter de mes thèses flagrantes se réuniraient.

Ainsi, je peux supposer que vous êtes intéressé par les algorithmes, leur complexité et que vous souhaitez écrire le code le plus parfait.

Des algorithmes

Dans la communauté C ++ professionnelle moderne, les gens sont souvent conseillés: pour rendre votre programme plus sûr, plus rapide, plus expressif, etc. - Utilisez les algorithmes de la bibliothèque standard. J'essaie aussi de vulgariser ce conseil dans mes livres, discours, séminaires ... partout où il y a un public approprié.

Bien sûr, il est absolument vrai que si nous sommes amenés à écrire une boucle for pour résoudre le problème auquel nous sommes confrontés, nous devons d'abord nous demander si les algorithmes existants de la bibliothèque standard (ou boost) sont adaptés à cela, et ne pas agir aveuglément.

Nous avons encore besoin de savoir comment ces algorithmes sont mis en œuvre, quelles exigences et garanties leur sont associées, quelle est leur complexité spatiale et temporelle.

Habituellement, si nous sommes confrontés à une tâche qui répond exactement aux exigences de l'algorithme STL et qu'elle peut être appliquée directement, cet algorithme sera la solution la plus efficace.

Un problème peut survenir si nous devons préparer les données d'une manière ou d'une autre avant d'appliquer l'algorithme.

Intersection d'ensembles

Supposons que nous écrivons un outil pour les développeurs C ++ qui donnerait des conseils sur le remplacement des options de capture par défaut (parler de [=] et [&] ) dans les expressions lambda, et afficherait explicitement une liste de variables capturées.

 std::partition(begin(elements), end(elements), [=] (auto element) { ^~~ -  -  ,   [threshold] return element > threshold; }); 

Lors de l'analyse d'un fichier, nous avons besoin d'une collection qui stocke les variables des portées actuelles et voisines. Dès que nous rencontrons une expression lambda avec une capture par défaut, nous devrons voir quelles variables y sont utilisées.

En conséquence, nous avons deux ensembles: dans l'un il y aura des variables des zones de visibilité environnantes, et dans l'autre il y aura des variables utilisées dans le corps de l'expression lambda.

La liste des options de capture que nous allons proposer pour le remplacement doit être l'intersection de ces deux ensembles (les expressions lambda peuvent utiliser des variables globales qui n'ont pas besoin d'être capturées, et toutes les variables de la portée environnante ne seront pas utilisées dans l'expression lambda).

Et, si nous avons besoin d'une intersection, nous pouvons utiliser l' std::set_intersection .

Cet algorithme est assez beau dans sa simplicité. Il accepte deux collections triées et les exécute simultanément du début à la fin:

• Si l'élément en cours dans la première collection est égal à l'élément en cours dans la deuxième collection, il est ajouté au résultat, que l'algorithme déplace simplement vers l'élément suivant dans les deux collections;
• Si l'élément réel dans la première collection est inférieur à l'élément réel dans la deuxième collection, l'algorithme ignore simplement l'élément actuel dans la première collection;
• Si l'élément réel dans la première collection est plus grand que l'élément réel dans la deuxième collection, l'algorithme ignore simplement l'élément actuel dans la deuxième collection;

Au moins un élément (de la première ou de la deuxième collection d'entrée) est ignoré à chaque itération - par conséquent, la complexité de l'algorithme sera linéaire - O(m + n) , où m est le nombre d'éléments dans la première collection et n est le nombre d'éléments dans la deuxième collection .

Simple et efficace. Tant que les collections d'entrée sont triées.

Tri

Voici le problème: que faire si les collections ne sont pas pré-triées?

Dans l'exemple précédent, il serait judicieux de stocker des variables de la portée environnante dans une structure de type pile, où l'analyseur pourrait simplement ajouter de nouveaux éléments entrant dans une nouvelle portée et supprimer les variables de la portée actuelle dès qu'il quitte.

Ainsi, les variables ne seront pas triées par nom, et nous ne pourrons pas utiliser directement std::set_intersection pour les opérations sur elles. De même, si vous suivez les variables dans le corps d'une expression lambda, nous ne pourrons probablement pas les enregistrer sous forme triée.

Puisque std::set_intersection ne fonctionne qu'avec des collections triées, dans de nombreux projets, ce principe se produit: d'abord nous trions les collections, puis nous appelons l' std::set_intersection .

Si nous oublions que le tri d'une pile de variables dans notre exemple dévalue complètement l'utilisation complète de la pile que nous avons définie, l'algorithme d'intersection pour les collections non triées ressemblera à ceci:

 template <typename InputIt1, typename InputIt2, typename OutputIt> auto unordered_intersection_1(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt dest) { std::sort(first1, last1); std::sort(first2, last2); return std::set_intersection(first1, last1, first2, last2, dest); } 

Quelle est la complexité de tout cet algorithme? Le tri prend un temps quasi-linéaire, donc la complexité globale de cette approche est O(n log n + m log m + n + m) .

Trier plus petit

Est-il possible de se passer du tri?

Si les deux collections ne sont pas triées, nous devrons faire le tour de la deuxième collection pour chaque élément du premier - pour décider de l'inclure ou non dans le jeu de résultats. Bien que cette approche soit assez courante dans les projets réels, elle est encore pire que la précédente - sa complexité est O(n * m) .

Au lieu de tout trier d'affilée, ou de ne rien trier, souvenez-vous du Zen et choisissez le troisième chemin - nous trions une seule collection.

Si une seule collection est triée, alors nous pouvons parcourir toutes les valeurs de la non triée une par une et pour chaque valeur vérifier si elle se trouve dans la collection triée. Pour ce faire, appliquez une recherche binaire.

Dans ce cas, la complexité temporelle sera O(n log n) pour trier la première collection et O (m log n) pour trier et vérifier. La complexité totale sera O((n + m) log n) .

Si nous décidions de trier la deuxième collection, et non la première, alors la complexité serait O((n + m) log m) .

Pour atteindre une efficacité maximale, nous trions toujours la collection dans laquelle il y a moins d'éléments, de sorte que la complexité finale de notre algorithme soit
((m + n) log (min(m, n)) .

L'implémentation ressemblera à ceci:

 template <typename InputIt1, typename InputIt2, typename OutputIt> auto unordered_intersection_2(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt dest) { const auto size1 = std::distance(first1, last1); const auto size2 = std::distance(first2, last2); if (size1 > size2) { unordered_intersection_2(first2, last2, first1, last1, dest); return; } std::sort(first1, last1); return std::copy_if(first2, last2, dest, [&] (auto&& value) { return std::binary_search(first1, last1, FWD(value)); }); } 

Dans notre exemple avec des listes de capture dans des expressions lambda, la collection de variables présentes dans l'expression lambda est généralement triée, car elle est probablement plus petite que la collection de toutes les variables de toutes les étendues environnantes.

Hachage

La dernière option consiste à construire std::unordered_set (une implémentation d'ensemble non ordonné basée sur le hachage) à partir d'une plus petite collection, plutôt que de la trier. Dans ce cas, la complexité des opérations de recherche sera en moyenne de O(1) , mais il faudra du temps pour construire std::unordered_set . La complexité du bâtiment peut aller de O(n) à O(n*n) , et c'est un problème potentiel.

 template <typename InputIt1, typename InputIt2, typename OutputIt> void unordered_intersection_3(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt dest) { const auto size1 = std::distance(first1, last1); const auto size2 = std::distance(first2, last2); if (size1 > size2) { unordered_intersection_3(first2, last2, first1, last1, dest); return; } std::unordered_set<int> test_set(first1, last1); return std::copy_if(first2, last2, dest, [&] (auto&& value) { return test_set.count(FWD(value)); }); } 

L'approche de hachage l'emporte complètement lorsque vous devez calculer les intersections de plusieurs ensembles avec un seul petit ensemble prédéfini. Autrement dit, nous avons l'ensemble A , les ensembles B₁ , B₂… et nous voulons calculer A ∩ B₁, A ∩ B₂…

Dans ce cas, vous pouvez ignorer la complexité de la construction std::unordered_set , et la complexité du calcul de chaque intersection sera linéaire - O(m) , où m est le nombre d'éléments dans la deuxième collection.

Contrôle

Bien sûr, il est toujours utile de vérifier la complexité de l'algorithme, mais dans de tels cas, il est également sage de vérifier différentes approches à l'aide de points de contrôle. Surtout lors du choix parmi les deux dernières options, où nous comparons les recherches binaires et les ensembles basés sur le hachage.
Mon test le plus simple a montré que la première option, où vous devez trier les deux collections, est toujours la plus lente.

Le tri d'une plus petite collection surpasse std::unordered_set peu std::unordered_set , mais pas particulièrement.

Les deuxième et troisième approches sont légèrement plus rapides que la première dans le cas où les deux collections ont un nombre égal d'éléments, et beaucoup plus rapide (jusqu'à six fois) lorsque le nombre d'éléments dans une collection est environ 1000 fois plus élevé que dans la seconde.