Une structure de données efficace prenant en charge Insert, Delete et MostFrequent

14

Supposons que nous ayons un ensemble et que chaque membre de D soit une paire de données et de clés. Nous voulons une structure de données qui prendrait en charge les opérations suivantes:DD

  • Insérez dans D ,(d,k)D
  • Supprimer le membre , (pas besoin de chercher pour trouver e , par exemple e pointe vers un membre en D ),eeeD
  • MostFrequent, qui renvoie un membre tel que e . k e y est l'une des clés les plus fréquentes en D (notez que la clé la plus fréquente n'a pas besoin d'être unique).eDe.keyD

Quelle serait une mise en œuvre efficace de cette structure de données?

Ma solution est un tas pour les clés et leurs fréquences hiérarchisées par les fréquences plus une table de hachage où la fonction de hachage mappe les membres avec la même clé vers le même emplacement dans la table de hachage (avec des pointeurs de chaque partie à l'autre).

Cela peut donner pour les deux premières opérations et Θ ( 1 ) pour la troisième (pire durée de fonctionnement).Θ(lgn)Θ(1)

Je me demande s'il y a une solution plus efficace? (ou une solution plus simple avec la même efficacité?)

Kaveh
la source
Vous pouvez utiliser un arbre de recherche binaire équilibré simple au lieu d'une table de hachage si vous le souhaitez.
Joe
La table de hachage utilise beaucoup d'espace non nécessaire, je proposerais une file d'attente prioritaire. Cela vous donnerait la même complexité de temps lors de l'insertion et de la suppression, mais la complexité de la mémoire serait meilleure.
Bartosz Przybylski
@Joe, l'utilisation d'un BST à la place d'une table de hachage rendrait les opérations MostFrequent moins efficaces, mais cela pourrait être un compromis raisonnable pour la mémoire.
Kaveh
2
Si vous utilisez uniquement des comparaisons, au moins un des éléments Insert / MostFrequent doit être amorti , en raison des limites inférieures du problème de distinction des éléments. Ω(logn)
Aryabhata
1
Il existe également des structures intéressantes dans le modèle de streaming. springerlink.com/content/t17nhd9hwwry909p
Joe

Réponses:

7

Dans le modèle de calcul basé sur la comparaison, vous pouvez implémenter la file d'attente prioritaire à l'aide d'un tas Fibonacci au lieu d'un tas ordinaire. Cela vous donnera les limites suivantes: temps amorti pour l'insertion et O ( log n ) temps amorti pour les opérations de suppression.O(1)O(logn)

Si vous vous écartez du modèle basé sur la comparaison et adoptez le modèle RAM où les clés sont considérées comme des chaînes binaires, chacune contenue dans un ou plusieurs mots machine, vous pouvez implémenter votre file d'attente prioritaire dans . En effet, vous pouvez réaliser pour les opérations d'insertion et de suppression O ( o(logn)etO(1)pour l'opération findMin. Thorup a prouvé queO(loglogn)O(1)

Si nous pouvons trier clés dans le temps S ( n ) par clé, alors nous pouvons implémenter une file d'attente prioritaire prenant en charge la recherche-min en temps constant et les mises à jour (insérer et supprimer) en temps S ( n ) .nS(n)S(n)

Voir M. Thorup. Equivalence between priority queues and sorting, 2002. in Proc. FOCS 2002

Puisque nous pouvons trier dans temps prévu et espace linéaire, comme illustré parO(nloglogn)

Y. Han et M. Thorup. Tri des entiers en temps prévu et espace linéaire. dans Proc. FOCS 2002O(nloglogn)

la borne est prouvée.

Massimo Cafaro
la source
1

Vous pouvez faire tout cela en temps amorti prévu. L'astuce essentielle est que nous n'avons pas besoin de toute la puissance d'une file d'attente prioritaire, car la fréquence des clés ne change que de 1 lors de chaque insertion ou suppression.O(1)

Ma solution ci-dessous est vraiment votre solution avec une file d'attente prioritaire "inefficace" qui fonctionne bien dans ce cas: une file d'attente prioritaire maximale implémentée comme une liste doublement liée de compartiments de clés a O (1) insertMin, deleteMax, removeFromBucket et augmenter la clé.


Conservez une liste de compartiments doublement liée, où chaque compartiment a un ensemble de clés de hachage non vide (que j'appellerai une cohorte) et un entier positif (que j'appellerai le ValCount). Dans un compartiment b, chaque clé k de la cohorte de b a le même nombre de valeurs uniques qui lui sont associées dans l'ensemble que vous conservez. Par exemple, si votre ensemble contient les paires (a, pomme), (a, avocat), (b, banane), (c, concombre), (d, fruit du dragon) où les lettres simples sont les clés et les fruits sont les valeurs, vous auriez alors deux compartiments: un compartiment aurait un ValCount de 2 et une cohorte composée d'une seule clé: a. L'autre Bucket aurait un ValCount de 1 et une Cohorte composée des trois clés b, c et d.

La liste doublement liée de Bucket doit être conservée par le ValCount. Il sera important que nous puissions trouver la tête et la queue de la liste en temps et que nous pouvons épisser dans un nouveau Bucket en temps O ( 1 ) si nous connaissons ses voisins. Sans imagination, j'appellerai la liste des Buckets la BucketList.O(1)O(1)

En plus de BucketList, nous aurons besoin d'un SetMap, qui est une carte de hachage mappant les clés à ValueBuckets. Un ValueBucket est une paire composée du ValueSet (un ensemble de valeurs de hachage non vide) et d'un pointeur non nul vers un Bucket. Le ValueSet associé à une clé k contient toutes les valeurs uniques associées à k. Le pointeur Bucket associé à un ValueSet a une cohorte égale à la taille du ValueSet. Le Bucket associé à une clé k dans SetMap est également associé à la clé k dans BucketList.

En C ++:

struct Bucket {
    unsigned ValCount;
    unordered_set<Key> Cohort;
    Bucket * heavier;
    Bucket * lighter;
};
Bucket * BucketListHead;
Bucket * BucketListTail;

struct ValueBucket {
  unordered_set<Value> ValueSet;
  Bucket * bucket;
};
unordered_map<Key, ValueBucket> SetMap;

Pour trouver une paire clé-valeur de fréquence maximale, il suffit de regarder la tête de la BucketList, de trouver une clé dans la cohorte, de rechercher cette clé dans le SetMap et de trouver une valeur dans le ValueSet de son ValueBucket. (phew!)

L'insertion et la suppression de paires clé-valeur est plus délicate.

Pour insérer ou supprimer une paire clé-valeur, nous l'insérons ou la supprimons d'abord dans le SetMap Cela changera la taille du ValueSet, nous devons donc modifier le Bucket associé à la clé. Les seuls compartiments que nous devrons examiner pour effectuer ce changement seront les voisins immédiats du compartiment dans lequel se trouvait la clé. Il existe plusieurs cas ici, et ils ne valent probablement pas la peine d'être expliqués en détail, bien que je serais heureux d'élaborer si vous rencontrez toujours des problèmes.

jbapple
la source
Merci. En fait, nous avions une idée similaire pour une solution, mais cela posait problème. Je dois vérifier quel était le problème car je ne m'en souviens pas pour l'instant. Je vérifierai cela plus attentivement la semaine prochaine pour voir si cela évite le problème de notre solution.
Kaveh
Voici une autre façon de penser à ma solution: c'est vraiment votre solution avec une file d'attente prioritaire "inefficace" qui fonctionne bien dans ce cas. Une file d'attente de priorité maximale implémentée en tant que listes doublement liées de compartiments de clés a O (1) insertMin, deleteMax, removeFromBucket et augmenterKey.
jbapple
Le moyen le plus efficace (en termes de pire cas) de maintenir le mappage à partir des clés pour ValueBuckets est probablement un arbre de recherche.
Raphael
Raphael - Je ne sais pas où tu veux en venir. Êtes-vous en train de dire que les tables de hachage sont coûteuses dans la pratique, ou qu'elles ont de mauvaises performances dans le pire des cas, ou quelque chose du troisième?
jbapple
-3

Complexité dans le pire des cas

O(1)

O(1)

O(1)

O(loglogn)

O(n)

Preuve

[0,N) O(log log mjen{n,N})

Qui est établi avec une combinaison de:

τ(n,N) n[0,N) τ(n,N)τ(N,N)τ

et:

n[0,N)O(1+log log n-log log q)q .

Référence

Thorup, Mikkel. «Files d'attente de priorité entières avec clé de diminution en temps constant et problème des chemins les plus courts à source unique». Dans les actes du trente-cinquième Symposium annuel ACM sur la théorie de l'informatique, 149-158. STOC '03. New York, NY, États-Unis: ACM, 2003.

À
la source
Notez que dans toutes les files d'attente prioritaires, il est trivial de passer à une structure prenant en charge «get-min» et «extract-min» vers une structure prenant en charge «get-max» et «extract-max».
À
Ping ...: @Kaveh
AT