Una estructura de datos eficiente que admite Insert, Delete y MostFrequent

14

Supongamos que tenemos un conjunto y cada miembro de D es un par de datos y claves. Queremos una estructura de datos que soporte las siguientes operaciones:rere

  • Inserte en D ,(re,k)re
  • Eliminar miembro , (no es necesario buscar para encontrar e , por ejemplo, e apunta a un miembro en D ),mimimire
  • MostFrequent, que devuelve un miembro tal que e . k e y es una de las claves más frecuentes en D (tenga en cuenta que la clave más frecuente no necesita ser única).miree.keyD

¿Cuál sería una implementación eficiente de esta estructura de datos?

Mi solución es un montón para las teclas y sus frecuencias priorizadas por las frecuencias más una tabla hash donde la función hash asigna miembros con la misma tecla a la misma ranura en la tabla hash (con punteros de cada parte a la otra).

Esto puede dar para las dos primeras operaciones y Θ ( 1 ) para la tercera (peor tiempo de ejecución).Θ(lgn)Θ(1)

Me pregunto si hay una solución más eficiente. (¿O una solución más simple con la misma eficiencia?)

Kaveh
fuente
Si lo desea, puede usar un árbol de búsqueda binario equilibrado simple en lugar de una tabla hash.
Joe
La tabla hash utiliza mucho espacio inestable, yo propondría una cola prioritaria. Le daría la misma complejidad de tiempo al insertar y eliminar, pero la complejidad de la memoria sería mejor.
Bartosz Przybylski
@Joe, usar un BST en lugar de una tabla hash haría que las operaciones más frecuentes sean menos eficientes, pero eso podría ser una compensación razonable para la memoria.
Kaveh
2
Si solo se utilizan comparaciones, al menos uno de Insert / MostFrequent debe amortizarse , debido a los límites inferiores para el problema de distinción de elementos. Ω(logn)
Aryabhata
1
También hay algunas estructuras interesantes en el modelo de transmisión. springerlink.com/content/t17nhd9hwwry909p
Joe

Respuestas:

7

En el modelo de cálculo basado en la comparación, puede implementar la cola de prioridad utilizando un montón de Fibonacci en lugar de un montón común. Esto le dará los siguientes límites: tiempo amortizado para insertar y O ( log n ) tiempo amortizado para operaciones de eliminación.O(1)O(Iniciar sesiónnorte)

