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

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:$D$$D$

• 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 ),$e$$e$$e$$D$
• 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).$e \in D$$e.key$$D$

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).$\Theta(\lg n)$$\Theta(1)$

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

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.$\mathcal{O}(1)$$\mathcal{O}(\log n)$

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(\log n)$etO(1)pour l'opération findMin. Thorup a prouvé que$\mathcal{O}(\sqrt{\log \log n})$$\mathcal{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 ) .$n$$S(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é par$\mathcal{O}(n \sqrt{\log \log n})$

Y. Han et M. Thorup. Tri des entiers en temps prévu et espace linéaire. dans Proc. FOCS 2002$\mathcal{O}(n \sqrt{\log \log n})$

la borne est prouvée.

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.

Complexité dans le pire des cas

$\mathcal{O}(1)$

$\mathcal{O}(1)$

$\mathcal{O}(1)$

$\mathcal{O}(\log \log n)$

$\mathcal{O}(n)$

Preuve

$[0 , N )$ $\mathrm{\mathcal{O}(log\ log\ min \{n, N\})}$

Qui est établi avec une combinaison de:

$\tau(n, N)$ $n$$[0 , N)$ $\tau ( n, N ) \le τ ( N, N)$$\tau$

et:

$n$$[0 , N)$$\mathrm{\mathcal{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.