Recientemente menos caché usada de C ++

Question

Estoy tratando de implementar LRU caché usando C ++. Me gustaría saber cuál es el mejor diseño para su aplicación. Sé LRU debe proporcionar find (), agregar un elemento y eliminar un elemento. La remove debe retirar el elemento LRU. Cuál es la mejor TDAs para implementar esta Por ejemplo: Si utilizo un mapa con elemento como el valor y el contador de tiempo como tecla puedo buscar O tiempo en (log n), Insertar es O (n), la eliminación se aplican O (log n)

.

Answer 1

Un problema importante con las memorias caché LRU es que hay poca operaciones "const", la mayoría va a cambiar la representación subyacente (aunque sólo sea porque golpee el elemento visitada).

Esto es por supuesto muy incómodo, ya que significa que no es un contenedor STL tradicional, y por lo tanto cualquier idea de exhibir iteradores es bastante complicado: cuando el iterador es sin referencia que se trata de un acceso, que debe modificar la lista estamos iterando ... oh mi.

Y hay la consideración actuaciones, tanto en términos de velocidad y el consumo de memoria.

Es desafortunado, pero necesitará una cierta manera de organizar los datos en una cola (LRU) (con la posibilidad de eliminar elementos de la media) y esto significa que sus elementos tendrán que ser independiente el uno del otro. A encaja std::list, por supuesto, pero es más de lo que necesitan. Una lista simplemente enlazada es suficiente aquí, ya que no es necesario para recorrer la lista hacia atrás (lo que desea es una cola, después de todo).

Sin embargo, un inconveniente importante de los pobres es su localidad de referencia, si se necesita más velocidad que necesita para proporcionar su propia costumbre asignador (piscina?) Para los nodos, de manera que se mantienen lo más cerca posible. Esto también aliviará la fragmentación del montón un poco.

A continuación, es obvio que necesita una estructura de índice (por el bit de memoria caché). El más natural es dar vuelta hacia un mapa hash. std::tr1::unordered_map, std::unordered_map o boost::unordered_map son normalmente aplicación de buena calidad, algunos deben estar disponibles para usted. También le asignan nodos adicionales para el manejo de hash de colisión, es posible que prefiera otro tipo de mapas de hash, echa un vistazo a artículo de Wikipedia sobre el tema y leer acerca de las características de las distintas técnicas de aplicación.

Continua, está el (obvio) de soporte roscado. Si usted no necesita soporte de hilos, entonces está bien, si lo hace, sin embargo, es un poco más complicado:

• Como ya he dicho, hay poca operación const en una estructura de este tipo, por lo que no necesita realmente para diferenciar lectura / escritura accesos
• bloqueo interno está muy bien, pero es posible encontrar que no se lleva bien con sus usos. El problema con bloqueo interno es que no es compatible con el concepto de "transacción", ya que renunciar a la cerradura entre cada llamada. Si este es su caso, transformar su objeto en un mutex y proporcionar un método std::unique_ptr<Lock> lock() (en la depuración, se puede afirmar que el bloqueo se toma en el punto de entrada de cada método)
• Hay (en estrategias de bloqueo) la emisión de reentrada, es decir, la capacidad de "rebloqueo" el mutex desde dentro del mismo hilo, comprobar Boost.Thread para obtener más información sobre las distintas cerraduras y mutexes disponible

Por último, está el tema de los informes de errores. Dado que se espera que una memoria caché puede no ser capaz de recuperar los datos que usted pone en, me gustaría considerar el uso de una excepción "mal gusto". Considerar o bien punteros (Value*) o Boost.Optional (boost::optional<Value&>). Yo preferiría Boost.Optional porque su semántica es clara.

Answer 2

La mejor manera de implementar un LRU es utilizar la combinación de un std :: lista y stdext :: hash_map (querer usar std mapa sólo entonces std ::).

• almacenar los datos en la lista para que la menos recientemente utilizado en el durar y utilizar el mapa para que señale el elementos de la lista.
• Para "conseguir" utilizar el mapa para obtener el Lista addr y recuperar los datos y mover el nodo actual a la Red en primer lugar (ya que este fue utilizado ahora) y actualizar el mapa.
• Para "insertar" eliminar el último elemento de la lista y añadir los nuevos datos en la parte delantera y actualizar el mapa.

Este es el más rápido usted puede conseguir, si está utilizando un hash_map debe tener casi todas las operaciones realizadas en O (1). Si se utiliza std :: Mapa que debe tomar O (log n) en todos los casos.

Una muy buena aplicación está disponible aquí

Answer 3

artículo describe un par de implementaciones de caché LRU C ++ (STL usando uno, usando una boost::bimap ).

Answer 4

Cuando dice prioridad, creo " montón ", que conduce naturalmente a aumento de clave y delete-min .

Answer 5

No haría que el caché visible para el mundo exterior en absoluto si podía evitarlo. Yo sólo tendría una colección (de lo que sea) y usa el almacenamiento en caché de forma invisible, añadir y eliminar elementos, según sea necesario, pero la interfaz externa sería exactamente la de la colección subyacente.

En cuanto a la aplicación va, un montón es probablemente la más obvia. Tiene complejidades más o menos similares a un mapa, pero en vez de construir un árbol de nodos enlazados, que organiza los elementos de una matriz y los "enlaces" están implícitos en base a los índices de matriz. Esto aumenta la densidad de almacenamiento de la memoria caché y mejora la localidad en la memoria caché "real" (física) del procesador.

Answer 6

montón y tal vez un Fibonacci Heap

Answer 7

me gustaría ir con un montón normales en C ++.

Con el std :: make_heap (garantizado por la norma para ser O (n)), std :: pop_heap y std :: push_heap en # include, poniendo en práctica sería absolutamente pastel. Usted sólo tiene que preocuparse de aumento de clave.