data-structures - resolucion - tablas hash estructura de datos

Estructura de datos para devolver eficientemente las entradas K superiores de una tabla hash(mapa, diccionario) (8)

Aquí hay una descripción:

Funciona como un mapa normal con los métodos get , put y remove , pero tiene un getTopKEntries(int k) para obtener los elementos K superiores, ordenados por la clave:

Para mi caso de uso específico, estoy agregando, eliminando y ajustando una gran cantidad de valores en la estructura, pero en cualquier momento hay aproximadamente 500-1000 elementos; Quiero devolver las entradas de las 10 teclas principales de manera eficiente.

Llamo a los métodos de put y remove muchas veces.
Llamo al método getTopKEntries .
Llamo a los métodos de put y remove algunas veces más.
Llamo al método getTopKEntries .
...

Estoy esperando O (1) get , put y remove operaciones, y que getTopKEntries dependa solo de K, no del tamaño del mapa.

Entonces, ¿qué es una estructura de datos para devolver eficientemente los elementos de K superiores de un mapa?

Mi otra pregunta es similar, pero es para el caso de devolver todos los elementos de un mapa, ordenados por la clave.

Si ayuda, tanto las claves como los valores son enteros de 4 bytes.

A menos que sea severamente poco creativo hoy, simplemente no puedes hacerlo todo en O (1).

Si está manteniendo un orden de clasificación, entonces agrega y borra probablemente estará en O (log n). Si no lo eres, entonces tu búsqueda tendrá que ser O (n).

Las tablas hash simplemente no hacen la clasificación. Sugiero que viva con el O (log n) para insertar y eliminar y use una de las estructuras de datos sugeridas (Heap es probablemente el mejor). Si necesita O (1) búsquedas, podría combinar un hash, pero luego mantendrá dos estructuras de datos en paralelo y podría usar un TreeMap.

Es posible que desee un montón (aunque la eliminación puede ser un problema).

No estoy seguro de aceptar totalmente la opinión de Konrad de que muchas operaciones de eliminación destruirían la estructura de una tabla hash.

Sin operaciones de eliminación, puede mantener todos los objetos en una tabla hash y mantener la parte superior K en un montón de prioridad que se actualizará incrementalmente. Esto haría insertar O (1 + log K), es decir, tiempo constante en N, suponiendo que K es constante y no depende de N (N = número de objetos en la tabla). Sin embargo, esto no funciona cuando tienes la operación de eliminación disponible. El montón de Fibonacci propuesto tiene una operación de eliminación amortiguada O (log N), por lo que tampoco proporciona una buena solución, ya que todos los objetos deberían mantenerse en el montón, y si finalmente elimina cada objeto que inserta, obtiene Comportamiento O (log N) en general por un par de inserción + eliminar.

Tal vez intente el siguiente enfoque:

Almacene los objetos en una tabla hash, suponiendo que necesita toda la tabla para otros fines distintos de devolver los objetos superiores. Mantenga un montón de prioridad (va el montón estándar) que contiene objetos K * C para C cuyo valor necesita buscar experimentalmente. Siempre que agregue un objeto nuevo, intente insertarlo en el montón; si cabe en el espacio K C (el montón todavía no está en su capacidad o empuja a otro objeto), insértelo y establezca un bit en la tabla hash para indicar que el objeto está en el montón; cuando empujas un objeto fuera del montón, borra la broca. Cuando eliminas un objeto, verifica el bit; si el bit = 1, es decir, el objeto estaba en el montón, quítelo de allí (debe buscarlo, a menos que tenga un puntero desde la tabla hash; lo mejor es mantener el puntero). Lo que sucede ahora es que el montón se reduce. Lo más importante es que , mientras el montón tenga todavía al menos objetos K , se garantiza que contendrá todos los objetos K superiores. Aquí es donde entra el factor C ya que proporciona el "margen" para el montón. Cuando el tamaño del montón cae por DEBAJO de K, ejecuta un escaneo lineal sobre toda la tabla hash y llena el montón hasta la capacidad KC .

La configuración C es empírica porque depende de cómo vayan apareciendo y desapareciendo los objetos; pero ajustarlo debería ser fácil, ya que puedes sintonizarlo solo en función del perfil de tiempo de ejecución.

Complejidad: Insertar es O (1 + log (KC)). Eliminar es O (1 + p log (KC) + q N) donde p es la probabilidad de que un objeto eliminado esté en el montón, y q es la probabilidad de que el montículo necesite ser reconstruido. p depende de las características de cómo van y vienen los objetos. Para un análisis simple podemos establecer p = (KC / N), es decir, asumir una probabilidad uniforme. q es aún más sensible al "flujo" de los objetos. Por ejemplo, si los objetos nuevos en general aumentan su valor a lo largo del tiempo y siempre se eliminan los objetos más antiguos, q tiende a cero.

Tenga en cuenta que, curiosamente, p es inversamente proporcional a N, por lo que en realidad esta parte se acelera cuando N crece :)

Un árbol binario de búsqueda (es decir, std::map en C ++) suena como la estructura perfecta: ya está ordenado lexicográficamente, es decir, un recorrido en orden simple producirá los elementos en orden ascendente. Por lo tanto, iterar sobre los primeros k elementos arrojará los elementos k superiores directamente.

Además, dado que prevé muchas operaciones de "eliminación", una tabla hash no será adecuada de todos modos: las operaciones de eliminación destruyen las características del factor de carga de las tablas hash lo que provoca un rápido deterioro del tiempo de ejecución.

Una alternativa sería simplemente ordenar los artículos.

En su escenario de uso solo hay 1000 elementos; ordenarlos es increíblemente rápido (recuerde que log ₂ 1000 ≈ 10 = casi 1), y parece que no ocurre con demasiada frecuencia.

Incluso puede adaptar el algoritmo de selección para devolver los elementos K más pequeños. Desafortunadamente, esto todavía dependerá de n , no solo de k como esperabas: O ( n + k log k ).

(He agregado esto como una nueva respuesta porque en realidad no está relacionado con mi primera entrada).

Yo recomendaría un montón de fibonacci .

Si la clave de clasificación es un entero simple o un número decimal, un trie será bastante rápido. Se agotará la memoria, y técnicamente encontrar un elemento en un trie es O (log n). Pero en la práctica será algo así como log ₂₅₆ n, por lo que el factor constante es muy pequeño (log ₂₅₆ de 2 mil millones = 4).

Creo que el montón es la mejor estructura de datos para este problema. Porque, poner, quitar y devolver K los elementos superiores se pueden devolver en O (klog (N)) vez. Usa un montón máximo si quieres elementos máximos.

Aquí, supongo que k elementos superiores significa que necesita los elementos k que tienen el valor máximo.