¿Cómo diseñar un último caché usado recientemente?

Question

¿Cómo diseñar un último caché usado recientemente?

Supongamos que ha visitado algunos artículos. Debe diseñar una estructura de datos para contener estos elementos. Cada artículo está asociado con el último tiempo visitado.

Cada vez que visite un elemento, verifíquelo en la estructura de datos. Si el artículo ha estado en el caché, actualice su tiempo de visita. De lo contrario, inserte en el caché. El tamaño de la memoria caché es fijo, si está lleno, elimine el elemento más antiguo.

Mi solución:

1. Use un mapa <elemento, visittime>

2. Initalización: ordene el mapa con f (visittime) con orden descendente. O (nlg n)

3. Si se visita un elemento, búscalo en el mapa con o (lg n).

4. Si ha estado en el mapa, actualice el tiempo o (1). Ordene el mapa o (lg n).

5. Si no, inserte en el mapa y luego ordene. O (lg n)

6. Si el tamaño del mapa> tamaño fijo, elimine el último elemento o (1).

Otra solución:

1. Use hashtable <item, VisitTime>

2. Ordíelo o (n lgn).

3. Si se visita un artículo, búscalo en el talbe con o (1).

4. Si ha estado en la tabla, actualice el tiempo o (1). Ordene la tabla o (n lg n).

5. Si no, inserte en la tabla y luego ordene. O (n lg n)

6. Si el tamaño de la tabla> Tamaño fijo, elimine el último elemento O (1).

¿Hay mejores soluciones? En) ?

Answer 1

Si usa una lista doblemente vinculada, obtendrá o (1) inserción (después de la búsqueda), o (1) eliminación, o (n) búsqueda.

Suponiendo que inserte nuevos elementos en el frente:

Si el caché no está lleno, simplemente agregue al frente (o (1)).

Si necesita actualizar un elemento, busque (o (n)), elimínelo de la lista vinculada (o (1)), luego agregue al frente (o (1)).

Si necesita eliminar el más antiguo para insertar un nuevo elemento, elimine el elemento final (o (1)) e inserte al frente (o (1)) [Nota: debe buscar primero la lista en este caso para ver Si el elemento aún no está en el caché, entonces o (n)].

Una lista vinculada también puede darle el mismo tiempo, ya que la búsqueda lo dejará en el último elemento.

Answer 2

Cache LRU de Python tiene o (1) inserción, eliminación y búsqueda. Su diseño utiliza una lista doblemente vinculada de entradas (dispuestas más antiguas a más nuevas) y una tabla hash para localizar un enlace particular.

Aquí hay una versión simplificada (pero rápida) en menos de 40 líneas de Python muy básica. No debería ser difícil traducir la solución de Python en C ++:

class LRU_Cache(object):

    def __init__(self, original_function, maxsize=1000):
        self.original_function = original_function
        self.maxsize = maxsize
        self.mapping = {}

        PREV, NEXT, KEY, VALUE = 0, 1, 2, 3
        self.head = [None, None, None, None]        # oldest
        self.tail = [self.head, None, None, None]   # newest
        self.head[NEXT] = self.tail

    def __call__(self, *key):
        PREV, NEXT, KEY, VALUE = 0, 1, 2, 3
        mapping, head, tail = self.mapping, self.head, self.tail
        sentinel = object()

        link = mapping.get(key, sentinel)
        if link is sentinel:
            value = self.original_function(*key)
            if len(mapping) >= self.maxsize:
                oldest = head[NEXT]
                next_oldest = oldest[NEXT]
                head[NEXT] = next_oldest
                next_oldest[PREV] = head
                del mapping[oldest[KEY]]
            last = tail[PREV]
            link = [last, tail, key, value]
            mapping[key] = last[NEXT] = tail[PREV] = link
        else:
            link_prev, link_next, key, value = link
            link_prev[NEXT] = link_next
            link_next[PREV] = link_prev
            last = tail[PREV]
            last[NEXT] = tail[PREV] = link
            link[PREV] = last
            link[NEXT] = tail
        return value

if __name__ == '__main__':
    p = LRU_Cache(ord, maxsize=3)
    for c in 'abcdecaeaa':
        print(c, p(c))

Answer 3

Puedes hacerlo en Java con el java.util.linkedhashset. Es una tabla hash junto con una lista vinculada que conserva el orden en que se insertaron los elementos. Debería obtener una búsqueda (esperada) de tiempo constante, inserciones y eliminaciones si la dispersión clave funciona bien.

Es posible que también desee mirar Débthashmap que implementa un mecanismo automatizado donde los elementos pueden ser recolectados de basura.

Answer 4

Use dos colecciones que compartan los mismos datos. Tener un hashtable y una lista. Use hashtable para verificar si existe el elemento y encontrarlo en la lista (el valor del mapa hash es iterador de lista). Use la lista para mantener el orden entre los elementos. Sincronice dos colecciones (al eliminar el elemento de la lista, elimine el elemento correspondiente de Hashtable). El iterador de la lista debe ser tal que no cambie cuando reubica el elemento dentro de la lista.

Editar: std :: list iterator es válido a lo largo de la adición y eliminación de elementos, siempre que el iterador mismo se hace referencia al iterador mismo no se elimina. Ver las últimas líneas en la sección Capacidad y asignación En Wikipedia.

Answer 5

Realmente no tienes que clasificar el contenedor. Simplemente agregue los elementos al mapa o el vector, y revise linealmente para encontrar el elemento necesario (o el elemento más antiguo).

Entonces será O(n).

Answer 6

Mira esto Boost :: multi_index. Uno de los ejemplos que muestra es un Lista de mru.