Faut-il préférer les algorithmes STL aux boucles roulées à la main?

https://stackoverflow.com/questions/135129

02-07-2019
|

Question

Il semble que je vois plus de boucles "for" que d'itérateurs dans les questions & amp; répond ici que je ne le fais pour_each (), transformer (), etc. Scott Meyers suggère que les algorithmes stl soient préférés , ou du moins ce qu'il a fait en 2001. Bien sûr, en utilisant eux signifie souvent déplacer le corps de la boucle dans une fonction ou un objet de fonction. Certains peuvent penser qu’il s’agit d’une complication inacceptable, alors que d’autres peuvent penser qu’il vaut mieux résoudre le problème.

Alors ... faut-il privilégier les algorithmes STL aux boucles roulées à la main?

La solution

Cela dépend de:

Si des performances élevées sont requises
La lisibilité de la boucle
Si l'algorithme est complexe

Si la boucle n'est pas le goulot d'étranglement et que l'algorithme est simple (comme pour for_each), pour la norme C ++ actuelle, je préférerais une boucle roulée à la main pour plus de lisibilité. (La localisation de la logique est la clé.)

Cependant, maintenant que C ++ 0x / C ++ 11 est supporté par certains compilateurs majeurs, je dirais que nous utilisons des algorithmes STL car ils autorisent désormais les expressions lambda - et donc la localité de la logique.

Autres conseils

Je vais aller à contre-courant et dire que l'utilisation d'algorithmes STL avec des foncteurs rend le code beaucoup plus facile à comprendre et à maintenir, mais vous devez le faire correctement. Vous devez faire plus attention à la lisibilité et à la clarté. En particulier, il faut bien nommer. Mais quand vous le faites, vous pouvez vous retrouver avec un code plus propre et plus clair et un changement de paradigme en techniques de codage plus puissantes.

Prenons un exemple. Nous avons ici un groupe d’enfants et nous voulons attribuer une valeur à leur «compte foo». L’approche standard pour les boucles et les itérateurs est la suivante:

for (vector<Child>::iterator iter = children.begin();
    iter != children.end();
    ++iter)
{
    iter->setFooCount(n);
}

Lequel, oui, c’est assez clair, et certainement pas mauvais . Vous pouvez le comprendre en le regardant un peu. Mais regardons ce que nous pouvons faire avec un foncteur approprié:

for_each(children.begin(), children.end(), SetFooCount(n));

Wow, cela dit exactement ce dont nous avons besoin. Vous n'êtes pas obligé de le comprendre; vous savez immédiatement que cela définit le «nombre de Foo» de chaque enfant. (Ce serait encore plus clair si nous n’avions pas besoin du non-sens .begin () / .end (), mais vous ne pouvez pas tout avoir, et ils ne m’ont pas consulté lors de la création de la STL.)

Certes, vous devez définir ce foncteur magique, SetFooCount , mais sa définition est plutôt géniale:

class SetFooCount
{
public:
    SetFooCount(int n) : fooCount(n) {}

    void operator () (Child& child)
    {
        child.setFooCount(fooCount);
    }

private:
    int fooCount;
};

Au total, il s’agit de plus de code, et vous devez chercher à un autre endroit pour savoir exactement ce que SetFooCount fait. Mais comme nous l’avons bien nommé, 99% du temps, nous n’avons pas à consulter le code de SetFooCount . Nous supposons que cela fait ce qu'il dit, et nous n'avons qu'à regarder la ligne for_each .

Ce que j’aime vraiment, c’est que l’utilisation des algorithmes entraîne un changement de paradigme. Au lieu de considérer une liste comme une collection d'objets et de modifier chaque élément de la liste, vous la considérez comme une entité de première classe et vous agissez directement sur la liste elle-même. La boucle for parcourt la liste en appelant une fonction membre sur chaque élément pour définir le nombre de Foo. Au lieu de cela, je fais une commande, qui définit le nombre de Foo de chaque élément de la liste. C’est subtile, mais quand on regarde la forêt au lieu des arbres, on gagne plus de pouvoir.

Donc, avec un peu de réflexion et de nommage soigneux, nous pouvons utiliser les algorithmes STL pour créer un code plus propre et plus clair et commencer à penser à un niveau moins granulaire.

Le std :: foreach est le genre de code qui m'a fait maudire la STL il y a des années.

