Conception de petits objets comparables

Question

Intro

Considérez-vous une liste de paires clé/valeur:

(0,a) (1,b) (2,c) 

Vous avez une fonction, qui insère une nouvelle valeur entre deux paires de courant, et vous avez besoin pour lui donner une clé qui maintient l'ordre:

(0,a) (0.5,z) (1,b) (2,c) 

Voici la nouvelle clé a été choisie comme la moyenne entre la moyenne des clés des paires de délimitation.

Le problème est que votre liste peut contenir plusieurs millions d'insertions. Si ces inserts sont tous placés près les uns des autres, vous pouvez vous retrouver avec des clés telles que 2^(-1000000), qui ne sont pas facilement stockables dans une classe de numéros standard ou spéciale.

Le problème

Comment pouvez-vous concevoir un système de génération de clés qui:

• donne quand par rapport à tout le reste des clés du résultat correct (plus/plus petit que).
• Récupère uniquement la mémoire O(logn) (où n correspond au nombre d'éléments de la liste).

Mes essais

• D'abord j'ai essayé différentes classes de nombre. Comme les fractions et même le polynome, mais je pourrais toujours trouver des exemples où la taille de la clé deviendrait linéaire avec le nombre d'insertions.
• Ensuite, j'ai pensé à enregistrer des pointeurs sur un certain nombre d'autres clés, et d'enregistrer la relation inférieure/supérieure, mais cela nécessiterait toujours au moins O(sqrt) mémoire et le temps pour la comparaison.

Extra info: Idéalement, l'algorithme ne doit pas se casser lorsque les paires sont supprimés de la liste.

Answer 1

Je suis d'accord avec le seigneur des neiges. Un arbre serait idéal dans ce cas. Un arbre rouge-noir empêcherait les choses de se déséquilibrer. Si vous avez vraiment besoin de clés, cependant, je suis sûr que vous ne pouvez pas faire mieux que d'utiliser la moyenne des clés de chaque côté de la valeur que vous devez insérer. Cela augmentera votre longueur de clé de 1 bit à chaque fois. Ce que je recommande est de renormaliser les clés périodiquement. Chaque x insertions, ou chaque fois que vous constatez que les clés sont générées trop rapprochées, renumérotent tout de 1 à n.

Édition: Vous n'avez pas besoin de comparer les clés si vous insérez par position au lieu de clé. La fonction de comparaison pour l'arbre rouge-noir utiliserait simplement l'ordre dans la liste conceptuelle, qui s'aligne avec l'ordre dans l'arbre. Si vous insérez en position 4 dans la liste, insérez un nœud à la position 4 dans l'arborescence (en utilisant la commande). Si vous insérez après un certain noeud (tel que "a"), c'est la même chose. Vous devrez peut-être utiliser votre propre implémentation si la langue/bibliothèque que vous utilisez nécessite une clé.

Answer 2

Je ne pense pas que vous puissiez éviter d'avoir des clés de taille O (n) sans réaffecter la clé pendant le fonctionnement.Comme solution pratique, je construirais un arbre de recherche inversé, avec des pointeurs des enfants aux parents, où chaque pointeur est marqué s'il provient d'un enfant gauche ou droit. Pour comparer deux éléments, vous devez trouver l'ancêtre commun le plus proche, où le chemin vers les éléments diverge.

Réaffecter des clés est alors rééquilibrer l'arbre, vous pouvez le faire par une rotation qui ne change pas l'ordre.