Structures de données: Que dois-je utiliser pour ces conditions?

Question

Cela ne devrait pas être une question difficile, mais je voudrais juste quelqu'un pour rebondir hors de avant que je continue. Je dois tout simplement de décider quelle est la structure des données à utiliser en fonction de ces activités prévues:

1. Est-ce besoin fréquemment itérer pour trier (à partir de la tête).
2. devez supprimer / restaurer des éléments arbitraires du / vue trié.
3. Plus tard, je vais souvent recourir les données et travailler avec plusieurs vues triées.
4. Aussi plus tard, je vais souvent en train de changer la position des éléments dans leurs vues triées.

Ceci est en Java, par la manière.

Ma meilleure estimation est que je vais soit déploierons hasch PREF lié (pour organiser les liens dans l'ordre de tri) ou peut-être juste à l'aide d'un ensemble d'arbres. Mais je ne suis toujours pas encore complètement sûr. Recommandations?

Modifier: Je suppose en raison de la supprimer arbitraire / restore, je devrais probablement rester avec un ensemble d'arbre, à droite

En fait, pas nécessairement. Hmmm ...

Answer 1

En théorie, je dirais que la structure de données est un arbre droit multivoies - de préférence quelque chose comme un arbre B +. Traditionnellement, c'est une structure de données sur disque, mais la mémoire principale moderne a beaucoup de caractéristiques similaires en raison de couches de cache et de la mémoire virtuelle.

En ordre itération d'un arbre B + est très efficace, car (1) vous n'itérer la liste chaînée des nœuds feuilles -. Nœuds de branche ne sont pas nécessaires, et (2) vous obtenez très bonne localité

Recherche, retrait et l'insertion des éléments arbitraires est log (n) sous la forme d'un arbre équilibré, mais avec différents facteurs constants.

Recourir dans l'arbre est surtout une question de choix d'un algorithme qui donne de bonnes performances lors de l'utilisation sur une liste chaînée de blocs (les nœuds feuilles), ce qui réduit la nécessité d'utiliser des nœuds feuilles - variantes de quicksort ou mergesort semblent comme des candidats probables . Une fois que les éléments sont classés dans les noeuds de branche, juste les informations de se propager résumé à travers les nœuds feuilles.

et - pragmatiquement, ce n'est quelque chose que vous feriez si vous êtes bien sûr que vous en avez besoin. Les chances sont bonnes que vous êtes mieux d'utiliser un certain conteneur standard. optimisation algorithme / structure de données est le meilleur type d'optimisation, mais il peut encore prématuré.

Answer 2

Standard LinkedHashSet ou LinkedMultiset des collections Google si vous voulez que votre structure de données pour stocker pas des valeurs uniques.