Que pouvez-vous dire à propos de moderne structures de données? Nous savons tous les classiques, comme des arbres, des essais, des piles, des listes, des B-arbres et ainsi de suite (je pense que Cormen du livre est une très bonne liste de "classiques"). Mais ce que sur les récentes recherches? Je peux en citer au moins 2 d'entre eux: doigt d'arbres et judy tableaux. Je voudrais savoir plus.
Réponses
Trop de publicités?
Cela dépend vraiment de votre définition de "récent". CLRS contient un grand nombre de structures de données, mais omet de nombreuses structures qui avait été développé autour de ce temps. Par exemple, le van Emde Boas arbre, ce qui permet très vite de stockage et de recherche de nombres entiers, avait été mis en place par ce temps, mais n'a pas été mentionné nulle part.
Beaucoup de la recherche moderne a été sur le cache-inconscient des structures de données, qui sont des structures qui prennent l'avantage optimal de la hiérarchie de mémoire sous réserve de certaines des hypothèses raisonnables. Brodal est un chercheur dans ce domaine et qui a produit un grand nombre d'excellentes structures de ce type.
Purement fonctionnelle des structures de données qui peuvent être utilisées dans les langages fonctionnels (ou dans des langages impératifs pour garantir la persistance) sont également un sujet actif de recherche. Chris Okasaki du travail dans ce domaine a conduit à des développements de nouveaux arbres et les files d'attente de priorité, par exemple.
Distribué des structures de données sont de grande importance ces jours-ci. BigTable de Google est un excellent exemple. De même, simultanées ou sans verrouillage des structures de données ont trouvé leur place dans de nombreux langages de programmation (voir, par exemple, de Java ConcurrentHashMap ou CopyOnWriteArrayList).
Les structures de données de base sur les amortissements sont mentionnés de manière tangentielle dans CLRS, qui met l'accent sur le tas de Fibonacci. Cependant, le feuilletage de l'arbre et de fausser les tas de structures développées à la même époque ne sont pas mentionnées, même si elles sont de grande importance aujourd'hui.
Probabiliste des structures comme le treap et sauter de la liste que vous avez beaucoup de l'activité de recherche, et sont un excellent endroit pour continuer à explorer. Dans un même ordre d'idées, puissant tables de hachage comme le coucou de la table de hachage ou dynamique parfait tables de hachage sont certainement la peine de regarder dans.
Structures de données pour le calcul de la géométrie ont eu un coup d'oeil de l'accent ces dernières années, mais malheureusement je ne sais pas pour eux, bien assez pour suggérer une quelconque des structures particulières.
Structures de données pour le traitement de chaîne, à savoir le suffixe de l'arbre, sont extrêmement pertinents dans biocomputation et de recherches sur le web. Je ne pense pas que CLRS mentionne même de leur existence. Vous devriez vraiment regarder dans eux, cependant, car ils sont responsables d'une grande partie du travail de la génomique.
De nombreux chercheurs ont fait des efforts dans la construction de structures de données qui profitent du fait que les machines modernes peuvent fonctionner sur plusieurs bits en parallèle. Certaines structures comme la fusion de l'arbre, l'exponentielle de l'arbre, ou y-rapide de l'arbre exploiter ces propriétés pour le tri et de recherche dans les tableaux d'entiers plus rapidement que le O(n lg n) les barrières imposées dans un naïf modèle de comparaison.
Il y a aussi beaucoup de travaux en cours sur la synthèse, des croquis, des synopsis et des structures de données que d'essayer de le rendre possible pour répondre à des questions sur un jeu de données sans stocker l'ensemble de manière explicite. Le Comte-Min sketch est un excellent exemple d'une de ces structures de données.
C'est juste un petit échantillon de la nouvelle et fraîche structures de là-bas. J'espère que c'est un bon point de départ!
SoapBox
Points
14183
Certains de la relativement récente (comme dans les 30 dernières années) structure de données innovations ont été probabiliste, comme Skip Lists. Je trouve particulièrement intéressant, mais je n'ai pas de garder sur la recherche. La lecture récente de l' ACM Transactions sur des Algorithmes peut vous aider à trouver certains intéressant de pointe et de la recherche.
Mais, plus rien de "nouveau" va être très spécialisé. C'est seulement une fois dans un très long moment que d'une nouvelle mais fondamentalement important de l'algorithme ou de la structure est créée (comme les listes, les arbres, etc).
Brian Makin
Points
553
Il existe plusieurs centaines de des structures spécialisées de données. http://en.wikipedia.org/wiki/List_of_data_structures c'est un bon début.
Andrey
Points
36869
Coucou hachage est un système dans l'ordinateur de programmation pour la résolution de hachage les collisions de valeurs de fonctions de hachage dans un tableau. Coucou hachage a d'abord été décrit par Rasmus Pagh et Flemming Friche Rodler en 2001.
http://en.wikipedia.org/wiki/Cuckoo_hashing
Puis frais sont les suivants: le Cache-inconscient des structures de données
