Structure de données à temps constant pour insérer, contenir, supprimer et obtenir des éléments par index

Question

J'ai un grand ensemble de données de Person objets qui sont mis en file d'attente dans une liste. Je souhaite que la structure de données puisse effectuer les opérations suivantes de manière efficace.

1. Ajoutez un Person à la fin de la file d'attente.
2. Supprimez le premier Person.
3. Si un Person existe, le cas échéant, supprimez-le et placez-le à la fin de la file d'attente.
4. Obtenez un Person particulier par sa position.

Est-il possible d'avoir le temps O (1) pour toutes ces opérations? Jusqu'à présent, j'ai trouvé deux façons, mais elles ne sont pas optimales.

1. ArrayList<Person> + HashMap<Person, Integer>

   Les HashMap stocke l'index des objets. Person Cela donne O (n) pour un fonctionnement 2 et 3 (élimination élément dans le ArrayList)

2. ArrayDeque<Person>/LinkedList<Person>

   Ils donnent O (1) pendant les 2 premières opérations, mais O (n) pour la dernière deux.

La complexité de l'espace ne doit pas être supérieure à O (n) dans mon cas. L'opération 4 est moins intensive, donc je pourrais tolérer un moyen un peu inefficace de le faire.

Toutes les suggestions seraient appréciées. Merci d'avance!

Answer 1

Je suppose que l'exigence 3 signifie "trouver une personne par une clé" (par exemple, son nom de famille)?Je crois fermement que vous ne pouvez pas avoir toutes ces exigences en O (1), pas même le temps amorti (une telle chose serait bien connue). Mais vous pouvez tous les avoir en O (log N). Vous devez commencer par une implémentation d'un arbre rouge-noir (std :: map en C++, je crois que c'est SortedMap en Java), et modifier la structure du nœud pour garder le nombre de tous les nœuds dans son sous-arbre. Cela vous donnera l'accès O (log N) par index, ainsi que l'insertion et la suppression de O (log N) n'importe où dans l'arbre. Trouver une personne par une clé peut être fait dans O (1) par une table de hachage externe (de noeuds d'arbre rouge-noir).

Si vous êtes d'accord avec O (N) pour la condition 4, alors je suggère d'utiliser quelque chose comme LinkedHashMap en Java, qui vous donne les exigences 1 à 3 dans O (1), tout en req. 4 peut être fait en itérant, en O (N).

Answer 2

Si la question n'a pas été marqué java, mais c++, une combinaison de std::deque et std::unordered_map serait presque suffisent. Je dis presque parce que la troisième demande est plutôt compliquée et je ne vois pas comment le faire en O(1) combiné avec trois autres.

std::unordered_map a son équivalent en Java, HashMap, mais ce std::deque fournit et ArrayDeque n'a pas, est O(1) accès aléatoire -> votre numéro de demande quatre. Même si has already been discussed, cette fonctionnalité est toujours manquant dans ArrayDeque, mais je suppose que ce ne serait pas si difficile à ajouter manuellement. Après tout, std::deque est simplement un vecteur avec des pointeurs vers les tampons de taille fixe.

Les deux premières opérations sont O(1) dans toute mise en œuvre décente. Selon la demande numéro trois, HashMap (ou std::unordered_map) vous donnerait une information si un Person existe en O(1) temps, et vous pouvez le mettre à la fin avec la même complexité. La suppression est un problème car d'autres éléments doivent être décalés et ne peuvent pas être obtenus en O(1) en utilisant cette stratégie.