Étant donné que l'achat de puissance de calcul est beaucoup plus abordable que par le passé, la connaissance des algorithmes et l'efficacité sont-elles moins importantes? Il est clair que vous voudriez éviter une boucle infinie, donc tout ne se passe pas. Mais si vous avez un meilleur matériel, pourriez-vous avoir un logiciel quelque peu pire?
efficiency
Quora Feans
la source
la source
Réponses:
J'aime vraiment l'exemple du livre Introduction to Algorithms , qui illustre l'importance de l'efficacité des algorithmes:
Comparons deux algorithmes de tri: le tri par insertion et le tri par fusion . Leur complexité est respectivement et O ( n log n ) = c 2 n lg n . Typiquement, le tri par fusion a un facteur constant plus grand, supposons donc c 1 < c 2 .O(n2)=c1n2 O(nlogn)=c2nlgn c1<c2
Pour répondre à votre question, nous évaluons le temps d'exécution d'un ordinateur plus rapide (A) exécutant un algorithme de tri par insertion par rapport à un ordinateur plus lent (B) exécutant un algorithme de tri par fusion.
Nous supposons:
Donc, avec ces hypothèses, il faut
pour que l'ordinateur A trie107chiffres et
pour l'ordinateur B.
Ainsi, l'ordinateur, qui est 1000 fois plus lent, peut résoudre le problème 17 fois plus rapidement. En réalité, l'avantage du tri par fusion sera encore plus important et augmentera avec la taille du problème. J'espère que cet exemple vous aidera à répondre à votre question.
Cependant, ce n'est pas tout sur la complexité de l'algorithme. Aujourd'hui, il est presque impossible d'obtenir une accélération significative simplement en utilisant la machine avec une fréquence CPU plus élevée. Les gens doivent concevoir des algorithmes pour des systèmes multicœurs qui évoluent bien. C'est également une tâche délicate, car avec l'augmentation des cœurs, une surcharge (pour la gestion des accès à la mémoire, par exemple) augmente également. Il est donc presque impossible d'obtenir une accélération linéaire.
Donc, pour résumer, la conception d'algorithmes efficaces aujourd'hui est tout aussi importante qu'avant, car ni l'augmentation de fréquence ni les cœurs supplémentaires ne vous donneront l'accélération par rapport à celle apportée par l'algorithme efficace.
la source
Au contraire. En même temps que le matériel devient moins cher, plusieurs autres développements ont lieu.
Premièrement, la quantité de données à traiter augmente de façon exponentielle. Cela a conduit à l'étude des algorithmes de temps quasi -linéaire et au domaine des mégadonnées . Pensez par exemple aux moteurs de recherche - ils doivent gérer de gros volumes de requêtes, traiter de grandes quantités de données et le faire rapidement. Les algorithmes sont plus importants que jamais.
Deuxièmement, le domaine de l'apprentissage automatique se renforce et regorge d'algorithmes (bien que d'un type différent de celui que vous apprenez dans votre BA). Le domaine est florissant, et de temps en temps un algorithme vraiment nouveau est inventé, et améliore les performances de manière significative.
Troisièmement, les algorithmes distribués sont devenus plus importants, car nous rencontrons un obstacle pour augmenter la vitesse de traitement du processeur . De nos jours, la puissance de calcul est augmentée par la parallélisation , ce qui implique des algorithmes dédiés.
Quatrièmement, pour contrebalancer la puissance croissante des CPU, les paradigmes de programmation modernes utilisent des méthodes de machine virtuelle pour lutter contre les failles de sécurité. Cela ralentit ces programmes d'un facteur appréciable. Ajoutant à l'énigme, votre système d'exploitation investit plus de temps CPU sur les cloches et les sifflets, laissant moins de temps CPU pour vos programmes réels, qui pourraient inclure des algorithmes gourmands en CPU tels que la compression et la décompression vidéo. Ainsi, bien que le matériel soit plus rapide, il n'est pas utilisé aussi efficacement.
Des algorithmes résumés et efficaces sont nécessaires pour gérer de grandes quantités de données; de nouveaux types d'algorithmes font leur apparition dans le domaine de l' intelligence artificielle ; les algorithmes distribués sont en train de se concentrer; et la puissance du processeur est exploitée moins efficacement pour diverses raisons (mais principalement parce que les ordinateurs deviennent plus puissants). Les algorithmes ne sont pas encore morts.
la source
La connaissance des algorithmes est bien plus que la façon d'écrire des algorithmes rapides.
Il vous donne également des méthodes de résolution de problèmes (par exemple diviser pour mieux régner, programmation dynamique, gourmand, réduction, programmation linéaire, etc.) que vous pouvez ensuite appliquer lorsque vous approchez d'un problème nouveau et difficile. Une approche appropriée conduit généralement à des codes plus simples et beaucoup plus rapides à écrire. Je dois donc être en désaccord avec la réponse de Kevin car les codes qui ne sont pas soigneusement assemblés sont souvent non seulement lents mais aussi compliqués. J'aime cette citation de David Parnas:
(Bien sûr, nous devons également combiner des algorithmes avec des méthodes de conception logicielle pour écrire de bons codes.)
La connaissance des algorithmes nous indique également comment organiser vos données afin que vous puissiez les traiter plus facilement et plus efficacement grâce à l'utilisation de structures de données.
De plus, cela nous permet d' estimer l'efficacité de votre approche et de comprendre les compromis entre plusieurs approches différentes en termes de complexité temporelle, de complexité spatiale et de complexité des codes. Connaître ces compromis est la clé pour prendre la bonne décision dans les limites de vos ressources.
Sur l'importance de l'efficacité des logiciels, je citerai la loi de Wirth:
Larry Page a récemment réaffirmé que le logiciel devient deux fois plus lent tous les 18 mois, et dépasse ainsi la loi de Moore.
la source
Oui , ils sont «relativement» moins importants dans une large industrie. L'éditeur de texte peut être «assez rapide» et n'a pas besoin de beaucoup d'améliorations. Une grande partie de l'effort informatique consiste à s'assurer que le composant A écrit en Java fonctionne avec le composant B écrit avec C communique correctement via une file d'attente de messages écrite en Cobol (ou quelque chose), ou pour mettre le produit sur le marché, etc.
De plus, l'architecture s'est compliquée. Lorsque vous aviez de vieux processeurs simples où vous aviez 1 instruction par cycle et que vous écriviez dans l'assemblage, les optimisations étaient «faciles» (il vous suffisait de compter le nombre d'instructions). Actuellement, vous ne disposez pas d'un processeur simple mais d'un processeur super-scalaire entièrement hors pipeline avec renommage des registres et cache à plusieurs niveaux. Et vous n'écrivez pas en assembleur mais en C / Java / etc. où le code est compilé / JITed (généralement pour un meilleur code que vous ou moi écrivions en assembleur), ou en Python / Ruby / ... où le code est interprété et vous êtes séparé par plusieurs niveaux d'abstraction de la machine. Les microoptimalisations sont difficiles et la plupart des programmeurs auraient un effet opposé.
Non , ils sont toujours aussi importants dans la recherche et en termes «absolus» . Il existe des domaines où la vitesse est importante car ils fonctionnent sur une grande quantité de données. A cette échelle, les complexités comptent comme le montre l'exemple de Pavel.
Cependant, il existe d'autres cas - descendre des algorithmes est toujours une option choisie lorsque la vitesse est importante (HPC, périphériques intégrés, etc.). Vous trouverez sur de nombreuses universités des groupes spécialisés dans les compilateurs et / ou l'optimisation logicielle. Par exemple, un simple échange de l'ordre des boucles peut obtenir une accélération de mille fois simplement parce qu'il utilise efficacement le cache - alors qu'il pourrait s'agir d'un exemple limite, l'écart entre la CPU et la mémoire a augmenté de 1000 fois au cours des 30 dernières années. L'architecture informatique fait également partie de CS. Par conséquent, bon nombre des améliorations de la vitesse de calcul font en fait partie du domaine CS général.
Du côté industriel - lorsque vous avez un cluster HPC, la vitesse est importante car un seul programme peut fonctionner pendant des jours, des mois ou des années. Non seulement vous devez payer la facture d'électricité, mais attendre peut également coûter de l'argent. Vous pouvez jeter deux fois plus de matériel, mais 700 millions de dollars peuvent difficilement être considérés comme un changement de poche pour toutes les entreprises, sauf les plus grandes - dans de tels cas, les programmeurs sont l'option la moins chère et si la réécriture du programme dans un nouveau langage signifie juste une `` petite '' accélération - ils pourraient considère-le.
La vitesse peut également signifier une meilleure UX. De nombreux avis sur les téléphones portables indiquent que le système d'exploitation est «plus vif» et bien que cela puisse être fait par des «astuces», c'est certainement un domaine d'étude. Vous souhaitez également accéder à vos données plus rapidement et faire rapidement ce dont vous avez besoin. Parfois, cela signifie que vous pouvez faire plus - dans les jeux, vous avez 0,017s pour tout faire et plus vous êtes rapide, plus vous pouvez mettre de bonbons.
la source
C'est une discussion intéressante. Et nous avons quelques choses à regarder ici.
L'informatique théorique - Il s'agit d'une science en évolution, ce qui signifie qu'avec le temps, nous trouverons de nouvelles et meilleures façons de résoudre les problèmes, ce qui signifie des algorithmes améliorés pour la recherche et le tri par exemple.
Grandes communautés / plus grandes bibliothèques - Parce que beaucoup de travail a été fait par d'autres personnes, nous pouvons simplement construire sur leur travail et utiliser les algorithmes qu'ils ont déjà créés et même codés. Et ces bibliothèques seront mises à jour avec le temps nous permettant un accès automatique à des programmes / algorithmes plus efficaces.
Développement - Maintenant, nous avons ici un problème, je pense. Beaucoup de programmeurs ne sont pas des informaticiens, ils écrivent donc du code pour résoudre des problèmes commerciaux et non des problèmes techniques / théoriques et seraient aussi heureux d'utiliser un tri à bulles qu'un tri rapide par exemple. Et ici, la vitesse du matériel permet aux mauvais programmeurs de s'en tirer avec de mauvais algorithmes et de mauvaises pratiques de codage. Mémoire, vitesse du processeur, espace de stockage, ces choses ne sont plus des préoccupations majeures et tous les quelques mois, les choses deviennent plus grandes, plus rapides et moins chères. Je veux dire, regardez les nouveaux téléphones portables. Ils sont désormais plus avancés que les ordinateurs / serveurs mainframe des années 70/80. Plus de stockage, plus de puissance de traitement, une mémoire plus rapide.
UI & DATA - Interface utilisateur / Expérience utilisateur et DATA sont désormais considérés comme plus importants que le code super efficace dans la plupart des domaines de développement. Ainsi, la vitesse ne devient et ne pose problème que lorsqu'un utilisateur doit attendre longtemps. Si nous donnons à l'utilisateur une bonne apparence et qu'il reçoit une bonne réponse de l'application, il est heureux. Et si les entreprises savent que toutes les données sont stockées de manière sûre et sécurisée et qu'elles peuvent les récupérer et les manipuler à tout moment, elles se moquent de l'espace dont elles ont besoin.
Je dois donc dire que ce n'est pas que les programmeurs efficaces ne sont plus importants ou nécessaires, c'est juste que très peu d'entreprises / d'utilisateurs récompensent les gens pour être des programmeurs super efficaces, et en raison du matériel meilleur, nous nous en sortons avec moins efficace. Mais il y a au moins encore des gens qui se concentrent sur l'efficacité et en raison de l'esprit communautaire, tout le monde en profite à temps.
la source
Quelques autres angles sur cette question intéressante et profonde qui mettent l'accent sur les aspects interdisciplinaires et transversaux du phénomène. Dai cite la loi de Wirth dans sa réponse:
Il existe des parallèles intéressants entre cette idée et les phénomènes observés en économie. Notez que l'économie a de nombreux liens profonds avec l'informatique, par exemple dans la planification, par exemple, où les ressources rares (par exemple, les threads, etc.) sont allouées sur demande, par des algorithmes «d'équilibrage de charge». Un autre exemple est ce qu'on appelle une file d'attente producteur-consommateur. Aussi, les enchères.
Aussi, par exemple, Liste des lois éponymes, Wikipedia :
Il existe également une forte similitude avec le paradoxe de Jevon qui a été observé dans l'augmentation de la consommation d'énergie après que les moteurs à vapeur Watt plus efficaces ont commencé à remplacer la conception de Newcomen, mais l'utilisation ou la prolifération des moteurs a augmenté:
L'analogie est que le matériel est la ressource et le logiciel est comme la consommation de la ressource (aka, l'offre vs la demande). Ainsi, les logiciels et le matériel (et les progrès dans chacun) existent quelque peu dans une boucle de rétroaction symbiotique étroitement couplée les uns avec les autres, dans un sens, coévoluant . De nombreux facteurs complexes et interdépendants influencent cette interaction, par exemple:
la source
Non, surtout en tenant compte de la complexité de l'espace! La capacité de stockage d'un ordinateur normal augmente de façon exponentielle.
la source