Discussion :

[saou88]

Salut tout le monde,
Ma question semblerait peut -être un peu bizarre ou peut être fera-t-il un sens pour certains.
En fait, je veux m'assurer du fait qu'il y ait ou pas une différence entre la complexité de calcul qu'engendrerait un algorithme et puis son implémentation sur machine. Par exemple, si deux algo ont une même complexité de calcul, l'un peut-il avoir une caractéristique d'être plus facile à implémenter?

PS. J'ai trouvé cette remarque dans un article, mais elle est brève sans aucune explication et je tiens à m'assurer de sa validité.

Merci.

[FR119492]

Salut!

différence entre complexité de calcul et complexité d'implémentation

Je ne connaissais pas ces deux termes, mais je peux te raconter une expérience que j'ai faite il y a quelques années: j'avais fait un programme pour chronométrer le temps nécessaire pour factoriser une matrice et le représenter en fonction de la taille de la matrice. Théoriquement, la complexité de l'algorithme utilisé était telle que le graphe aurait dû être une cubique. En réalité, c'était loin d'être le cas. D'une part, il y avait une forte dispersion: pour la même matrice, on trouvait des temps assez différents, probablement parce que le processeur de mon ordinateur faisait d'autres choses en même temps. D'autre part, le graphe présentait une discontinuité inattendue; je suppose qu'elle provenait du fait qu'à partir d'une certaine taille il y avait des transferts de données vers le disque dur. Cette expérience m'a convaincu que la notion de complexité, en théorie, c'était très joli, mais qu'en pratique, ça ne servait pas à grand chose.
Jean-Marc Blanc

[kwariz]

[...] Cette expérience m'a convaincu que la notion de complexité, en théorie, c'était très joli, mais qu'en pratique, ça ne servait pas à grand chose.
Jean-Marc Blanc

Bonjour,

c'est comme tous les outils, mal utilisés ils sont inutiles. Utiliser «le bon algorithme» ne consiste pas uniquement à en regarder la compléxité asymptotique en temps.
Je prends le terme compléxité d'implémentation comme «la difficulté à implémenter un algorithme sur une plateforme particulière dans un langage particulier par une personne particulière.
Quand on décide de l'utilisation d'un algorithme c'est non seulement parce qu'il est adapté au problème à résoudre, aux données réelles qu'il va devoir traiter mais aussi parce qu'on dispose de structures de données adaptées, des connaissances suffisantes pour le faire, de suffisamment de temps pour le faire (que l'on soit seul ou que l'on travaille en équipe).
Essayer d'utiliser à chaque instant et à tout endroit l'algorithme de meilleure complexité est en soi un hérésie (à mon sens) cela amène souvent à un code spaghetti, une usine à gaz non maintenable quand (enfin si) ça fonctionne.

[pseudocode]

Cette expérience m'a convaincu que la notion de complexité, en théorie, c'était très joli, mais qu'en pratique, ça ne servait pas à grand chose.

En pratique, ca a permis de montrer que:
1. la complexité serait "au mieux" cubique.
2. le hardware/software était un facteur limitant pour atteindre les performance attendues.

Pas si mal pour un truc qui ne sert pas a grand chose.

[Aleph69]

Bonjour,

Par exemple, si deux algo ont une même complexité de calcul, l'un peut-il avoir une caractéristique d'être plus facile à implémenter?

Ta question n'a pas de sens tant que tu n'as pas rigoureusement défini une relation d'ordre entre deux algorithmes du type "algo A est plus facile à implémenter que algo B". La notion de facilité d'implémentation est bien trop subjective. Si tu devais réellement implémenter un algorithme de A à Z, c'est-à-dire sans utiliser aucune bibliothèque standard, extérieure ou aucune fonction prédéfinie d'aucun langage, tu n'y arriverais peut-être même pas dans la plupart des cas. J'entends par là que la facilité d'implémentation que tu évoques dépend du niveau d'implémentation où tu te places. Un algorithme pourra te sembler très facile à implémenter à un haut niveau alors que tu aurais trouvé l'implémentation des fonctions bas niveau trop difficiles à ton goût.

[davcha]

Bonjour,



Ta question n'a pas de sens tant que tu n'as pas rigoureusement défini une relation d'ordre entre deux algorithmes du type "algo A est plus facile à implémenter que algo B". La notion de facilité d'implémentation est bien trop subjective. Si tu devais réellement implémenter un algorithme de A à Z, c'est-à-dire sans utiliser aucune bibliothèque standard, extérieure ou aucune fonction prédéfinie d'aucun langage, tu n'y arriverais peut-être même pas dans la plupart des cas. J'entends par là que la facilité d'implémentation que tu évoques dépend du niveau d'implémentation où tu te places. Un algorithme pourra te sembler très facile à implémenter à un haut niveau alors que tu aurais trouvé l'implémentation des fonctions bas niveau trop difficiles à ton goût.

Tu supposes que la dérivée de ta fonction d'ordre par rapport au niveau d'implémentation (comme tu dis) change en fonction de l'algorithme, là...

Prise de tête tout ça.

Je pense qu'on pouvait répondre : oui, il existe une différence, dans la mesure où la notion de "complexité de calcul" (temporelle ou spatiale) est différente de la notion de difficulté d'implémentation qui est de toute façon subjective.

[Aleph69]

Salut davcha,

Tu supposes que la dérivée de ta fonction d'ordre par rapport au niveau d'implémentation (comme tu dis) change en fonction de l'algorithme, là...

Je ne comprends pas le sens de ta phrase. Qu'appelles-tu une fonction d'ordre?

Je pense qu'on pouvait répondre : oui, il existe une différence, dans la mesure où la notion de "complexité de calcul" (temporelle ou spatiale) est différente de la notion de difficulté d'implémentation qui est de toute façon subjective.

Sauf erreur de ma part, tu as écrit : "il existe une différence entre A et B parce que A est différent de B".

Il est nécessaire de définir clairement de quoi on parle pour pouvoir prouver le vrai ou le faux. Sans quoi, on aboutit à des affirmations qui peuvent apparaître à première vue évidentes mais qui sont finalement dépourvues de sens.

[kwariz]

Bonjour,

Le premier message est confus car on peut l'interpréter de manière différente. La première vient de la partie :

En fait, je veux m'assurer du fait qu'il y ait ou pas une différence entre la complexité de calcul qu'engendrerait un algorithme et puis son implémentation sur machine.

Que l'on peut interpréter comme : si on a un algo en O(f(n)) est-on certain que son implémentation sera réellement en O(f(n)), c'est-à-dire si on crée un graphique du genre [taille entrée]/[temps effectivement pris pour la résolution]
alors ce graphique aura-t-il bien la bonne forme prédite ?
La réponse est à la fois oui et non.
Le non s'explique simplement. Quand on étudie la complexité algorithmique d'un algo, celle-ci donne un comportement asymptotique. Mais ce qui est important est de remarquer que la compleité algorithmique considère, par exemple, que l'accès mémoire se fait en temps constant quelle que soit la taille d'un tableau. Ce qui dans les faits est totalement faux. Autant on peut considérer le temps d'accès en RAM constant dans une certaine mesure, autant il y a des mécanisme qui soit font que l'accès est plus rapide (mémoire cache, lecture de données proches ou peu de données => plus rapide), soit font que l'accès est plus lent (beaucoup de données, accès à des données éloignées => plus lent). Donc le graphique va certainement présenter des sauts.
Ce n'est qu'un exemple, j'aurai pu aussi citer la difficulté de chronométrer précisément le temps d'exécution, ou les optimisations des compilos ou même des différences entre langage (c=lecture d'un tableau par ligne, fortran=lecture d'un tableau par colonnes).
Non aussi pour des raisons non physiques : si on essaye de créer un graphe de performances de quicksort on ne verra pas une courbe mais un nuage de points délimité par deux courbes (cas favorable en n.lg n et cas défavorable en n).
Enfin la partie oui, car dans les morceaux où les hypothèses comme temps d'accès constant sont vraies alors oui, la courbe aura bien la bonne forme.
Une étude de complexité n'est pas juste un exercice, c'est une donnée utile.

Tout ce que j'ai dit sur la complexité en temps est tout aussi valable en complexité en espace.



La seconde interprétation vient de la question qui suit :

Par exemple, si deux algo ont une même complexité de calcul, l'un peut-il avoir une caractéristique d'être plus facile à implémenter?

Ici le PO parle de "plus facile" à implémenter. Comme ça a été dit, la difficulté à implémenter est très subjective et très dépendante de l'environement d'implémentation, de celui qui inplémente, mais aussi de celui qui a écrit l'algo en fin de compte.
Une personne qui a l'habitude du C ne produira pas généralement le même type de pseudo code que quelqu'un qui a l'habitude de Matlab par exemple.
Les notations seront forcément teintées par le background de celui qui écrit.

Mais peut-être le PO confond-il les deux notions : complexité d'un algo = difficulté à l'écrire : ce qui est totalement faux.

PS. J'ai trouvé cette remarque dans un article, mais elle est brève sans aucune explication et je tiens à m'assurer de sa validité.

Merci.

Peut-être pourrais-tu nous donner les références de cet article (ou à défaut nous écrire le passage)


PS: en relisant je remarque que l'exemple de quicksort est un vrai bon mauvais exemple. En effet lorsqu'on donne une complexité d'un algo de tri par comparaisons cette conplexité mesure le nombre de comparaisons ...

[Franck Dernoncourt]

FYI http://www.developpez.net/forums/sea...archid=8628225

[Invité]

Le non s'explique simplement. Quand on étudie la complexité algorithmique d'un algo, celle-ci donne un comportement asymptotique. Mais ce qui est important est de remarquer que la compleité algorithmique considère, par exemple, que l'accès mémoire se fait en temps constant quelle que soit la taille d'un tableau. Ce qui dans les faits est totalement faux.

Ce genre de choses peut être pris en compte dans les calculs de complexités asymptotiques. Aujourd'hui, on sait évaluer le nombre de cache miss/page miss effectués par un programme, et en déduire une complexité. Et on peut même créer des algorithmes de haut niveau qui cherchent à diminuer au maximum ces complexités. Ça s'appelle des cache oblivious algorithms. Donc, d'un point de vue formel, les accès mémoires en eux-mêmes ne changent pas la complexité asymptotique d'un algorithme. On se retrouve simplement avec deux complexités : une qui mesure le nombre d’opérations arithmétiques, et une autre pour les caches miss : il suffit de prendre la plus grande pour obtenir la bonne complexité.

Après, il y a bien des trucs qui vont venir perturber ce beau monde : les divers mécanismes de data prefetching peuvent faire varier les complexités asymptotiques de certains codes, du moins pour la complexité en cache/page miss. Mis pour être franc, c'est rare, et à part quelques cas simples (itération dans un tableau), je n'ai pas d'exemples. Il faut dire qu'à part dans des algorithmes dans lesquels on pré-calcule beaucoup de choses, il est rare d'avoir une complexité asymptotique bornée supérieurement par la complexité en cache miss et pas par la complexité des opérations arithmétiques.

[FR119492]

Bonjour à tous!
Ce qui compte réellement, lorsqu'on choisit un algorithme, c'est seulement le temps que le programme prendra pour effectuer les calculs, et la connaissance de la complexité des divers algorithmes peut nous donner des idées pour effectuer notre choix; par exemple, si on doit résoudre un système de 10'000 équations à 10'000 inconnues, on ne choisira pas la méthode de Sarrus. Mais on ne choisira pas non plus celle de Strassen, bien que sa complexité soit inférieure à celle des méthodes "classiques". D'autre part, la méthode de Cholesky est presque deux fois plus rapide que celle de Gauss-Jordan, bien qu'elle ait la même complexité.
Un autre problème est aussi significatif: remplir une matrice de très grande taille: en Fortran, ça va plus vite si on la parcourt colonne par colonne, alors qu'en C, il vaut mieux le faire ligne par ligne. Alors, quel rôle joue la complexité?
Jean-Marc Blanc

