Indexer le nombre de seaux

Question

Donc, voici mon petit problème.

Disons que j'ai une liste des seaux un ... un _n qui contiennent respectivement L < = c ... c _n < articles H. Je peux décider des limites L et H. Je pourrais même les mettre à jour dynamiquement, bien que je ne pense pas que cela aiderait beaucoup.

L'ordre des godets est important. Je ne peux pas aller les échanger.

Maintenant, je voudrais indexer ces seaux de sorte que:

• Je sais que le nombre total d'articles
• Je Recherch l'élément ième
• je peux ajouter/supprimer des éléments à partir de n'importe quel compartiment et mettre à jour l'index efficacement

Cela semble facile non? En voyant ces critères, j'ai immédiatement pensé à un arbre Fenwick. C'est ce à quoi ils sont destinés.

Cependant, quand vous pensez au sujet des cas d'utilisation, quelques autres cas d'utilisation fluage:

• si un nombre de seau tombe en dessous de L, le seau doit disparaître (ne vous inquiétez pas encore sur les articles)
• si un nombre seau atteint H, un nouveau seau doit être créé, car celui-ci est plein

Je n'ai pas compris comment modifier un arbre Fenwick efficacement: supprimer/ajouter un nœud sans reconstruire le arbre entier ...

Bien sûr, nous pourrions configurer L = 0, de sorte que la suppression deviendrait inutile, mais l'ajout d'éléments ne peut pas vraiment être évité.

Voici donc la question:

Savez-vous soit une meilleure structure pour cet indice ou comment mettre à jour un arbre Fenwick? La préoccupation principale est l'efficacité, et parce que j'ai l'intention de mettre en œuvre des considérations de mémoire cache/mémoire valent la peine d'inquiétude.

Contexte:

J'essaie de trouver une structure quelque peu similaire à B-Arbres et listes Classé Passer mais avec un index localisé. Le problème de ces deux structures est que l'index est conservé le long des données, ce qui est inefficace en terme de cache (c'est-à-dire que vous devez récupérer plusieurs pages de la mémoire). Les implémentations de base de données suggèrent que garder l'index isolé des données réelles est plus favorable au cache, et donc plus efficace.

Answer 1

Je comprends bien votre problème:

Chaque godet a un ordre interne et se seaux ont un ordre, de sorte que tous les éléments ont une commande et vous devez l'élément ième dans cette commande.

Pour résoudre que:

Ce que vous pouvez faire est de maintenir un arbre « valeur cumulative » où les nœuds feuilles (x1, x2, ..., xn) sont les tailles de godet. La valeur d'un nœud est la somme des valeurs de ses enfants immédiats. Garder n une puissance de 2 le rendra simple (vous pouvez toujours le remplir avec des seaux de taille zéro à la fin) et l'arbre sera un arbre complet.

En correspondance avec chaque compartiment, vous conservez un pointeur sur le nœud feuille correspondant.

Par exemple, disons que les dimensions des godets sont 2,1,4,8.

L'arbre ressemblera

 15 
    /\ 
    3 12 
/\/\ 
2 1 4 8 

Si vous voulez que le nombre total, lisez la valeur du nœud racine.

Si vous souhaitez modifier certaines valeurs xk (c'est-à-dire modifier la taille de compartiment correspondante), vous pouvez parcourir l'arborescence en suivant les pointeurs parents, en mettant à jour les valeurs.

Par exemple, si vous ajoutez 4 éléments au deuxième seau, il sera (les nœuds marqués avec * sont ceux qui ont changé)

 19* 
    / \ 
    7* 12 
/\ /\ 
2 5* 4 8 

Si vous voulez trouver l'élément ième, vous marchez dans la au-dessus de l'arbre, effectuant efficacement la recherche binaire. Vous avez déjà un enfant gauche et l'enfant droit compte. Si je> quitté la valeur de nœud enfant du nœud actuel, vous soustrayez la valeur de nœud enfant gauche et recurse dans l'arborescence droite. Si i < = la valeur du noeud enfant gauche, vous allez à gauche et recurse à nouveau.

que vous vouliez trouver le 9 élément dans l'arbre ci-dessus:

Depuis l'enfant gauche de la racine est 7 < 9. Vous soustrayez 7 de 9 (pour obtenir 2) et allez à droite.

Depuis 2 < 4 (l'enfant de gauche de 12), vous allez à gauche.

Vous êtes au noeud feuille correspondant au troisième compartiment. Vous devez maintenant choisir le deuxième élément dans ce seau. Si vous devez ajouter un nouveau compartiment, doublez la taille de votre arbre (si nécessaire) en ajoutant une nouvelle racine, en faisant de l'arbre existant l'enfant de gauche et ajoutez un nouvel arbre avec tous les seaux sauf celui ajouté (que nous sommes la feuille la plus à gauche du nouvel arbre). Ce sera amorti O (1) temps pour ajouter une nouvelle valeur à l'arbre. Attention, vous pouvez seulement ajouter un seau à la fin, et pas n'importe où au milieu.

Obtenir le nombre total est O (1). La mise à jour d'un seul compartiment/recherche d'élément est O (logn).

L'ajout d'un nouveau compartiment est amorti O (1).

L'utilisation de l'espace est O (n). Au lieu d'un arbre binaire, vous pouvez probablement faire la même chose avec un arbre binaire.

Answer 2

J'espère toujours des réponses, mais voici ce que j'ai pu trouver jusqu'ici, suite à la suggestion @Moron.

Apparemment mon petit Fenwick Tree idée ne peut pas être facilement adapté. Il est facile d'ajouter de nouveaux seaux à la fin du fenwick tree, mais pas au milieu, donc c'est une sorte de cause perdue.

Il nous reste 2 structures de données: les arbres indexés binaires (ironiquement le nom que Fenwick a utilisé pour décrire sa structure) et la liste des sauts classés.

En général, cela ne sépare pas les données de l'indice, mais nous pouvons obtenir ce comportement:

1. Utilisation indirection: l'élément tenu par le noeud est un pointeur sur un seau, et non le seau lui-même
2. Utilisez l'allocation de la piscine afin que les éléments d'index, même quoiqu'imputé indépendamment les uns des autres, sont encore proches en mémoire qui doit aide le cache

J'ont tendance à préférer les listes de saut à arbres binaires car ils sont auto organisation, donc je suis spa rouge la peine de constamment rééquilibrer mon arbre.

Ces structures permettraient d'accéder à l'élément ith en O(log N), je ne sais pas s'il est possible d'obtenir des performances asymptotiques plus rapides.

Un autre détail d'implémentation intéressant est J'ai un pointeur vers cet élément, mais d'autres ont peut-être été insérés/supprimés, comment puis-je connaître le rang de mon élément maintenant?

Il est possible que le compartiment pointe vers le nœud qui le possède. Mais cela signifie que le nœud ne doit pas bouger ou qu'il doit mettre à jour le pointeur du seau lorsqu'il est déplacé.