Efficacité algorithmique - Algorithmic efficiency

En informatique , l' efficacité algorithmique est une propriété d'un algorithme qui se rapporte à la quantité de ressources de calcul utilisées par l'algorithme. Un algorithme doit être analysé pour déterminer son utilisation des ressources, et l'efficacité d'un algorithme peut être mesurée en fonction de l'utilisation de différentes ressources. L'efficacité algorithmique peut être considérée comme analogue à la productivité d' ingénierie pour un processus répétitif ou continu.

Pour une efficacité maximale, nous souhaitons minimiser l'utilisation des ressources. Cependant, différentes ressources telles que la complexité temporelle et spatiale ne peuvent pas être comparées directement, donc lequel des deux algorithmes est considéré comme le plus efficace dépend souvent de la mesure d'efficacité considérée comme la plus importante.

Par exemple, bubble sort et timsort sont tous deux des algorithmes permettant de trier une liste d'éléments du plus petit au plus grand. Le tri à bulles trie la liste dans le temps proportionnellement au nombre d'éléments au carré ( , voir la notation Big O ), mais ne nécessite qu'une petite quantité de mémoire supplémentaire qui est constante par rapport à la longueur de la liste ( ). Timsort trie la liste en temps linéaire (proportionnel à une quantité multipliée par son logarithme) dans la longueur de la liste ( ), mais a un encombrement linéaire dans la longueur de la liste ( ). Si de grandes listes doivent être triées à grande vitesse pour une application donnée, timsort est un meilleur choix ; cependant, s'il est plus important de minimiser l'empreinte mémoire du tri, le tri à bulles est un meilleur choix.

Arrière-plan

L'importance de l'efficacité par rapport au temps a été soulignée par Ada Lovelace en 1843 comme s'appliquant au moteur d'analyse mécanique de Charles Babbage :

"Dans presque chaque calcul, une grande variété d'arrangements pour la succession des processus est possible, et diverses considérations doivent influencer les sélections parmi eux aux fins d'un moteur de calcul. Un objet essentiel est de choisir cet arrangement qui tendra à réduire à au minimum le temps nécessaire à la réalisation du calcul"

Les premiers ordinateurs électroniques étaient sévèrement limités à la fois par la vitesse des opérations et la quantité de mémoire disponible. Dans certains cas, on s'est rendu compte qu'il y avait un compromis espace-temps , par lequel une tâche pouvait être gérée soit en utilisant un algorithme rapide qui utilisait beaucoup de mémoire de travail, soit en utilisant un algorithme plus lent qui utilisait très peu de mémoire de travail . Le compromis technique consistait alors à utiliser l'algorithme le plus rapide qui tiendrait dans la mémoire disponible.

Les ordinateurs modernes sont nettement plus rapides que les premiers ordinateurs et disposent d'une plus grande quantité de mémoire disponible ( gigaoctets au lieu de kilooctets ). Néanmoins, Donald Knuth a souligné que l'efficacité est toujours une considération importante :

"Dans les disciplines d'ingénierie établies, une amélioration de 12%, facilement obtenue, n'est jamais considérée comme marginale et je pense que le même point de vue devrait prévaloir en génie logiciel"

Aperçu

Un algorithme est considéré comme efficace si sa consommation de ressources, également appelée coût de calcul, est égale ou inférieure à un niveau acceptable. En gros, « acceptable » signifie : il s'exécutera dans un laps de temps ou d'espace raisonnable sur un ordinateur disponible, généralement en fonction de la taille de l'entrée. Depuis les années 1950, les ordinateurs ont connu des augmentations spectaculaires à la fois de la puissance de calcul disponible et de la quantité de mémoire disponible, de sorte que les niveaux acceptables actuels auraient été inacceptables il y a même 10 ans. En fait, grâce au doublement approximatif de la puissance des ordinateurs tous les 2 ans , les tâches qui sont acceptablement efficaces sur les smartphones modernes et les systèmes embarqués peuvent avoir été inacceptablement inefficaces pour les serveurs industriels il y a 10 ans.

Les fabricants d'ordinateurs sortent fréquemment de nouveaux modèles, souvent plus performants . Les coûts des logiciels peuvent être assez élevés, donc dans certains cas, le moyen le plus simple et le moins cher d'obtenir des performances plus élevées peut être d'acheter simplement un ordinateur plus rapide, à condition qu'il soit compatible avec un ordinateur existant.

Il existe de nombreuses façons de mesurer les ressources utilisées par un algorithme : les deux mesures les plus courantes sont la vitesse et l'utilisation de la mémoire ; d'autres mesures pourraient inclure la vitesse de transmission, l'utilisation temporaire du disque, l'utilisation du disque à long terme, la consommation d'énergie, le coût total de possession , le temps de réponse aux stimuli externes, etc. Beaucoup de ces mesures dépendent de la taille de l'entrée de l'algorithme, c'est-à-dire le quantité de données à traiter. Ils peuvent également dépendre de la manière dont les données sont organisées ; par exemple, certains algorithmes de tri fonctionnent mal sur des données déjà triées ou triées dans l'ordre inverse.

En pratique, d'autres facteurs peuvent affecter l'efficacité d'un algorithme, tels que les exigences de précision et/ou de fiabilité. Comme détaillé ci-dessous, la manière dont un algorithme est implémenté peut également avoir un effet significatif sur l'efficacité réelle, bien que de nombreux aspects de cela soient liés à des problèmes d' optimisation .

Analyse théorique

Dans l' analyse théorique des algorithmes , la pratique normale consiste à estimer leur complexité au sens asymptotique. La note la plus couramment utilisée pour décrire la consommation de ressources ou « complexité » est Donald Knuth de notation Big O , représentant la complexité d'un algorithme en fonction de la taille de l'entrée . La notation Big O est une mesure asymptotique de la complexité de la fonction, où cela signifie approximativement que le temps requis pour un algorithme est proportionnel à , en omettant les termes d'ordre inférieur qui contribuent moins qu'à la croissance de la fonction à mesure qu'elle devient arbitrairement grande . Cette estimation peut être trompeuse lorsqu'elle est petite, mais est généralement suffisamment précise lorsqu'elle est grande car la notation est asymptotique. Par exemple, le tri à bulles peut être plus rapide que le tri par fusion lorsque seuls quelques éléments doivent être triés ; cependant, l'une ou l'autre implémentation est susceptible de répondre aux exigences de performance pour une petite liste. En règle générale, les programmeurs s'intéressent aux algorithmes qui s'adaptent efficacement à de grandes tailles d'entrée, et le tri par fusion est préféré au tri à bulles pour les listes de longueur rencontrées dans la plupart des programmes à forte intensité de données.

Voici quelques exemples de notation Big O appliquée à la complexité temporelle asymptotique des algorithmes :

Notation Nom Exemples
constant Trouver la médiane à partir d'une liste triée de mesures ; Utilisation d'une table de recherche de taille constante ; Utilisation d'une fonction de hachage appropriée pour rechercher un élément.
logarithmique Recherche d'un élément dans un tableau trié avec une recherche binaire ou un arbre de recherche équilibré ainsi que toutes les opérations dans un tas binomial .
linéaire Trouver un élément dans une liste non triée ou un arbre mal formé (pire des cas) ou dans un tableau non trié ; Ajout de deux entiers n bits par ripple carry .
linéaire , log-linéaire ou quasi-linéaire Réalisation d'une transformée de Fourier rapide ; heapsort , quicksort ( meilleur et moyen cas ) ou tri par fusion
quadratique Multiplier deux nombres à n chiffres par un algorithme simple ; tri à bulles (pire des cas ou implémentation naïve), tri Shell, tri rapide ( pire des cas ), tri par sélection ou tri par insertion
exponentiel Trouver la solution optimale (non approximative ) au problème du voyageur de commerce en utilisant la programmation dynamique ; déterminer si deux instructions logiques sont équivalentes à l' aide de la recherche par force brute

Benchmarking : mesurer la performance

Pour les nouvelles versions de logiciels ou pour fournir des comparaisons avec des systèmes concurrents, des références sont parfois utilisées, qui aident à évaluer les performances relatives d'un algorithme. Si un nouvel algorithme de tri est produit, par exemple, il peut être comparé à ses prédécesseurs pour s'assurer qu'au moins il est efficace comme avant avec des données connues, en tenant compte des améliorations fonctionnelles. Les références peuvent être utilisées par les clients lorsqu'ils comparent divers produits de fournisseurs alternatifs pour estimer quel produit répondra le mieux à leurs exigences spécifiques en termes de fonctionnalité et de performance. Par exemple, dans le monde de l' ordinateur central, certains produits de tri propriétaires d' éditeurs de logiciels indépendants tels que Syncsort rivalisent avec les produits des principaux fournisseurs tels qu'IBM pour la vitesse.

Certains benchmarks offrent des opportunités pour produire une analyse comparant la vitesse relative de divers langages compilés et interprétés par exemple et The Computer Language Benchmarks Game compare les performances des implémentations de problèmes de programmation typiques dans plusieurs langages de programmation.

Même la création de benchmarks « faites-le vous-même » peut démontrer les performances relatives de différents langages de programmation, en utilisant une variété de critères spécifiés par l'utilisateur. C'est assez simple, comme le démontre par l'exemple un "Rassemblement de performances en neuf langues" de Christopher W. Cowell-Shah.

Problèmes de mise en œuvre

Les problèmes de mise en œuvre peuvent également avoir un effet sur l'efficacité, comme le choix du langage de programmation, ou la manière dont l'algorithme est réellement codé, ou le choix d'un compilateur pour un langage particulier, ou les options de compilation utilisées, ou encore le fonctionnement système utilisé. Dans de nombreux cas, un langage implémenté par un interpréteur peut être beaucoup plus lent qu'un langage implémenté par un compilateur. Voir les articles sur la compilation juste-à-temps et les langages interprétés .

Il existe d'autres facteurs qui peuvent affecter les problèmes de temps ou d'espace, mais qui peuvent être hors du contrôle d'un programmeur ; ceux-ci incluent l'alignement des données , la granularité des données , la localité du cache , la cohérence du cache , le ramasse - miettes , le parallélisme au niveau des instructions , le multithreading (au niveau matériel ou logiciel), le multitâche simultané et les appels de sous - programme .

Certains processeurs ont des capacités de traitement vectoriel , qui permettent à une seule instruction d'opérer sur plusieurs opérandes ; il peut ou non être facile pour un programmeur ou un compilateur d'utiliser ces capacités. Les algorithmes conçus pour le traitement séquentiel peuvent devoir être complètement repensés pour utiliser le traitement parallèle , ou ils pourraient être facilement reconfigurés. Alors que l'informatique parallèle et distribuée gagne en importance à la fin des années 2010, davantage d'investissements sont réalisés dans des API de haut niveau efficaces pour les systèmes informatiques parallèles et distribués tels que CUDA , TensorFlow , Hadoop , OpenMP et MPI .

Un autre problème qui peut survenir lors de la programmation est que les processeurs compatibles avec le même jeu d'instructions (tels que x86-64 ou ARM ) peuvent implémenter une instruction de différentes manières, de sorte que les instructions relativement rapides sur certains modèles peuvent être relativement lentes sur d'autres modèles. . Cela présente souvent des défis pour l' optimisation des compilateurs , qui doivent avoir une grande connaissance du processeur spécifique et des autres matériels disponibles sur la cible de compilation pour optimiser au mieux les performances d'un programme. Dans le cas extrême, un compilateur peut être contraint d' émuler des instructions non prises en charge sur une plate-forme cible de compilation, l'obligeant à générer du code ou à lier un appel de bibliothèque externe pour produire un résultat qui serait autrement incalculable sur cette plate-forme, même si elle est nativement prise en charge et plus efficace en matériel sur d'autres plates-formes. C'est souvent le cas dans les systèmes embarqués en ce qui concerne l' arithmétique à virgule flottante , où les microcontrôleurs petits et de faible puissance manquent souvent de support matériel pour l'arithmétique à virgule flottante et nécessitent donc des routines logicielles coûteuses en calcul pour produire des calculs en virgule flottante.

Mesures de l'utilisation des ressources

Les mesures sont normalement exprimées en fonction de la taille de l'entrée .

Les deux mesures les plus courantes sont :

  • Temps : combien de temps met l'algorithme à se terminer ?
  • Espace : quelle quantité de mémoire de travail (généralement RAM) est nécessaire à l'algorithme ? Cela a deux aspects : la quantité de mémoire nécessaire au code (utilisation de l'espace auxiliaire) et la quantité de mémoire nécessaire pour les données sur lesquelles le code opère (utilisation de l'espace intrinsèque).

Pour les ordinateurs alimentés par une batterie (ex. ordinateurs portables et smartphones ), ou pour les calculs très longs/volumineux (ex. supercalculateurs ), d'autres mesures intéressantes sont :

  • Consommation d'énergie directe : puissance nécessaire directement pour faire fonctionner l'ordinateur.
  • Consommation électrique indirecte : puissance nécessaire pour le refroidissement, l'éclairage, etc.

Depuis 2018, la consommation d'énergie devient une mesure importante pour les tâches de calcul de tous types et à toutes les échelles, allant des périphériques Internet des objets embarqués aux périphériques système sur puce en passant par les batteries de serveurs . Cette tendance est souvent qualifiée d' informatique verte .

Des mesures moins courantes de l'efficacité de calcul peuvent également être pertinentes dans certains cas :

  • Taille de transmission : la bande passante peut être un facteur limitant. La compression des données peut être utilisée pour réduire la quantité de données à transmettre. L'affichage d'une image ou d'une image (ex : logo Google ) peut entraîner la transmission de dizaines de milliers d'octets (48K dans ce cas) contre six octets pour le texte « Google ». Ceci est important pour les tâches informatiques liées aux E/S .
  • Espace externe : espace nécessaire sur un disque ou autre périphérique de mémoire externe ; il peut s'agir d'un stockage temporaire pendant l'exécution de l'algorithme, ou il peut s'agir d'un stockage à long terme devant être reporté pour référence future.
  • Temps de réponse ( latence ) : ceci est particulièrement pertinent dans une application en temps réel lorsque le système informatique doit répondre rapidement à un événement externe .
  • Coût total de possession : en particulier si un ordinateur est dédié à un algorithme particulier.

Temps

Théorie

Analysez l'algorithme, en utilisant généralement une analyse de complexité temporelle pour obtenir une estimation du temps d'exécution en fonction de la taille des données d'entrée. Le résultat est normalement exprimé en utilisant la notation Big O . Ceci est utile pour comparer des algorithmes, en particulier lorsqu'une grande quantité de données doit être traitée. Des estimations plus détaillées sont nécessaires pour comparer les performances des algorithmes lorsque la quantité de données est faible, bien que cela soit probablement moins important. Les algorithmes qui incluent un traitement parallèle peuvent être plus difficiles à analyser .

Entraine toi

Utilisez un benchmark pour chronométrer l'utilisation d'un algorithme. De nombreux langages de programmation ont une fonction disponible qui fournit l'utilisation du temps CPU . Pour les algorithmes de longue durée, le temps écoulé pourrait également être intéressant. Les résultats doivent généralement être moyennés sur plusieurs tests.

Profilage basé sur l' exécution peut être très sensible à la configuration matérielle et la possibilité d'autres programmes en cours d' exécution ou de tâches en même temps dans un traitement multi-processeurs et multi-programmation environnement.

Ce type de test dépend également fortement de la sélection d'un langage de programmation, d'un compilateur et d'options de compilateur particuliers, de sorte que les algorithmes comparés doivent tous être implémentés dans les mêmes conditions.

Espace

Cette section concerne l' utilisation des ressources de mémoire ( registres , cache , RAM , mémoire virtuelle , mémoire secondaire ) , tandis que l'algorithme est en cours d' exécution. Comme pour l'analyse temporelle ci-dessus, analysez l'algorithme, en utilisant généralement une analyse de complexité spatiale pour obtenir une estimation de la mémoire d'exécution nécessaire en fonction de la taille des données d'entrée. Le résultat est normalement exprimé en utilisant la notation Big O .

Il y a jusqu'à quatre aspects de l'utilisation de la mémoire à prendre en compte :

Les premiers ordinateurs électroniques et les premiers ordinateurs personnels disposaient d'une mémoire de travail relativement faible. Par exemple, le calculateur automatique de stockage électronique de délai (EDSAC) de 1949 avait une mémoire de travail maximale de 1024 mots de 17 bits, tandis que le Sinclair ZX80 de 1980 était initialement doté de 1024 octets de mémoire de travail de 8 bits. À la fin des années 2010, il est courant que les ordinateurs personnels aient entre 4 et 32 Go de RAM, soit une augmentation de plus de 300 millions de fois plus de mémoire.

Mise en cache et hiérarchie mémoire

Les ordinateurs actuels peuvent avoir des quantités de mémoire relativement importantes (éventuellement des gigaoctets), donc devoir compresser un algorithme dans une quantité confinée de mémoire est beaucoup moins un problème qu'auparavant. Mais la présence de quatre catégories différentes de mémoire peut être significative :

  • Les registres du processeur , la plus rapide des technologies de mémoire informatique avec le moins d'espace de stockage. La plupart des calculs directs sur les ordinateurs modernes se produisent avec les opérandes source et destination dans les registres avant d'être mis à jour dans le cache, la mémoire principale et la mémoire virtuelle si nécessaire. Sur un cœur de processeur , il y a généralement de l'ordre de centaines d'octets ou moins de disponibilité de registre, bien qu'un fichier de registre puisse contenir plus de registres physiques que de registres architecturaux définis dans l'architecture du jeu d'instructions.
  • La mémoire cache est la deuxième mémoire la plus rapide et la deuxième plus petite disponible dans la hiérarchie de mémoire. Les caches sont présents dans les CPU, les GPU, les disques durs et les périphériques externes, et sont généralement implémentés dans la RAM statique . Les caches mémoire sont à plusieurs niveaux ; les niveaux inférieurs sont plus grands, plus lents et généralement partagés entre les cœurs de processeur dans les processeurs multicœurs . Afin de traiter les opérandes dans la mémoire cache, une unité de traitement doit récupérer les données du cache, effectuer l'opération dans les registres et réécrire les données dans le cache. Cela fonctionne à des vitesses comparables (environ 2 à 10 fois plus lentes) avec l'unité arithmétique logique ou arithmétique du CPU ou du GPU ou l' unité à virgule flottante si elle se trouve dans le cache L1 . Il est environ 10 fois plus lent s'il y a un échec de cache L1 et il doit être récupéré et écrit dans le cache L2 , et 10 fois plus lent s'il y a un échec de cache L2 et il doit être récupéré à partir d' un cache L3 , si cadeau.
  • La mémoire physique principale est le plus souvent implémentée en RAM dynamique (DRAM). La mémoire principale est beaucoup plus grande (généralement des gigaoctets contre ≈8 mégaoctets ) qu'un cache de processeur L3, avec des latences de lecture et d'écriture généralement 10 à 100 fois plus lentes. Depuis 2018, la RAM est de plus en plus implémentée sur la puce des processeurs, sous forme de mémoire CPU ou GPU .
  • La mémoire virtuelle est le plus souvent implémentée en termes de stockage secondaire tel qu'un disque dur , et est une extension de la hiérarchie de mémoire qui a un espace de stockage beaucoup plus grand mais une latence beaucoup plus grande, généralement environ 1000 fois plus lente qu'un manque de cache pour une valeur en RAM . Bien qu'à l'origine motivée pour créer l'impression de quantités de mémoire plus élevées que celles réellement disponibles, la mémoire virtuelle est plus importante dans l'utilisation contemporaine pour son compromis espace-temps et pour permettre l'utilisation de machines virtuelles . Les défauts de cache de la mémoire principale sont appelés défauts de page et entraînent d'énormes pénalités de performances sur les programmes.

Un algorithme dont les besoins en mémoire vont tenir dans la mémoire cache sera beaucoup plus rapide qu'un algorithme qui tient dans la mémoire principale, qui à son tour sera beaucoup plus rapide qu'un algorithme qui doit recourir à la mémoire virtuelle. Pour cette raison, les politiques de remplacement du cache sont extrêmement importantes pour le calcul hautes performances, tout comme la programmation prenant en compte le cache et l'alignement des données . Pour compliquer davantage le problème, certains systèmes ont jusqu'à trois niveaux de mémoire cache, avec des vitesses effectives variables. Différents systèmes auront différentes quantités de ces différents types de mémoire, de sorte que l'effet des besoins en mémoire de l'algorithme peut varier considérablement d'un système à l'autre.

Au début de l'informatique électronique, si un algorithme et ses données ne rentraient pas dans la mémoire principale, l'algorithme ne pouvait pas être utilisé. De nos jours, l'utilisation de la mémoire virtuelle semble fournir beaucoup de mémoire, mais au détriment des performances. Si un algorithme et ses données tiennent dans la mémoire cache, alors une très grande vitesse peut être obtenue ; dans ce cas, minimiser l'espace aidera également à minimiser le temps. C'est ce qu'on appelle le principe de localité , et peut être subdivisé en localité de référence , localité spatiale et localité temporelle . Un algorithme qui ne rentre pas complètement dans la mémoire cache mais qui présente une localité de référence peut fonctionner raisonnablement bien.

Critique de l'état actuel de la programmation

L'efficacité du logiciel diminue de moitié tous les 18 mois, compensant la loi de Moore

May poursuit en déclarant :

Dans les systèmes omniprésents, la réduction de moitié des instructions exécutées peut doubler la durée de vie de la batterie et les grands ensembles de données offrent de grandes opportunités pour de meilleurs logiciels et algorithmes : la réduction du nombre d'opérations de N x N à N x log(N) a un effet dramatique lorsque N est grand ... pour N = 30 milliards, ce changement équivaut à 50 ans d'améliorations technologiques.

  • L'auteur de logiciels Adam N. Rosenburg dans son blog " L'échec de l'ordinateur numérique ", a décrit l'état actuel de la programmation comme se rapprochant de " l'horizon des événements logiciels " (faisant allusion à l'" horizon des événements de chaussures " fictif décrit par Douglas Adams dans son Guide de l'auto-stoppeur du livre Galaxy ). Il estime qu'il y a eu un facteur de perte de productivité de 70 dB ou « 99,9999% de sa capacité à livrer la marchandise », depuis les années 1980—« quand Arthur C. Clarke a comparé la réalité de l'informatique en 2001 à l'ordinateur HAL 9000 dans son livre 2001: A Space Odyssey , il a souligné à quel point les ordinateurs étaient merveilleusement petits et puissants, mais à quel point la programmation informatique était devenue décevante".

Concours des meilleurs algorithmes

Les concours suivants invitent les candidatures pour les meilleurs algorithmes sur la base de certains critères arbitraires décidés par les juges :

Voir également

Les références

Liens externes