Est-il connu de la mise en œuvre d'un indexés liste chaînée?
Mon instinct me dit qu'il ya pas de bonne façon de le réaliser, mais, à la différence de M. Stephen Colbert, je préfère faire confiance à une communauté de développeurs que mon intestin...
Est-il un moyen connu pour mettre en œuvre efficacement un "meilleur des deux mondes" de la liste, celui qui fournit l'accès aléatoire par l'indice de et O(1) insertion/retrait comme une liste chaînée?
Je pense que les deux résultats possibles: soit "Non, c'est impossible, pour des raisons évidentes..." ou "Euh, oui, cela a été fait; voir ici, ici et ici."
InformationsquelleAutor Dan Tao | 2009-11-11
Vous devez vous connecter pour publier un commentaire.
Je ne crois pas qu'il sera possible d'obtenir
O(1)
pour à la fois l'insertion et la recherche. La minute que vous l'ajouter à un tableau (ou même de fantaisie, splittable vecteurs), l'insertion devientO(n)
.Il existe des moyens de limiter les dégâts en fonction du comportement attendu de votre liste. Si il y aura beaucoup plus de recherches que les insertions/délétions, il peut être préférable de simplement utiliser des vecteurs (de taille variable tableaux) - ce sont raisonnablement efficace, pas tout à fait comme des tableaux, mais mieux que la traversée de listes (puisque ceux-ci tendent à être des listes de tableaux, c'est toujours techniquement parcourant une liste, mais chaque élément de la liste a généralement sa taille, ce qui le rend plus efficace).
Si les insertions et les suppressions sont de plus en plus fréquentes, vous pouvez faire l'index de construire un paresseux, de sorte que c'est fait uniquement lorsque c'est nécessaire. Par exemple, les insertions et les suppressions ne changera la liste liée part (et de la marque de l'indice de sales) - uniquement lorsque quelqu'un tente d'utiliser l'index, il sera reconstruite et marqué comme propre.
Vous pouvez même optimiser la reconstruction en gardant une trace de la première sale entrée. Cela signifie que si vous n'insérez ou supprimez dans la dernière moitié de la liste, vous n'avez pas besoin de reconstruire la totalité de l'index quand quelqu'un veut l'utiliser.
Une solution une fois, j'ai mis en œuvre est un 2D Liste. Par cela, je veux dire:
Alors que cela fait à la fois l'insertion et de la recherche O(n), le solde était de droite. Dans une pure solution de matrice, la recherche est
O(1)
et de l'insertion estO(n)
. Pour un pur liste liée, de l'insertion estO(1)
(une fois que vous avez trouvé le point d'insertion, bien sûr, une opération qui est lui-mêmeO(n)
) et la recherche estO(n)
.La 2D liste est
O(n)
pour les deux mais avec un faible facteur. Si vous êtes à la recherche d'insérer, vous pouvez trouver la colonne de droite tout simplement par l'examen de la première ligne de chaque colonne. Puis vous traversez la colonne elle-même à la recherche de la ligne droite. Ensuite, l'élément est inséré et le comte de cette colonne est augmenté. De même pour les suppressions, même si dans ce cas le nombre est diminué, et l'ensemble de la colonne est supprimée lorsque son compte à rebours atteint zéro.Pour une recherche d'index, vous traversez les colonnes de trouver la bonne colonne, puis parcourir les éléments dans la colonne pour obtenir l'élément de droite.
Et, il peut même être auto-réglage en essayant de garder le maximum de la hauteur et la largeur à peu près la même.
Si vous pensez que O(log N) == O(1),
découvrez:
Quand j'étais mise en œuvre d'une liste liée dans la classe j'ai pensé sur l'optimisation des temps d'accès en stockant 3 champs supplémentaires: Le nœud au milieu de la liste, l'indice de la plus récente accessible nœud et le plus récemment ouvert nœud lui-même.
Pour récupérer un nœud à l'index que je ne puis premier coup d'oeil à tous les chemins disponibles pour atteindre le nœud à l'index donné et choisi le meilleur moyen de le faire. Les moyens seraient tout simplement:
Le chemin avec la plus petite différence dans notre index et notre indice de départ serait l'option la moins chère. Si aucun nœud n'a accédé encore, récemment accédé nœud pourrait être le moyen de nœud. Bien sûr, avec un même nombre d'éléments, il n'y a pas de milieu, de sorte que je venais de choisir le sol de n/2.
De toute façon, je n'ai jamais eu l'occasion de réellement mettre en œuvre cette optimisation ou même vraiment l'analyser, mais j'espère que je pourrais aider.
Votre intestin est correcte sur ce.
Les listes chaînées sont en O(1) insertion/suppression, car l'opération que vous effectuez d'insérer ou de retirer quelque chose est juste à changer un couple de pointeurs (un ou deux sur l'objet que vous êtes à l'insertion, et un ou deux sur un ou deux autres objets). Cela ne change pas par la taille de la liste, évidemment.
Un saut de liste va vous donner O(logn) de recherche, mais puisque vous êtes maintenant un indice il signifie aussi O(logn) insertion/délétion, parce que l'indice doit être tenu à jour.
Parallèles structure de données que vous utilisez pour la recherche devront être maintenus, de sorte que votre complexité de mise à l'échelle par l'indice de complexité.
Vous avez un problème particulier à l'esprit que vous essayez de résoudre?
Par exemple, vous pouvez obtenir O(n) d'insertion, de suppression et de recherche si vous pouvez garantir une parfaite hachage. Mais vous devez savoir certaines choses à propos de vos données à l'avance de temps pour que cela fonctionne.
Comment sur une table de hachage? Vous obtenez O(1) d'accès aléatoire par clé et O(1) insertion/suppression. Le hic, c'est que les inscriptions sont non ordonnée.
Pour une mise en œuvre efficace de séquences ordonnées, découvrez doigt arbres. Ils vous donnent O(1) l'accès à
head
etlast
et O(log n) accès aléatoire à l'intérieur des nœuds. Insérer ou de supprimer, à la fin en O(1). Notamment, le renversement d'un doigt arbre à temps constant.Je ne sais pas exactement BigO à l'insertion (car ce serait varier en fonction de la taille de l'échantillon et de la croissance), mais Java est
java.util.LinkedList
viendrait immédiatement à l'esprit.http://java.sun.com/j2se/1.5.0/docs/api/java/util/LinkedList.html
EDIT: oui, apparemment, en-dessous, c'est toujours un vrai liste liée et en tant que tel indexé obtient pourrait être O(n/2), qui est bien sûr formellement O(n).
Vous pouvez toujours déchets tout un tas d'espace et de mettre en œuvre une Liste de mise en œuvre qui garde, en parallèle, une liste liée et tableau avec différé d'insertion/renvoi.
Alors que je ne pense pas que vous pouvez obtenir de l'entier de l'indexation, une sauvegarde de la table de hachage pourrait fonctionner si vous utilisez "référence" types.
De Java
LinkedList
a O(n) accès indexé obtient.LinkedList
s'étendAbstractSequentialList
de montrer qu'il n'offre pas de O(1) indexés obtient.Je vous suggère de prendre un coup d'oeil à Apache liste arborescente. Il propose O(log n) insertions/suppressions et O(1) indexé sur les recherches.
get(Object)
et/ou un indice deget(index)
. En se référant à indexés obtient, je parle de la dernière où vous souhaitez que le n-ième élément de la liste.