trouver l'index de l'élément dans une collection, quelle collection utiliser?

Question

J'ai un problème de choisir la structure de données droite/s, ce sont les exigences:

• Je dois pouvoir insérer et supprimer des éléments
• Je dois aussi être en mesure d'obtenir l'indice de l'élément la collecte (l'ordre dans la collection)
• éléments a un numéro d'identification unique
• I peut trier (si nécessaire) des éléments à l'aide de tout critère

commande est pas vraiment un must, l'important est d'obtenir l'index de l'élément, peu importe comment est implémenté en interne, mais de toute façon je pense que la meilleure approche est la commande. L'index de l'élément est l'ordre dans la collection. Donc, une sorte d'ordre doit être utilisé. Quand je supprime un élément, les autres éléments de celui-ci à la fin changent leur ordre/index.

La première approche utilise une liste chaînée, mais je ne veux pas d'O (n). J'ai aussi pensé à utiliser et à ordonner un dictionnaire, ce qui donnerait O (log n) pour la recherche/insertion/suppression, n'est-ce pas? Y a-t-il une meilleure approche? Je sais qu'un TRIE donnerait O (1) pour des opérations communes, mais je ne vois pas comment obtenir l'index d'un élément, je devrais itérer sur le trie et donnerais O (n), ai-je tort?

Answer 1

On dirait que vous voulez une structure de données ordonnée, c'est-à-dire un BST (équilibré). L'insertion et la suppression seraient en effet O (lg n), ce qui suffit pour de nombreuses applications. Si vous voulez aussi des éléments pour avoir un indice dans la structure, alors vous voulez un order statistic tree (voir par exemple, CLR, Introduction aux algorithmes, chapitre 14) qui fournit cette opération en O (nlg). Le ré-tri dynamique de la totalité de la collection serait O (n lg n).

Si par « l'ordre dans la collection » vous dire un ordre aléatoire est assez bon, alors il suffit d'utiliser un tableau dynamique (vecteur): amortissement O (1) ajouter et supprimer, O (n lg n) tri sur place, mais O (n) recherche jusqu'à ce que vous faites le tri, après quoi la recherche devient O (lg n) avec la recherche binaire. La suppression serait O (n) si les données doivent rester triées, cependant.

Si vos données sont semblables à des chaînes, vous pourriez être en mesure d'étendre une trie de la même manière qu'un BST est étendu pour devenir une arborescence de statistiques d'ordre.Bien si votre collection est triée, vous n'avez pas besoin de O (n) pour trouver des éléments.

Answer 2

Vous ne mentionnez pas de tableau/vecteur ici, mais il répond à la plupart de ces critères. (Notez que "Éléments a un numéro d'identification unique" est vraiment indépendant de la structure de données, est-ce que cela signifie la même chose que l'index? Ou est-ce une clé immuable, qui est plus fonction des données que vous mettez? dans la structure ...)

Il y aura des compromis de synchronisation dans n'importe quel scénario: vous dites que la liste chaînée est O (n), mais O (n) pour quoi? Vous ne comprenez pas vraiment vos exigences de performances pour les ajouts par rapport aux suppressions par rapport aux recherches; ce qui est plus important?

Answer 3

Il est possible d'utiliser la recherche binaire par exemple pour déterminer l'indice de l'élément. Il est également possible d'écrire un wrapper simple à propos de Entry dans votre tableau, qui se souvient de son index à l'intérieur de la collection.