Y a-t-il un graphique ou une table n'importe où qui affiche beaucoup de structures de données (au moins populaires) et d'algorithmes avec leurs temps de fonctionnement et leur efficacité?
Ce que je cherche, c'est quelque chose que je peux regarder et décider quelle structure / algorithme est le meilleur pour un cas particulier. Il serait utile lorsque vous travaillez sur un nouveau projet ou tout comme guide d'étude.
4 Réponses :
Un graphique ou une table ne sera pas une référence particulièrement utile.
Si vous allez utiliser un algorithme ou une structure de données particulière pour résoudre un problème, vous feriez mieux de le savoir et de la comprendre à l'intérieur et à l'extérieur. Et cela inclut la connaissance (et savoir dériver) leurs gains d'efficience respectifs. Ce n'est pas particulièrement difficile. La plupart des algorithmes standard ont des moments d'exécution simples et intuitives tels que Cela étant dit, le temps d'exécution Big-o n'est pas tout. Prendre le tri par exemple. Le tri des tas a un meilleur Big-O que de dire un tri rapide, mais une sorte de tri rapide fonctionne beaucoup mieux dans la pratique. Les facteurs constants dans les Big-O peuvent également faire une différence énorme.
Lorsque vous parlez de structures de données, il y a beaucoup plus à eux que de rencontrer l'œil. Par exemple, une carte de hachage semble être juste une carte d'arbre avec beaucoup de meilleures performances, mais vous obtenez une structure de tri supplémentaire avec une carte d'arborescence.
SAVOIR Quelle est la meilleure algorithme / structure de données à utiliser est une question d'expérience de la connaissance, pas une table de recherche.
Retour à votre question, je ne connais aucune référence de ce type. Ce serait un bon exercice de s'en faire soi-même. Wikipedia a des articles très décents sur des algorithmes communs / des structures de données avec une analyse décente. n ^ 2 , n * logn , etc.
Merci! Prendra votre conseil!
Je ne crois pas que cette liste existe. Le nombre abrégé d'algorithmes connus et de structures de données est stupéfiant et de nouveaux sont développés tout le temps. De plus, bon nombre de ces algorithmes et structures de données sont spécialisés, ce qui signifie que même si vous aviez une liste devant vous, il serait difficile de savoir quelles étaient applicables aux problèmes particuliers que vous essayiez de résoudre.
Une autre préoccupation avec une telle liste est de savoir comment quantifier l'efficacité. Si vous deviez classer des algorithmes en termes de complexité asymptotique (BIG-O), vous pourriez finir par mettre de certaines algorithmes et structures de données asymptotiquement optimales mais peu lentes sur de petites intrants devant les algorithmes qui sont connu pour être rapide pour des cas pratiques mais pourrait ne pas être théoriquement parfait. À titre d'exemple, envisagez d'examiner l'algorithme médiane de médianes pour les statistiques de l'ordre de temps linéaire, qui a un facteur constant aussi important que d'autres algorithmes ont tendance à être beaucoup mieux en pratique. Ou considérez Quicksort, qui dans le pire des cas est O (n 2 ) mais dans la pratique a une complexité moyenne o (n lg n) et est beaucoup plus rapide que d'autres algorithmes de tri .
D'autre part, essayiez-vous d'énumérer les algorithmes par efficacité d'exécution, la liste serait trompeuse. L'efficacité d'exécution est basée sur un certain nombre de facteurs spécifiques à la machine et à une entrée (tels que la localité, la taille de l'entrée, la forme de l'entrée, la vitesse de la machine, l'architecture de processeur, etc.), il pourrait être utile en règle générale. -Of-pouce, mais dans de nombreux cas, vous pourriez être induire en erreur par les chiffres pour choisir un algorithme quand un autre est bien supérieur.
Il y a aussi une complexité de la mise en œuvre à considérer. De nombreux algorithmes n'existent que dans les papiers ou ont des implémentations de référence qui ne sont pas optimisées ou sont écrites dans une langue qui ne correspond pas à ce que vous recherchez. Si vous trouvez un algorithme Saint Graal qui fait exactement ce que vous voulez, mais pas de mise en œuvre pour cela, il pourrait être incroyablement difficile de coder et de déboguer votre propre version. Par exemple, s'il n'y avait pas une prépondérance des implémentations d'arbres rouges / noirs, pensez-vous que vous pourrez le coder vous-même? Que diriez-vous des tas de fibonacci? Ou (de l'expérience personnelle) van emme boas arbres? Souvent, il peut être une bonne idée de choisir un algorithme plus simple qui est "assez bon" mais facile à mettre en œuvre sur un algorithme beaucoup plus complexe.
En bref, je souhaite qu'une table comme celle-ci puisse exister que cela avait vraiment toutes ces informations, mais de manière pratiquement, je doute que cela puisse être construit d'une manière utile. Les liens Wikipedia des commentaires de @ Hammar sont en fait assez bons, mais le meilleur moyen d'apprendre ce que les algorithmes et les structures de données à utiliser dans la pratique sont en train de les pratiquer.
Merci beaucoup pour votre aide! Connaissance ++;
Y a-t-il une étude sur ce sujet? Comme dans, quelqu'un a effectivement enregistré les statistiques de la machine, diverses entrées, etc. avec divers algorithmes différents et publié dans un livre? Ce serait un excellent livre à lire à mon avis.
@ Gbert90- Ce livre ne serait pas très utile. Si nous devions attendre dix ans après sa publication et consulter les chiffres, ils seront tous relatifs aux machines qui ne sont plus utilisées. Les OSES auront changé, de sorte que les effets de la mémoire virtuelle organiseraient également les chiffres. Avec le nombre de cœurs par chèvre augmentant, des algorithmes parallèles sembleraient pire de manière disproportionnée sur les plus anciennes machines. Avec la RAM devenant plus disponible, des algorithmes qui utilisent beaucoup de mémoire pourraient commencer à devenir beaucoup plus rapide et plus viable même s'ils étaient plus lents aujourd'hui.
Vrai, mais si les résultats de l'étude ont été mis dans un graphique, ne vous aideraient-ils pas à voir quels facteurs affectent le temps de fonctionnement le plus / le moins? Je veux dire, garder tout le reste constant et simplement changer chaque facteur à la fois. Ou aller au fond de Wikipedia répond à toutes ces questions?
Peut-être, mais il y a un lot de facteurs à prendre en compte et qu'il n'y a aucun moyen de rendre compte de tous. Voici quelques éléments à suivre: vitesse du processeur, taille de cache de processeur, nombre de processeurs, système d'exploitation, température ambiante (vitesse de processeur), quantité de RAM, vitesse de la RAM, nombre de cache misses, étendue de l'optimisation du compilateur, langage de programmation de Choix, taille d'entrée, complexité d'entrée (très difficile à quantifier), générateur aléatoire utilisé (pour algorithmes aléatoires), vitesse de disque (pour les défauts de page), etc. Aucune table ne pourrait jamais espérer rendre compte de tout cela.
Ce serait bien / utile pour calculer des vitesses relatives. Bien entendu, la performance de certains algorithmes dépend des choses telles que la performance de cache. Mais dans l'ensemble, il s'agirait d'une référence utile, comparant les algorithmes sur différents types d'intrants.
Ah, je vois. Merci pour des réponses détaillées! Je suppose donc que travailler sur de nombreuses machines et algorithmes différents vous donnera une "sensation" de ce qui pourrait fonctionner mieux et ce qui ne pourrait pas.
La première priorité pour un programme informatique est correcte et la seconde, la plupart du temps, est une heure programmeuse - quelque chose directement lié à la manipulation et à l'extensibilité.
Pour cette raison, il existe une école de programmation qui préconise simplement en utilisant des substances simples telles que des tableaux d'enregistrements, à moins que cela ne soit un élément sensible à la performance, auquel cas vous avez besoin non seulement de considérer les structures de données et les algorithmes, mais également le " Architechture "qui vous a amené à avoir ce problème en premier lieu.
Pour moi, trier de grandes quantités de données à l'aide de quelque chose comme Bubble Tri n'est pas "correct". L'efficacité compte, et beaucoup plus que la plupart des programmeurs se rendent compte.
C'est une question très délicate et il y a certainement un équilibre à frapper entre "juste le faire fonctionner" et "le rendre fou fous vite". Vous et @tskuzzy avez-vous des points valides ici. C'est juste une question de trouver la moyenne d'or entre les deux extrêmes.
Mais dans ce cas, en utilisant une bibliothèque intégrée fonction comme qsort est également plus simple et plus susceptible d'être correcte que de faire votre propre algorithme (inefficace) de toute façon. Le point important est que l'utilisation d'une source de données fantaisie est toujours liée à un coût de gestion accrue qui ne doit pas être ignoré.
Collecte Tous les Les algorithmes et / ou les structures de données sont essentiellement impossibles - même comme je l'écrivent, il y a sans aucun doute quelqu'un, quelque part invente une nouvelle algorithme ou une nouvelle structure de données. Dans le plus grand schéma des choses, ce n'est probablement pas beaucoup de grande importance, mais c'est toujours probablement nouveau et (tellement légèrement) différent de tout ce qui est fait avant (bien sûr, il est toujours possible ça se révéler être une grande chose importante).
Cela dit, le Nist américain a un Dictionnaire des algorithmes et des structures de données qui énumère plus que la plupart des gens se connaissent ou se soucient de. Il couvre la plupart des "grands" évidents que tout le monde sait et beaucoup de moins connus aussi bien connu. L'Université de Canterbury a autre c'est (ou au moins me semble-à-moi) un peu plus modeste, mais couvre toujours la majeure partie de ce qu'un programmeur typique se soucie probablement et est un peu mieux organisé pour trouver un algorithme pour résoudre un problème particulier, plutôt que d'être fondé principalement sur le nom déjà connu. de l'algorithme que vous voulez.
Il existe également divers collections / listes plus spécialisées. Par exemple, Le référentiel d'algorithme de Stony Brook est consacré principalement (exclusivement?) Aux algorithmes combinatoires . Il est basé sur le manuel de conception d'algorithme , il peut donc être particulièrement utile si vous avez / utilisez ce livre (et au cas où vous vous demandez, ce livre est généralement très apprécié).
ici et ici , même si vous devrez cliquer pour vérifier leur complexité.