¿Cómo implementar la memoria caché LFU usando STL?

Question

Estoy tratando de implementar la caché LFU (uso menos frecuente) usando STL puro (no quiero usar Boost!).

Los requisitos son:

• el acceso a cualquier elemento asociativo utilizando un Key como con std::map.
• Posibilidad de liberar el elemento de prioridad más baja (utilizando su atributo UsesCount).
• Posibilidad de actualizar la prioridad (UsesCount) de cualquier elemento.

Los problemas son:

• Si uso std::vector como contenedor de artículos (Key, Value, UsesCount), std::map como un contenedor de iteradores al vector para el acceso asociativo y std::make_heap, std::push_heap y std::pop_heap como implementación de cola de prioridad dentro del vector, los elementos en el mapa no son válidos después de las operaciones de pila.
• Si uso std::list (o std::map) en lugar de std::vector en la configuración anterior, std::make_heap etc. puede no ser compilado robaba sus iteradores no soporta aritméticas.
• Si me gustaría usar std::priority_queue, no tengo la capacidad de actualizar la prioridad del elemento.

Las preguntas son:

• Me estoy perdiendo algo obvio cómo este problema podría ser resuelto?
• ¿Puede indicarme alguna implementación pura de C++/STL de caché LFU que cumpla con los requisitos previos como ejemplo?

Gracias por su conocimiento.

Answer 1

Su implementación de make utilizando las funciones *_heap y un vector parece ser una buena opción. aunque dará lugar a actualizaciones lentas. El problema sobre la invalidación del iterador que encuentras es normal para cada contenedor que usa un vector como estructura de datos subyacente. Este es el enfoque también tomado por boost::heap::priority_queue, pero no proporciona una interfaz mutable por el motivo mencionado anteriormente. Otro boost::heap data-structures ofrece la posibilidad de actualizar el montón.

Algo que parece un poco extraño: incluso si pudieras usar std::priority_queue, seguirás enfrentando el problema de invalidación del iterador.

Para responder a sus preguntas directamente: No le falta algo obvio. std::priority_queue no es tan útil como debería ser. El mejor enfoque es escribir su propia implementación de almacenamiento dinámico que admita actualizaciones. Para que sea totalmente compatible con STL (especialmente con el asignador) es bastante complicado y no es una tarea sencilla. Además de eso, implementa la caché LFU.

Para el primer paso, consulte las implementaciones de Boost para tener una idea del esfuerzo. No estoy al tanto de ninguna implementación de referencia para el segundo.

Para evitar la invalidación de iteradores, siempre puede elegir indirectamente en otro contenedor, aunque debe tratar de evitarlo, ya que crea un costo adicional y puede ser bastante complicado.

Answer 2

Un enfoque algo más simple que mantener dos estructuras de datos:

• sólo seguir un mapa, que mapea las llaves a su pareja de valores/el uso de conteo.
• cuando la caché está llena:
• • crear un vector de iteradores a los elementos del mapa (O(n))
• • uso std::nth_element para encontrar el peor 10% (O(n))
• • eliminarlas todas de el mapa (O(n log n))

Por lo tanto, la adición de un nuevo elemento a la caché es caso común O(log n), peor de los casos O(n log n), y se amortiza O(log n).

Eliminar el peor 10% podría ser un poco drástico en un caché LFU, porque las nuevas entradas tienen que llegar al 90% superior o se cortan. Por otra parte, si solo quita un elemento, las nuevas entradas aún deben salir del final antes de la próxima entrada nueva, o se cortan, y tienen menos tiempo para hacerlo. Entonces, dependiendo de por qué LFU es la estrategia de almacenamiento en caché adecuada para usted, mi cambio podría ser una estrategia incorrecta, o podría estar bien.