Si se aleja del modelo basado en la comparación y adopta el modelo RAM donde las claves se consideran cadenas binarias, cada una contenida en una o más palabras de máquina, puede implementar su cola prioritaria en . De hecho, puede lograr tanto para insertar como para eliminar operaciones O ( o(Iniciar sesiónnorte)yO(1)tiempo para la operación findMin. Thorup demostró queO(Iniciar sesiónIniciar sesiónnorte)O(1)

Si podemos ordenar claves en el tiempo S ( n ) por clave, entonces podemos implementar una cola prioritaria que soporte find-min en tiempo constante y actualizaciones (insertar y eliminar) en tiempo S ( n ) .norteS(norte)S(norte)

Ver M. Thorup. Equivalencia entre colas prioritarias y clasificación, 2002. en Proc. FOCS 2002

Como podemos ordenar en tiempo esperado y espacio lineal, como lo muestraO(norteIniciar sesiónIniciar sesiónnorte)

Y. Han y M. Thorup. Clasificación de enteros en tiempo esperado y espacio lineal. en Proc. FOCS 2002O(norteIniciar sesiónIniciar sesiónnorte)

El límite está probado.

Massimo Cafaro
fuente
1

Puedes hacer todo esto en tiempo amortizado esperado. El truco esencial es que no necesitamos toda la potencia de una cola prioritaria, ya que la frecuencia clave solo cambia en 1 durante cada inserción o eliminación.O(1)

Mi solución a continuación es realmente su solución con una cola de prioridad "ineficiente" que funciona bien para este caso: una cola de prioridad máxima implementada como listas doblemente vinculadas de cubos de claves tiene O (1) insertMin, deleteMax, removeFromBucket, y aumentar la clave.


Mantenga una lista doblemente vinculada de Buckets, donde cada Bucket tiene un conjunto de claves hash no vacías (que llamaré Cohorte) y un número entero positivo (que llamaré ValCount). En un Bucket b, cada clave k en la Cohorte de b tiene el mismo número de valores únicos asociados en el conjunto que está manteniendo. Por ejemplo, si su conjunto tiene los pares (a, manzana), (a, aguacate), (b, plátano), (c, pepino), (d, fruta del dragón) donde las letras individuales son las claves y las frutas son los valores, entonces tendría dos Buckets: un Bucket tendría un ValCount de 2 y una Cohorte que constaría de una sola clave: a. El otro Bucket tendría un ValCount de 1 y una Cohorte que constaría de las tres teclas b, c y d.

ValCount debe mantener ordenada la lista doblemente vinculada de Bucket. Será importante que podamos encontrar el encabezado y la cola de la lista en el tiempo y que podamos empalmar en un nuevo Cubo en O (O(1) si conocemos a sus vecinos. Inimaginablemente, llamaré a la lista de Buckets la BucketList.O(1)

Además de BucketList, necesitaremos un SetMap, que es un mapa de claves de asignación de hash a ValueBuckets. Un ValueBucket es un par que consiste en el ValueSet (un conjunto de valores hash no vacío) y un puntero no nulo a un Bucket. El ValueSet asociado con una clave k contiene todos los valores únicos asociados con k. El puntero del depósito asociado con un ValueSet tiene una Cohorte igual al tamaño del ValueSet. El Bucket asociado con una clave k en SetMap también está asociado con la clave k en 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;

Para encontrar un par clave-valor de frecuencia máxima, solo tenemos que mirar el encabezado de la lista de cubo, encontrar una clave en la cohorte, buscar esa clave en el SetMap y encontrar un valor en el ValueSet de su ValueBucket. (¡Uf!)

Insertar y eliminar pares clave-valor es más complicado.

Para insertar o eliminar un par clave-valor, primero lo insertamos o eliminamos en el SetMap Esto cambiará el tamaño del ValueSet, por lo que debemos modificar el Bucket asociado con la clave. Los únicos Buckets que tendremos que mirar para hacer este cambio serán los vecinos inmediatos del Bucket en el que solía estar la llave. Hay varios casos aquí, y probablemente no valga la pena explicarlos completamente, aunque estaría feliz para elaborar si todavía tienes problemas.

jbapple
fuente
Gracias. En realidad teníamos una idea similar para una solución, pero era un problema con ella. Tengo que comprobar cuál era el problema, ya que no lo recuerdo en este momento. Revisaré esto más cuidadosamente la próxima semana para ver si evita el problema que tenía nuestra solución.
Kaveh
Aquí hay otra manera de pensar en mi solución: en realidad es solo su solución con una cola de prioridad "ineficiente" que funciona bien para este caso. Una cola de máxima prioridad implementada como listas doblemente vinculadas de cubos de claves tiene O (1) insertMin, deleteMax, removeFromBucket y aumentarKey.
jbapple el
La forma más eficiente (en términos del peor de los casos) para mantener la asignación de claves para ValueBuckets es probablemente un árbol de búsqueda.
Raphael
Raphael: no estoy seguro de a qué te refieres. ¿Estás diciendo que las tablas hash son caras en la práctica, o que tienen un mal rendimiento en el peor de los casos, o alguna tercera cosa?
jbapple
-3

La peor complejidad del caso

O(1)

O(1)

O(1)

O(Iniciar sesiónIniciar sesiónnorte)

O(norte)

Prueba

[0 0,norte) O(losol losol metroyonorte{norte,norte})

Que se establece con una combinación de:

τ(norte,norte) norte[0 0,norte) τ(norte,norte)τ(norte,norte)τ

y:

norte[0 0,norte)O(1+losol losol norte-losol losol q)q

Referencia

Thorup, Mikkel. "Colas de prioridad de enteros con clave de disminución en tiempo constante y el problema de los caminos más cortos de una sola fuente". En las actas del trigésimo quinto simposio anual de ACM sobre teoría de la computación, 149-158. STOC '03. Nueva York, NY, EE. UU .: ACM, 2003.

A
fuente
Tenga en cuenta que en todas las colas de prioridad es trivial moverse a una estructura que soporte 'get-min' y 'extract-min' a una estructura que soporte 'get-max' y 'extract-max'.
AL
Ping ...: @Kaveh
AL