On parle beaucoup de structures de données, mais je ne trouve pas de liste simple de structures de données et de leur utilisation pratique. J'essaie d'étudier pour une entrevue et je pense que cela m'aiderait, avec beaucoup d'autres. Je cherche quelque chose comme ça:
Structure de données - Exemple / Utilisé pour
Table de hachage - recherche rapide de données ... puis donnez un exemple
Tableau - ...
Arbre binaire - ...
S'il existe une ressource comme celle-ci quelque part, veuillez me le faire savoir.
Merci!
EDIT: Je veux dire que wikipedia est bon et tout, mais sur la plupart des pages, ils ne répertorient pas les utilisations pratiques. Je cherche quelque chose de plus que ça.
data-structures
Joël
la source
la source
Je suis dans le même bateau que toi. J'ai besoin d'étudier pour des entretiens techniques, mais mémoriser une liste n'est pas vraiment utile. Si vous avez 3-4 heures à perdre et que vous voulez faire une plongée plus profonde, je vous recommande de vérifier
mycodeschool
J'ai regardé sur Coursera et d'autres ressources telles que les blogs et les manuels, mais je les trouve soit pas assez complets, soit à l'autre bout du spectre, trop denses avec des terminologies informatiques préalables.
Le mec dans la vidéo a un tas de conférences sur les structures de données. Ne vous inquiétez pas des dessins idiots, ou du léger accent du tout. Vous devez comprendre non seulement la structure de données à sélectionner, mais également d'autres points à prendre en compte lorsque les gens pensent aux structures de données:
J'ai également posté des notes sur github si vous êtes intéressé.
la source
Selon ma compréhension, la structure des données est toute donnée résidant dans la mémoire de tout système électronique qui peut être gérée efficacement. Il s'agit souvent d'un jeu de mémoire ou d'une accessibilité plus rapide des données. En termes de mémoire encore, il y a des compromis à faire avec la gestion des données en fonction du coût pour l'entreprise de ce produit final. Une gestion efficace nous indique comment accéder au mieux aux données en fonction de l'exigence principale du produit final. C'est une explication de très haut niveau mais les structures de données sont un vaste sujet. La plupart des enquêteurs plongent dans des structures de données dont ils peuvent se permettre de discuter dans les entretiens en fonction du temps dont ils disposent, qui sont des listes chaînées et des sujets connexes.
Maintenant, ces types de données peuvent être divisés en primitifs, abstraits, composites, en fonction de la façon dont ils sont logiquement construits et accessibles.
J'espère que cela vous aidera à plonger.
la source
L'excellent livre " Algorithm Design Manual" de Skienna contient un vaste référentiel d'algorithmes et de structure de données.
Pour des tonnes de problèmes, les structures de données et l'algorithme sont décrits, comparés et discutent de l'utilisation pratique. L'auteur fournit également des références aux implémentations et aux documents de recherche originaux.
Le livre est génial de l'avoir sur votre bureau si vous recherchez la meilleure structure de données pour résoudre votre problème. Il est également très utile pour la préparation des entretiens.
Une autre excellente ressource est le dictionnaire NIST des structures de données et des algorithmes .
la source
Peu d'application plus pratique des structures de données
Arbres rouge-noir (utilisé lorsqu'il y a des insertions / suppressions fréquentes et peu de recherches) - Clustering K-mean utilisant un arbre noir rouge, bases de données, base de données simple, recherche de mots dans les dictionnaires, recherche sur le Web
Arbres AVL (plus de recherche et moins d'insertion / suppression) - Analyse de données et exploration de données et les applications qui impliquent plus de recherches
Heap min - Algorithmes de clustering
la source
Tout classement de diverses structures de données sera au moins partiellement lié au contexte du problème. Cela aiderait à apprendre à analyser les performances spatio-temporelles des algorithmes. Typiquement, la "notation en gros O" est utilisée, par exemple la recherche binaire est en temps O (log n), ce qui signifie que le temps de recherche d'un élément est le journal (en base 2, implicitement) du nombre d'éléments. Intuitivement, étant donné que chaque étape élimine la moitié des données restantes comme non pertinentes, doubler le nombre d'éléments augmentera le temps d'une étape. (La recherche binaire s'adapte plutôt bien.) Les performances de l'espace concernent la croissance de la quantité de mémoire pour des ensembles de données plus volumineux. Notez également que la notation big-O ignore les facteurs constants - pour les ensembles de données plus petits, un algorithme O (n ^ 2) peut toujours être plus rapide qu'un algorithme O (n * log n) qui a un facteur constant plus élevé.
Outre le temps et l'espace, d'autres caractéristiques incluent le tri d'une structure de données (les arbres et les skplists sont triés, les tables de hachage ne le sont pas), la persistance (les arbres binaires peuvent réutiliser les pointeurs d'anciennes versions, tandis que les tables de hachage sont modifiées sur place), etc.
Bien que vous ayez besoin d'apprendre le comportement de plusieurs structures de données pour pouvoir les comparer, une façon de comprendre pourquoi elles diffèrent en termes de performances consiste à en étudier de près quelques-unes. Je suggérerais de comparer des listes à liaison unique, des arbres de recherche binaires et des listes de sauts , qui sont tous relativement simples, mais ont des caractéristiques très différentes. Pensez à combien de travail il faut pour trouver une valeur, ajouter une nouvelle valeur, trouver toutes les valeurs dans l'ordre, etc.
Il existe différents textes sur l'analyse des performances des algorithmes / structures de données que les gens recommandent, mais ce qui les a vraiment mis en valeur pour moi, c'est d'apprendre OCaml. Traiter avec des structures de données complexes est le point fort de ML, et leur comportement est beaucoup plus clair lorsque vous pouvez éviter les pointeurs et la gestion de la mémoire comme en C. (Apprendre OCaml juste pour comprendre les structures de données est presque certainement le long chemin, cependant. :))
la source