Je ne peux pas dire si c'est mieux, mais j'aime plus que le code de ma boucle soit placé sous le préambule de la boucle. Pour moi, c’est une exigence forte . Et la construction std :: foreach ne me le permet pas (assez étrangement, les versions foreach de Java ou C # sont cool, en ce qui me concerne ... Donc, je suppose que cela confirme la localité du corps de la boucle est très très importante).

Je n’utiliserai donc le foreach que s’il existe déjà un algorithme lisible / compréhensible utilisable avec lui. Sinon, non, je ne le ferai pas. Mais c’est une question de goût, je suppose, comme je devrais peut-être essayer de mieux comprendre et apprendre à analyser tout ça ...

Notez que les utilisateurs de Boost ont apparemment ressenti un peu la même chose, car ils ont écrit BOOST_FOREACH:

#include <string> #include <iostream> #include <boost/foreach.hpp> int main() { std::string hello( "Hello, world!" ); BOOST_FOREACH( char ch, hello ) { std::cout << ch; } return 0; }

Voir: http://www.boost.org/ doc / libs / 1_35_0 / doc / html / foreach.html

C'est vraiment la seule chose à laquelle Scott Meyers s'est trompé.

S'il existe un algorithme correspondant à ce que vous devez faire, utilisez bien sûr l'algorithme.

Mais si tout ce que vous avez à faire est de parcourir une collection et de faire quelque chose pour chaque élément, faites simplement la boucle normale au lieu d'essayer de séparer le code dans un foncteur différent, cela finira simplement par découper le code en bits sans aucun réel gain.

Il existe d’autres options telles que boost :: bind ou boost :: lambda, mais ce sont des métaprogrammations de modèles vraiment complexes, elles ne fonctionnent pas très bien avec le débogage et l’exploration du code, elles doivent donc généralement être évitées.

Comme d'autres l'ont mentionné, tout cela changera lorsque les expressions lambda deviendront un citoyen de première classe.

La boucle pour est impérative, les algorithmes sont déclaratifs. Lorsque vous écrivez std :: max_element , ce dont vous avez besoin est évident. Lorsque vous utilisez une boucle pour obtenir le même résultat, ce n'est pas nécessairement le cas.

Les algorithmes peuvent également présenter un léger avantage en termes de performances. Par exemple, lors de la traversée d'un std :: deque , un algorithme spécialisé peut éviter de vérifier de manière redondante si un incrément donné déplace le pointeur sur une limite de bloc.

Cependant, les expressions de foncteur compliquées rendent rapidement les invocations d’algorithmes illisibles. Si une boucle explicite est plus lisible, utilisez-la. Si un appel d'algorithme peut être exprimé sans expressions de liaison à dix étages, préférez-le. La lisibilité est plus importante que la performance here , car ce type d’optimisation est ce que Knuth attribue si bien à Hoare; vous pourrez utiliser une autre construction sans problème une fois que vous réaliserez que c'est un goulot d'étranglement.

Cela dépend, si l'algorithme ne prend pas de foncteur, utilisez toujours la version de l'algorithme std. Il est à la fois plus simple d’écrire et plus clair.

Pour les algorithmes utilisant des foncteurs, généralement non, jusqu'à ce que C ++ 0x lambdas puisse être utilisé. Si le foncteur est petit et l’algorithme complexe (la plupart ne le sont pas), il peut être préférable d’utiliser quand même l’algorithme std.

Je suis un grand fan des algorithmes STL en principe mais, dans la pratique, il est trop lourd. Au moment où vous définissez vos classes foncteur / prédicat, une boucle de deux lignes peut se transformer en plus de 40 lignes de code qui sont 10 fois plus difficiles à comprendre.

Heureusement, les choses vont devenir beaucoup plus faciles en C ++ 0x avec les fonctions lambda, auto et la nouvelle pour . Consultez cette Présentation de C ++ 0x sur Wikipedia.

Je n’utiliserais pas de règle absolue. Il y a de nombreux facteurs à prendre en compte, comme souvent, vous exécutez certaines opérations dans votre code, ce n'est qu'une boucle ou un "réel". algorithme, l’algorithme dépend-il de beaucoup de contexte que vous auriez à transmettre à votre fonction?

Par exemple, je ne mettrais pas quelque chose comme

for (int i = 0; i < some_vector.size(); i++) if (some_vector[i] == NULL) some_other_vector[i]++;

dans un algorithme, car il en résulterait beaucoup plus de pourcentage de code et je devrais faire en sorte que some_other_vector soit connu de l’algorithme.

Il existe de nombreux autres exemples dans lesquels l’utilisation des algorithmes STL est très utile, mais vous devez décider au cas par cas.

Je pense que l'interface de l'algorithme STL est sous-optimale et doit être évitée car l'utilisation directe de la boîte à outils STL (pour les algorithmes) pourrait générer un très faible gain de performances, mais coûtera certainement . lisibilité, facilité de maintenance et même un peu d'écriture lorsque vous apprenez à utiliser les outils.

La norme pour une boucle sur un vecteur est beaucoup plus efficace:

int weighted_sum = 0; for (int i = 0; i < a_vector.size(); ++i) { weighted_sum += (i + 1) * a_vector[i]; // Just writing something a little nontrivial. }

que d'utiliser une construction for_each ou d'essayer de l'intégrer à un appel à accumuler?

Vous pourriez soutenir que le processus d'itération est moins efficace, mais un for _ each introduit également un appel de fonction à chaque étape ( pourrait être atténué en essayant d'intégrer la fonction, mais rappelez-vous que "inline" n’est qu’une suggestion au compilateur - il peut l’ignorer).

Dans tous les cas, la différence est faible. D'après mon expérience, plus de 90% du code que vous écrivez n'est pas critique en termes de performances, mais est critique pour le temps du codeur . En gardant votre boucle STL littéralement en ligne, elle est très lisible. Il y a moins d'indirection pour trébucher, pour vous ou pour les futurs responsables. Si cela se trouve dans votre guide de style, vous gagnez du temps d’apprentissage pour vos codeurs (admettez-le, apprendre à utiliser correctement le STL la première fois implique quelques moments inattendus). Ce dernier bit est ce que je veux dire par un coût en écriture.

Bien sûr, il existe des cas particuliers - par exemple, vous pourriez en fait vouloir que la fonction for_each soit séparée pour pouvoir être réutilisée à plusieurs autres endroits. Ou bien, cela pourrait être l’une de ces rares sections très critiques en termes de performances. Mais ce sont des cas spéciaux - des exceptions plutôt que la règle.

IMO, il convient d'éviter de nombreux algorithmes de bibliothèque standard tels que std :: for_each - principalement pour les problèmes de manque de lambda évoqués par d'autres, mais aussi parce qu'il existe un problème de dissimulation inappropriée des détails.

Bien sûr, cacher les détails dans les fonctions et les classes fait partie de l’abstraction, et en général, une abstraction de bibliothèque vaut mieux que de réinventer la roue. Mais une habileté essentielle en abstraction consiste à savoir quand le faire - et quand ne pas le faire. Une abstraction excessive peut nuire à la lisibilité, à la facilité de maintenance, etc. Le bon jugement découle de l’expérience, et non de règles inflexibles - bien que vous deviez apprendre les règles avant d’apprendre à les enfreindre, bien sûr.

OTOH, cela vaut la peine de prendre en compte le fait que beaucoup de programmeurs utilisent C ++ (et avant cela, C, Pascal, etc.) depuis longtemps. Les vieilles habitudes ont la vie dure, et il existe cette chose appelée dissonance cognitive qui mène souvent à des excuses et à des rationalisations. . Cependant, ne tirez pas trop vite les conclusions: il est au moins aussi probable que les responsables de la normalisation soient coupables de dissonance post-décisionnelle.

Je pense que le niveau de confort du développeur est un facteur important.

Il est probablement vrai que transformer ou for_each est la bonne chose à faire, mais ce n’est pas plus efficace, et les boucles manuscrites ne sont pas dangereuses en soi. Si cela prend une demi-heure à un développeur pour écrire une boucle simple, par rapport à une demi-journée pour obtenir la syntaxe de transformation ou for_each exacte et déplacer le code fourni dans une fonction ou un objet de fonction. Et ensuite, les autres développeurs auraient besoin de savoir ce qui se passait.

Un nouveau développeur serait probablement mieux servi en apprenant à utiliser transform and for_each plutôt qu’à des boucles faites à la main, puisqu’il serait capable de les utiliser systématiquement sans erreur. Pour le reste d'entre nous pour qui écrire des boucles est une seconde nature, il est probablement préférable de s'en tenir à ce que l'on sait et de se familiariser davantage avec les algorithmes pendant notre temps libre.

En termes simples, si je disais à mon patron que j'ai passé la journée à convertir des boucles faites main en appels for_each et à transformer des appels, je doute qu'il soit vraiment ravi.

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow