Version imprimable
Bonjour,
pourriez vous m'expliquer ou m'indiquer un site (ou un pdf ou un tutoriel...) qui explique comment calculer la complexité en espace d'un Algorithme ou d'un code source. Ou meme carrément s'il existe un logiciel pour calculer ca.
C'est peut etre des question un peu cons mais je n'ai jamais aborder le sujet de la complexite espace donc soyez indulgents...
En juste quelques mots, la complexité en espace est la quantité de mémoire dont a besoin un algorithme pour pouvoir être exécuté en fonction de la taille de l'entrée.
Par exemple, pour faire un tri de n entiers, la taille de l'entrée est proportionnelle à n (soit kn, où k est une constante). Pour faire tous les calculs, on a besoin de stocker les entiers mais aussi de quelques variables auxiliaires. La complexité en taille est donc kn+k'. En général, comme pour la complexité en temps, on utilise les notations en grand O: l'entrée est en O(n) et la complexité en mémoire est en O(n). La complexité en temps est, selon en O(n^2) ou en O(n logn) selon l'algo.
Je savais ce qu'etait la complexité en espace je ne sais juste pas comment la calculer pour un programme donné...
Ca se calcule de la même facon que la complexité en temps, à part qu'au lieu de comptabiliser les opérations, tu comptabilises chaque allocation de mémoire (en gros chaque fois que tu fais apparaitre une nouvelle variable dans ton code). Bien sur, il te faut savoir la taille occupée par chacun de tes types (types de base et types complexes). Evidemment, desfois la taille de tes nouvelles structures dépend de la valeur d'une variable de ton code: il faut alors, soit faire une analyse dans le pire des cas, soit en moyenne.
Comme pour la complexité en temps, il n'y a pas une méthode systématique mais on utilise très souvent quelques règles récurrentes. On se concentre uniquement sur les structures de données, les variables simples (entiers, booléens, flottants) sont en général négligés car ils occupent un espace "constant" (qui ne dépend pas de l'entrée).
La taille des tableaux est simple à calculer: elle est en grand O du produit de ces dimensions. Un tableau à une dimension de n élément est en O(n), une matrice nxm est en O(nm), etc...
Les chaînes de caractères sont en grand O de leur longueur.
Le point délicat est quand il y a des structures dynamiques (listes, tas...) dans lesquelles différents éléments sont ajoutés et enlevés successivement. Il faut alors borner supérieurement le nombre d'éléments contenus dans la structure. Une borne simple est de compter le nombre d'ajouts potentiels et d'ignorer les suppressions mais, inversement, elle peut être de mauvaise qualité. Si on veut avoir une borne plus fine, il faut se baser sur les propriétés particulière de l'algorithme.
Il existe un algo de tri en O(n), le tri distribué.Citation:
Envoyé par FrancisSourd
Pour info ;)
Tu es sûr que ce n'est pas le "tri par casiers", plutôt ?Citation:
Envoyé par camboui
Sa complexité est O(m+n), "m" étant la cardinalité du domaine des entiers à trier (=65536 pour des entiers 16 bits, par exemple), mais ne marche que pour des trier des entiers...
Lien : http://www.dailly.info/algorithmes-de-tri/casier.php
Si je me souviens bien de mes cours, le tri en O(n) demande O(n) machines.Citation:
Envoyé par Mac LAK
Un résultat classique d'informatique théorique est qu'on ne peut pas faire mieux que O(n log n) quand on a une seule machine (cela correspond au log des n! possibilités de tris, en utilisant la formule de Stirling).
Ce n'est pas tout à fait vrai, le tri par casiers en est un bon exemple. Si tu dois trier N nombres entiers (N grand), mais faisant partie d'un domaine assez restreint (<= 16 bits), alors la composant "m" de la complexité devient négligeable, et aboutit à une complexité O(n).Citation:
Envoyé par FrancisSourd
Le piège, c'est que ça ne marche que pour des entiers... Même pas la peine de penser à l'adapter à une clé primaire, par exemple.
Va jeter un oeil sur l'algo, tu verras comment ça fonctionne, c'est très intéressant.
Il y a des similitudes, mais ce n'est pas tout à fait ça.Citation:
Envoyé par Mac LAK
De plus, il est généralisable. La preuve, je l'ai fait :P
Ce que j'ai implémenté s'appelle "tri distribué" :D
La complexité est O(256.p.n), p étant une quasi constante en pratique, en gros...
Exemple: des entiers de 32bits à trier.
Ils sont stockés en mémoire sur 4 octets, de l'octet de poids "fort" à l'octet de poids "faible".
Dans une première passe, on les trie suivant l'octet de poids fort qui peut prendre 256 valeurs. Ensuite on trie chaque sous-ensemble pré-trié par le 2ème octet, et ainsi de suite jusqu'au 4ème octet. "p" vaut 4 dans ce cas-ci.
Si on connait la répartition (toutes les valeurs <1000000 par exemple), une optimisation est possible en s'abstenant de trier par le premier octet (qui vaut alors toujours zéro). Dans certaines implémentations, j'ai même été plus loin en faisant des décalages bit à bit pour s'aligner sur le premier bit significatif.
C'est pareil pour une chaîne de caractères qui n'est qu'une suite d'octets, et donc de nombres dont on connait les bornes: de 0 à 255. On trie suivant le premier caractère, puis chaque sous-ensemble pré-trié suivant le caractère suivant, etc.
Le nombre de casiers (étant donné le nom que tu donnes "tri par casiers") est donc toujours 256.
Reste ce que j'appelle la profondeur "p". Elle est de maximum 4 pour des entiers de 32bits. Pour des chaînes de caractères, elle correspond à leur taille moyenne.
En pratique, je me suis toujours limité à une profondeur de 4 car en général c'est suffisant pour obtenir un tri "presque fini", quelque soit le type de tri. Je veux dire que les sous-ensembles restant à trier après cette prodondeur sont peu nombreux. Par ailleurs, j'ai aussi constaté que ce tri est surtout performant pour de très grands ensembles, moins pour des petits pour lesquelles j'utilise alors le qsort habituel. Je laisse ainsi qsort s'occuper des petits sous-ensembles pré-triés après une profondeur de 4. Je pense que cela est dû à l'accès séquentiel de l'implémentation que j'ai faite de ce tri (la mémoire adore les accès séquentiels, les disques aussi). Quand on fait des accès directs, il y a toujours une latence pénalisante; c'est le cas de qsort qui, je suppose, bénéficie alors de la mémoire cache sur des petits ensembles (la cache n'est pas très utile en accès séquentiel).
D'un point de vue théorique, j'imagine que la complexité est d'ordre O(n.p), p étant la profondeur et je me dis bien que cette profondeur est sans doute fonction de n et non pas constante, mais "faiblement" fonction de n. Donc pas tout à fait O(n) mais presque. Je laisse cette étude détaillée aux théoriciens ;)
Ce qui compte dans mes tris c'est qu'ils soient rapides, et je constate qu'ils le sont avec le tri distribué par rapport à qsort.
Donc, en résumant, on peut tout trier "par casiers" si on peut décomposer les éléments à trier en octets significatifs.
:arrow: camboui : Intéressante, ta méthode... Faudrait voir ce que ça donne sur des enregistrements avec clé primaire, par exemple, et si la complexité est réellement en O(n) ou pas (un facteur constant, même multiplicatif, est ignoré en complexité), ou si le facteur "p" est de l'ordre de O(log n)... Calculer la complexité moyenne et la complexité maximale serait également intéressant, histoire de voir si elles sont du même ordre ou pas.
Pour le tri par casiers, je ne sais pas si tu as remarqué, mais c'est en fait plus un "dénombrement trié" qu'un véritable tri, c'est la raison pour laquelle ça ne marche qu'avec des entiers...
Pour le calcul de complexité, prenons l'exemple des entiers.
Sur nos machines actuelles, les entiers sont bornés puisque limités à 32 bits. "p" vaut 4 au maximum, c'est une constante. Donc la complexité est bien O(n).
Sur une machine 64 bits, "p" vaudra 8, encore une constante, donc toujours O(n).
Idem si on à des nombres à virgule flotante. Les double sont codés sur 64 bits (déterminer l'octet le plus significatif est juste un peu plus compliqué).
Mais "p" est une constante parce que nos machines sont finies.
Sur une machine où les entiers ne seraient pas bornés, on voit bien que "p" dépend de la valeur la plus grande de l'ensemble à trier.
En prenant en exemple des chaines de caractères, "p" vaut, au pire, la taille de la chaine la plus longue. En général, cette taille est indépendante du nombre de chaines à trier. Donc encore une complexité O(n).
En pratique, dans nos situations quotidiennes, les éléments à trier se trouvent dans des limites qui sont "quasi" indépendantes de la quantité d'éléments. La valeur maximale de "p" pourra être déterminée et sera "presque" constante.
Dans un cadre strictement théorique, "p" semble quand même être dépendant de "n". Enfin, non. Il dépend plutôt de l'étendue (ou profondeur) des données, pas tellement de la quantité "n".
Mais si un jour on passe à 64 bits pour les entiers, c'est parce que les 32 bits ne suffiront plus. Le tout est de déterminer pourquoi il ne suffiront plus; parce qu'on a besoin d'énumérer plus de 4 milliards d'éléments (n) ou bien parce que l'étendue de valeurs de 1 jusque 4 milliards ne suffit (p)? Un peu des deux sans doute finalement...
Il faudrait également regarder l'aspect "consommation mémoire" de ton algo, pour rester un peu dans le topic initial... ;-)
N'oublie pas les Real*10 IEEE-754 (10 octets).Citation:
Envoyé par camboui
Mais tu ne connais pas cette taille à priori : donc, recherche de maximum. Suivant le type de chaîne, calculer toutes les longueurs peut être très long...Citation:
Envoyé par camboui
Vrai, mais que se pass-t-il lorsque toutes les chaînes n'ont pas la même longueur ? De plus, je ne suis pas certain que ton algorithme puisse gérer le tri lexicographique, c'est un peu particulier comme critère de comparaison...Citation:
Envoyé par camboui
Actuellement, c'est plus pour un problème d'adressage : lorsqu'il est facile et peu onéreux d'avoir une machine qui bouffe la moitié de son espace d'adressage en RAM, faut commencer à s'inquiéter... Or, des machines à 2 Go de RAM, ça devient relativement fréquent.Citation:
Envoyé par camboui
C'est vrai qu'on est un peu sorti du sujet initial.
Mais bon, on a un cas bien concret :D
Alors, pour la mémoire, en effet, il m'en faut un paquet. Il n'y a pas de "swap" entre deux éléments, mais placement direct de chaque élément au bon endroit. L'ensemble de départ doit donc être dédoublé.
En pratique, j'utilise parfois un tableau de pointeurs, comme ça on ne dédouble qu'un ensemble de pointeurs (32 bits) et pas tous les éléments. C'est d'ailleurs la méthode à utiliser quand l'ensemble est sur disque, on ne s'amuse pas déplacer les éléments dans ce cas (un peu comme un index).
Pour le reste, en informatique, TOUT peut être ramené à des nombres entiers (je ne t'apprend rien j'espère ;) ). Un processeur ne connait que ça, et encore, il ne connait que 2 valeurs si on ne garde à l'extrème que la représentation minimaliste, le nombre binaire. Crois-moi, le tri lexicographique marche très bien avec cet algorithme, sans besoin de calculer les longueurs des chaines au préalable. Il ne faut pas faire l'amalgame entre analyse de la complexité (ce que j'ai essayé de faire dans ma précédante intervention) et implémentation pratique.
Ça fait 5 ou 6 ans que j'ai implémenté le tri distribué et que je l'utilise professionnellement avec succès. J'en ai fait une fonction qui s'utilise comme le qsort, mais avec 3 paramètres supplémentaires en plus des 4 de qsort. Le premier est le niveau de profondeur maximale à ne pas dépasser (au delà, les sous-ensembles restant éventuellement à trier le seront avec qsort), ensuite une fonction qui renvoit une valeur de 0 à 255 (ben oui, c'est la base de l'algorithme), et un paramètre optionnelle qui est un contexte de travail (et qui manque à qsort je trouve).
Ceci dit, c'est quand même assez complexe à utiliser car cela demande une analyse préalable des données à trier afin de bien évaluer la valeur [0-255] en fonction de la profondeur où l'on se trouve. Il me faut ensuite deux besoins pour l'utiliser: disposer d'assez de mémoire, et une nécessité impérieuse de vitesse (car, en définitive, qsort est très bien et très facile à utiliser).
On peut quand même remarquer que si on veut stocker n entiers différents, il faut que la taille "p" pour stocker chaque entier en binaire soit au moins log(n). Cela veut dire que la complexité théorique de 'algo n'est pas mieux que O(nlog(n)), sauf dans le cas particulier où il y a des doublons dans l'ensemble à trier.Citation:
Envoyé par camboui
D'un point de vue pratique, je suis convaincu que cet algo est plus rapide que le tri par tas: tous les log(n) ne naissent pas égaux;-)