Dans quels domaines de la programmation le temps d'exécution des algorithmes est-il réellement un problème important?

Parfois, j'entends des gens dire qu'en raison de la vitesse des processeurs et de la quantité de mémoire disponible, l'efficacité des algorithmes et le temps d'exécution ne sont pas, dans la pratique, une préoccupation majeure.

Mais j'imagine qu'il y a encore des domaines où de telles considérations restent d'une importance capitale. Deux qui me viennent à l'esprit sont le trading algorithmique, où des milliers de transactions doivent être effectuées en quelques fractions de seconde, et la programmation de systèmes embarqués, où la mémoire et la puissance sont souvent rares. Ai-je raison sur ces exemples? et quels autres domaines seraient également des exemples?

La vitesse est toujours demandée. Je suppose que vous avez raison. Voici quelques exemples où des algorithmes soignés sont demandés:

1. Cryptographie

2. Recherche de grandes bases de données

3. Tri et fusion

4. Recherche de texte (non indexée), y compris les caractères génériques

5. Problèmes mathématiques avec calculs intensifs

6. Simulation

7. Applications d'exploration de données

8. Animation

9. AI

10. Vision par ordinateur

Dans certains cas, l'exécution de l'algorithme peut ne pas être un problème, car nous en sommes arrivés au point que vous pouvez simplement passer à travers un algorithme plus long avec un matériel plus puissant. Mais il y a certainement des endroits où les accélérations sont essentielles.

De manière générale, tout ce qui utilise d'énormes ensembles de données sera un problème. Lorsque vous avez quelque chose qui évolue mal avec n, et que vous faites un nombre vraiment énorme, vous avez un problème. Je soupçonne que si vous accédiez au site bêta de Computational Science et que vous passiez un peu de temps, vous pourriez trouver de nombreux problèmes nécessitant des algorithmes meilleurs et plus rapides. Quelques domaines que j'ai rencontrés:

• Analyse statistique particulièrement complexe. Une combinaison d'algorithmes inefficaces et de grands ensembles de données peut entraîner des ralentissements massifs. Pour certaines études, cela pourrait ne pas avoir d'importance, mais que se passe-t-il si vous essayez de faire quelque chose avec un retournement rapide? «Il se détachera du serveur dans un mois» est probablement une mauvaise chose lorsque vous utilisez un système de surveillance des menaces chimiques / nucléaires / biologiques.
• Exploration de données sur de grands ensembles de données.
• Simulations impliquant de nombreuses variables.

De manière générale, le calcul scientifique semble généralement être un domaine où la complexité de ce qui est programmé génère des opportunités de ralentissements sérieux si votre algorithme est lent (beaucoup d'entre eux souffrant de n très grands). Et, comme vous l'avez mentionné, il y a des applications financières. Lorsque les millisecondes peuvent déterminer si vous gagnez ou perdez de l'argent sur un métier, les algorithmes "assez bons" ne vont pas le couper s'il y a quelque chose de mieux qui peut être fait.

Parfois, j'entends des gens dire qu'en raison de la vitesse des processeurs et de la quantité de mémoire disponible, l'efficacité des algorithmes et le temps d'exécution ne sont pas, dans la pratique, une préoccupation majeure.

Prenez-le avec un grain de sel. Plus de puissance de calcul signifie simplement que votre n peut devenir beaucoup plus grand avant de ralentir considérablement. Pour la plupart des problèmes quotidiens, ce n est maintenant suffisamment grand pour que vous n'ayez pas besoin de vous en soucier. Cependant, vous devez toujours connaître la complexité de vos algorithmes.

Avec plus de ressources disponibles, il peut être nécessaire de récupérer plus de données ultérieurement. Aujourd'hui, vous devez analyser un fichier journal de 10 Mo avec 100 000 lignes. En un an, vous pouvez avoir un fichier journal de 100 Go avec 1 000 000 000 de lignes. Si la quantité de données croît plus rapidement que la puissance des ressources, vous rencontrez des problèmes plus tard.

Avec plus de ressources disponibles, plus de couches sont empilées les unes sur les autres. OS, framework OS, framework tiers, interprète de langue, et enfin sur votre propre outil. Toutes les inefficacités inutiles dans toutes les différentes couches se multiplient. Demain, votre outil peut fonctionner sur un nouvel OS avec plus de cloches et de sifflets, qui lui-même mange plus de cycles et plus de mémoire, vous en laissant moins.

Donc, pour répondre à votre question, vous devez toujours vous soucier où de plus en plus de données doivent être croisées (suffisamment d'exemples donnés dans les autres réponses), et où vous ne fournissez pas l'outil final, mais une autre couche d'abstraction pour d'autres outils.

Il y a quelques années, j'ai dû écrire un algorithme qui triait les tubes à essai disposés sur des nracks en deux partitions distinctes: c'est-à-dire qu'un sous-ensemble des tubes était «choisi» et les autres étaient «non choisis» et le résultat final serait qu'aucun rack aurait à la fois un tube «choisi» et «non choisi» (il y avait des exigences supplémentaires telles que la compression). Chaque portoir contenait un maximum de 100 tubes.

L'algorithme devait être utilisé pour piloter un robot de tri de tubes dans un laboratoire pharmaceutique.

Lorsque la spécification originale m'a été donnée, j'ai eu environ 1 minute de temps de calcul pour trier environ 2000 tubes, car nous pensions que la convivialité n'était pas trop douloureuse. Il était nécessaire que le nombre de mouvements soit minimal sur toutes les combinaisons possibles car le robot lui-même était lent .

L'hypothèse implicite était que la complexité serait exponentielle avec le nombre de tubes. Cependant, en travaillant sur la conception de l'algorithme, j'ai découvert qu'il existe un O(n)algorithme rapide où nest le nombre de racks qui ont effectué un partitionnement optimal des tubes. Le résultat de cela était que le temps de tri de l'algorithme était instantané, de sorte que l'affichage du tri serait mis à jour en temps réel lorsque l'utilisateur configurait son opération de tri.

Pour moi, la différence entre l'utilisateur assis pendant une minute après chaque changement et ayant une interface graphique immédiatement réactive était la différence entre un logiciel qui était fonctionnellement suffisant et un logiciel qui était un plaisir à utiliser.

Les autres domaines comprennent de nombreux types de traitement du signal en temps réel, les systèmes de contrôle de rétroaction, la déconvolution d'exploration pétrolière, la compression vidéo, le traçage des rayons et le rendu des images de film, les systèmes de réalité virtuelle, les jeux où la fréquence d'images élevée peut être un avantage concurrentiel important, et les smartphones et autres les applications pour appareils mobiles, où un grand nombre de cycles de processeur consommera plus rapidement la batterie des utilisateurs

Je suis assez surpris que cette question soit même posée, car pour tout supercalculateur Top 500 jamais construit, il y a probablement une liste d'attente de chercheurs qui peuvent le maximiser et souhaiter des puissances de calcul plus importantes ou de meilleurs algorithmes pour résoudre certains problèmes (pliez des protéines pour déchiffrer le cancer, etc.) avant de prendre votre retraite.

Je pense que les moteurs de recherche comme Google et Bing sont l'un des plus grands domaines où des algorithmes complexes sont utilisés et ils jouent un rôle clé dans l'accélération des résultats avec pertinence (classement des pages) apportant plus d'utilité aux utilisateurs.

L'efficacité des algorithmes n'est pas une préoccupation majeure de nos jours car nous utilisons des algorithmes efficaces. Si vous utilisiez un algorithme O (n!), Il serait lent sur tout type de matériel.

La complexité des algorithmes devient de plus en plus importante à mesure que la quantité de données augmente. Heureusement, des solutions génériques efficaces pour les problèmes de programmation courants (recherche et tri, principalement) sont incluses dans à peu près toutes les bibliothèques standard du langage de programmation moderne, donc normalement, un programmeur n'a pas à se soucier de ces choses. L'inconvénient est que de nombreux programmeurs ne savent pas du tout ce qui se passe sous le capot et quelles sont les caractéristiques des algorithmes qu'ils utilisent.

Cela devient particulièrement problématique car de nombreuses applications ne sont pas testées correctement: les gens écrivent du code qui fonctionne bien pour de petits ensembles de données de test, mais lorsqu'ils sont confrontés à quelques milliers de fois plus de données, le code s'arrête. Quelque chose qui fonctionne bien pour dix enregistrements explose rapidement lorsque l'ensemble de données s'agrandit. Exemple réel: un morceau de code qui était censé nettoyer les éléments qui n'étaient plus liés à aucune catégorie utilisait une boucle imbriquée à trois niveaux, qui est O (n ^ 3). Avec seulement 10 enregistrements dans la base de données de test, cela signifiait 1000 contrôles - parfaitement faisables, et n'introduit pas de retard notable. Cependant, la base de données de production s'est rapidement remplie d'environ 1000 lignes, et soudain, le code effectue un milliard de vérifications à chaque fois.

Donc: Non, vous n'avez pas besoin de connaître les tenants et aboutissants de la mise en œuvre de toutes sortes d'algorithmes soignés, et vous n'avez pas besoin d'être en mesure d'inventer les vôtres, mais vous avez besoin de quelques connaissances de base sur les algorithmes courants, ce que leurs les points forts et les points faibles sont, quand et quand ne pas les utiliser, et vous devez être conscient de l'impact possible de la complexité algorithmique, afin de pouvoir décider quel niveau de complexité est acceptable.

Il ne s'agit pas de savoir quels domaines d'application sont sensibles à l'exécution. N'importe quel programme, où qu'il se trouve, a une performance minimale en dessous de laquelle il est effectivement sans valeur. Le point de complexité de l'algorithme est de savoir comment il varie avec l'augmentation de la taille d'entrée. En d'autres termes, les domaines où la vitesse est particulièrement importante sont ceux où vous vous attendez à devoir évoluer au-delà non seulement de la taille actuelle de votre problème, mais de l' ordre de grandeurde la taille actuelle de votre problème. Si vous traitez les demandes fiscales des citoyens d'un département de la France, la tâche peut être importante, mais il est peu probable que la taille de la population ou la complexité du traitement d'un enregistrement augmente jamais de dix à cent fois, donc tout ce qui fonctionne pour maintenant, vous continuerez probablement à travailler. Mais si vous essayez de créer quelque chose qui va décoller à des volumes d'Internet, algorithme de complexité est la clé: tout ce qui dépend plus de façon linéaire ou log-linéaire de la taille d'entrée sera devenu beaucoup plus cher très rapide, et finalement la vitesse du processeur ne peux pas suivre la croissance.

Dans mon domaine (VFX, qui couvre des choses comme le traçage de chemin, l'animation par ordinateur, la simulation de particules, la dynamique des fluides, le traitement d'image, etc.), la complexité algorithmique est fondamentale. Il n'y a aucun moyen que quelque chose de pire que le temps linéithmique puisse espérer se terminer en un temps raisonnable sur des entrées qui atteignent généralement des millions de sommets, polygones, voxels, particules, texels, en particulier lorsque beaucoup de ces choses doivent se terminer plusieurs fois par seconde pour fournir rétroaction interactive en temps réel.

Cela dit, l'accent mis sur la complexité algorithmique n'est généralement pas si fort dans les discussions entre collègues, peut-être parce qu'il est quelque peu tenu pour acquis et plutôt "rudimentaire". On suppose généralement, si vous écrivez un traceur de chemin, qu'il fonctionnera en temps logarithmique ou mieux, et que les structures de données telles que les hiérarchies de volumes limites sont familières et relativement triviales à mettre en œuvre pour le lecteur. J'ai même eu un collègue qualifié qui n'arrêtait pas de dire que le multithreading et la SIMD sont plus importants que les algorithmes, et je ne pense pas qu'il voulait dire cela dans le sens où vous pouvez vous attendre à tirer le meilleur parti de la parallélisation d'un type de bulles. Je pense qu'il a dit que parce qu'il tenait pour acquis que nous appliquerions des algorithmes sensés,

Souvent, ces derniers temps, l'accent est mis sur la prise d'un grand nombre de ces algorithmes familiers et sur leur meilleure exploitation des caractéristiques sous-jacentes du matériel comme le cache du processeur, les registres et instructions SIMD, les GPU et les cœurs multiples. Par exemple, Intel a trouvé une nouvelle façon de prendre le vieux BVH familier et de proposer le concept de "paquets de rayons", testant essentiellement plusieurs rayons cohérents à la fois avec une sorte récursive de traversée d'arbre (qui pourrait ressembler à cela viendrait avec sa part de complexité et de surcharge, sauf qu'il est plus que compensé par le fait que ces rayons peuvent désormais être testés simultanément pour les intersections rayon / AABB et rayon / triangle via des instructions et registres SIMD).

Une chose similaire avec comme la subdivision catmull-clark, qui est très rudimentaire en infographie. Mais de nos jours, ce qui est compétitif, chaud et super efficace, ce sont les implémentations GPU qui se rapprochent de la subdivision CC en utilisant les correctifs Gregory, popularisés par Charles Loop et adoptés plus tard par Pixar. L'implémentation plus simple du CPU est maintenant plutôt obsolète, pas nécessairement parce qu'elle a été remplacée en termes de complexité algorithmique, mais parce qu'elle a été remplacée par quelque chose qui fonctionne bien avec le GPU.

Et c'est généralement une grande partie du défi de nos jours n'est pas de trouver le meilleur algorithme d'une manière qui soit relativement indépendante des caractéristiques sous-jacentes du matériel. En fait, j'ai mis le pied dans l'industrie en proposant une nouvelle structure d'accélération qui a considérablement accéléré la détection des collisions pour les personnages animés et autres corps mous dans les années 90 en utilisant une approche de segmentation hiérarchique par opposition à un indice spatial, ce qui m'a procuré beaucoup de offres d'emploi, mais de nos jours ce n'est plus si impressionnant depuis que je l'ai publié bien avant que nous ayons des caches CPU et des cœurs multiples et des GPU programmables aussi impressionnants et ainsi de suite, et aujourd'hui j'utilise une approche complètement différente en raison des changements importants apportés à la matériel sous-jacent.

Une fois, j'ai rencontré un problème où un algorithme fonctionnait généralement en O (n), mais dans des circonstances rares et extrêmement improbables, il faudrait du temps O (n ^ 3) - les circonstances "rares" étaient un répertoire contenant des fichiers avec des noms valides dans un système d'exploitation mais pas dans un autre.

Personne n'a jamais rencontré de problèmes. Ensuite, un client a utilisé une stratégie pour nommer les fichiers qui s'exécuteraient systématiquement dans le cas O (n ^ 3), et avec quelques 100 fichiers, le système s'est immobilisé virtuellement. Le résultat a été que l'algorithme a dû être changé.

Trois autres qui n'ont pas été mentionnés:

1) De nombreux jeux de stratégie en temps réel. Regardez ceux qui ont des unités qui ne peuvent pas partager une position. Observez ce qui arrive à la recherche de chemin lorsqu'un grand groupe d'unités se déplace sur un terrain restreint. Je n'ai pas encore rencontré de jeu sans aucun problème substantiel avec cela car il n'y a tout simplement pas assez de puissance CPU disponible.

2) Beaucoup de problèmes d'optimisation. (Edit: depuis que j'ai écrit cette réponse, j'en ai frappé une. Mon objectif était d'élaguer les chemins redondants afin de laisser tous les nœuds connectés avec le poids minimum des chemins de connexion. à cette routine, alors j'ai réalisé que c'était 2 ^ n. Maintenant c'est n ^ 2 même si cela peut parfois produire un résultat légèrement non optimal.)

3) Les choses qui doivent fonctionner sur de grandes quantités de données en temps réel. Considérez un DVD: vous obtenez généralement 2 heures de vidéo en 4,7 Go. Considérez un fichier vidéo typique à la même résolution: ces 2 heures de vidéo seront généralement inférieures à 1 Go. La raison en est que lorsque les spécifications DVD ont été établies, vous ne pouviez pas créer un lecteur DVD à un prix raisonnable qui pourrait décoder les formats les plus modernes assez rapidement.

Eh bien, toute application qui s'exécute généralement sur un supercalculateur ( liste des plus grandes machines ) est éligible. Celles-ci sont diverses, mais une grande sous-classe d'entre elles sont les simulations physiques:

• Simulations physiques:
  • Prévisions météorologiques
  • Simulations climatiques
  • Simulations d'étoiles qui explosent, etc.
  • Simulations d'explosions d'armes nucléaires
  • Simulations aérodynamiques de voitures / avions / trains etc.
  • ...
• Calcul d'images à partir de données de radiotélescopes
• Applications biologiques:
  • Des trucs avec des séquences d'ADN (je ne suis pas vraiment dedans)
  • Des trucs biochimiques comme le repliement des protéines
  • Simulations de la façon dont les cellules nerveuses fonctionnent ensemble pour traiter l'information
  • Simulations d'autres interactions complexes comme les écosystèmes
  • ...
• ...

Ce ne sont que les sujets principaux de ma tête, mais il suffit de lire la liste des différents supercalculateurs et de réaliser que chacun d'entre eux est conçu pour permettre une ou plusieurs sortes de calculs qui ne seraient pas possibles sans de telles machines gigantesques.

Et, une fois que vous voyez que nous avons réellement besoin de ces machines, réalisez combien vous pouvez économiser, simplement en accélérant ces applications de 10% . Toute optimisation de ces codes augmente directement la quantité de résultats que nous pouvons obtenir de ces machines.