[Aleph69]

Bonjour à tous!
Ce qui compte réellement, lorsqu'on choisit un algorithme, c'est seulement le temps que le programme prendra pour effectuer les calculs

... et la stabilité comme tu l'as implicitement souligné avec l'exemple de l'algorithme de Strassen!

D'autre part, la méthode de Cholesky est presque deux fois plus rapide que celle de Gauss-Jordan, bien qu'elle ait la même complexité.

En fait si tu regardes la constante devant le terme en n^3, tu trouveras respectivement 1/3 et 2/3, ce qui explique ta remarque.

Un autre problème est aussi significatif: remplir une matrice de très grande taille: en Fortran, ça va plus vite si on la parcourt colonne par colonne, alors qu'en C, il vaut mieux le faire ligne par ligne. Alors, quel rôle joue la complexité?

Cela rejoint l'intervention de mewtow (très intéressante au passage) : tout dépend de la manière dont tu calcules la complexité. En général, on fait beaucoup d'hypothèses simplificatrices mais libre à toi de ne pas les faire.

[kwariz]

[...]
Cela rejoint l'intervention de mewtow (très intéressante au passage) : tout dépend de la manière dont tu calcules la complexité. En général, on fait beaucoup d'hypothèses simplificatrices mais libre à toi de ne pas les faire.

Ce ne sont pas des hypothèses simplificatrices mais des modèles (machine RAM ou machine de Turing, ou d'autres encores). La différence c/fortran est une différence d'implémentation pas de modèle à proprement parler.

[kwariz]

Bonjour à tous!
Ce qui compte réellement, lorsqu'on choisit un algorithme, c'est seulement le temps que le programme prendra pour effectuer les calculs,

On ne choisit pas un algo, on choisit d'implémenter un algo et tout ce qui va avec (entre autre les structures adaptées) pour obtenir le résultat escompté (car l'algo a été vérifé formellement : il est correct, il termine, etc ..). Le souci d'avoir une version rapide n'est jamais obligatoire, on peut aussi se soucier de minimiser d'autres ressources que le temps (la mémoire, les accès coûteux à des ressources externes, tout dépend de ce qu'on mesure).

et la connaissance de la complexité des divers algorithmes peut nous donner des idées pour effectuer notre choix; par exemple, si on doit résoudre un système de 10'000 équations à 10'000 inconnues, on ne choisira pas la méthode de Sarrus. Mais on ne choisira pas non plus celle de Strassen, bien que sa complexité soit inférieure à celle des méthodes "classiques". D'autre part, la méthode de Cholesky est presque deux fois plus rapide que celle de Gauss-Jordan, bien qu'elle ait la même complexité.

Tu parles d'implémentations pas d'algorithmes. La complexité d'un algo est un outil théorique qui peut donner non seulement des indications d'utilisations mais aussi des contre indications. Après il s'agit parfois d'expérience et de savoir-faire. Il est tout autant ridicule de vouloir toujours utiliser heapsort pour trier un tableau sous prétexte qu'il a le meilleur comportement même dans le pire des cas et pour justifier par là même qu'on ne peut faire mieux vu qu'on a utilisé le meilleur algo de dispo.

Un autre problème est aussi significatif: remplir une matrice de très grande taille: en Fortran, ça va plus vite si on la parcourt colonne par colonne, alors qu'en C, il vaut mieux le faire ligne par ligne. Alors, quel rôle joue la complexité?
Jean-Marc Blanc

À nouveau il s'agit de problèmes d'implémentations, donc ici la complexité algorithmique ne joue aucun rôle particulier : peu importe les diff de perf entre c/ligne fortran/colonne l'algo aura toujours le même comportement.