Qu'est-ce lié ajustements de structure de données de la liste me donner recherche rapide au hasard?

Question

J'utilise actuellement une liste doublement chaînée (la std::list de C de) afin de maintenir un groupe d'enregistrements qui ont chacune un identificateur entier unique. La liste chaînée est créée afin de telle sorte que dans Sorted la liste, l'élément suivant a toujours un identifiant unique, plus grand que son prédécesseur.

La question que je suis confronté est que, parfois, je dois être en mesure d'insérer un élément rapidement dans sa position triée relative et en utilisant un moyen de liste chaînée ordinaire cette opération est O $ (n) $, ce qui est à l'origine des problèmes de performance pour moi . En général, cela voudrait dire que je veux utiliser quelque chose comme un arbre binaire (C ++ std::map), cependant, je suis également en fonction de la caractéristique d'une liste doublement chaînée suivante pour une bonne performance:

• Possibilité de raccorder une section contiguë sur une liste liée à un autre en $ O (1) $ temps. ($ O Amorti (1) $ ou $ O (\ log \ log n) $ serait assez bon.)

Une caractéristique de mes données que je voudrais l'effet de levier est que j'ai souvent de longues plages d'enregistrements contigus où nombre entier unique de chacun est exactement un de plus que son prédécesseur. Lors de la recherche de la position relative Sorted un élément, il serait toujours en dehors de ces enregistrements contigus car il n'y a pas d'identification en double.

Je voudrais trouver une structure de données de remplacement ou l'augmentation d'une liste doublement chaînée qui me permettra de continuer à raccorder des sections entières d'une liste à l'autre constante de temps, mais permettez-moi de localiser la position triée dans laquelle insérer un nouveau record en mieux que O $ (n) $ temps.

D'autres opérations sont en avant et en arrière itération sur les éléments. Les indices d'enregistrement commencent à zéro et poussent vers le haut en direction de 64 bits, en général de manière séquentielle, et le code fonctionne bien dans de tels cas. De temps en temps certains documents ne sont pas disponibles avant les suivantes, il est l'insertion de ces documents manquants qui cause maintenant les problèmes de performance.

Une approche possible qui se produit pour moi de mettre en cache l'emplacement de plusieurs indices. Le cache obtiendrait invalidée chaque fois qu'une jonction supprime les éléments qui pourraient chevaucher les entrées mises en cache. Avec ce cache, au lieu de faire une recherche linéaire, la recherche pourrait commencer au lieu du point de cache iterator dont index unique est le plus proche de celui dont la position est recherchée. Cependant, je voudrais plus utiliser pleinement la fonction des enregistrements contigus. Je pensais aussi sur une liste chaînée hiérarchique où j'ai une liste chaînée de niveau supérieur des régions contiguës, où chaque région est une liste chaînée d'enregistrements qui sont consécutifs, mais je ne vois pas une manière propre d'adapter une liste chaînée pour fournir cette Fonctionnalité. Peut-être quelque chose comme cela a été fait avant? Je trouve les listes de saut à être proches, mais ne vois pas la fonctionnalité épissure (), ainsi qu'une liste de saut générique ne fait que tirer parti de l'insertion ne se produit jamais dans les dossiers contigus.

Answer 1

Une approche simple pourrait être d'utiliser une liste doublement chaînée des degrés, où chaque mesure représente une séquence d'enregistrements contigus. Les dossiers de chaque mesure pourraient à leur tour être représentés par une liste doublement chaînée.

Cela permet de préserver votre capacité à faire O $ (1) $ épissage de temps, et maintenant l'opération d'insertion prend O $ (k) $ temps, où $ k $ est le nombre d'extensions (plutôt que $ O (n) $ , où n $ est le nombre d'enregistrements). Si vous avez beaucoup moins étendues que les dossiers, cela pourrait être une amélioration partielle.

Je ne sais pas si ce sera mieux que la liste simple ou arbre binaire.

Notez que si vous utilisez un arbre binaire, vous pouvez toujours faire épissage efficace. L'opération de raccordement est plus O $ (1) $ temps, mais il peut être fait en $ O (\ log \ ell) $ temps, où $ \ ell $ est le nombre d'enregistrements dans le segment épissé. Ce n'est pas aussi vite que O $ (1) $ épissage de temps, mais en fonction de la fréquence relative de vos différentes opérations, il est une autre structure de données que vous pourriez envisager (par exemple, référence sur des ensembles de données réalistes).

Et, bien sûr, vous pouvez combiner ces idées, par exemple, avec un arbre binaire de degrés, où chaque mesure est à son tour une liste doublement chaînée des dossiers contigus. Inserts prendra $ O (\ lg k) $ temps et épissage peut être fait en $ O (\ lg \ ell) $ temps (les deux qui pourraient potentiellement être mieux que le $ O (\ logn) $ atteint par un simple, arbre binaire).