Tasa de aciertos de caché de un feed
La misión
Problema
Un servicio de feed de noticias guarda las publicaciones vistas recientemente en una caché LRU delante de su base de datos. Dada la secuencia de ids de publicaciones que piden los lectores y la capacidad de la caché en publicaciones, reproduce las solicitudes: una solicitud de una publicación que está en caché es un acierto y la convierte en la usada más recientemente; un fallo carga la publicación en la caché y desaloja la publicación usada menos recientemente si la caché supera su capacidad. Devuelve la tasa de aciertos como porcentaje redondeado a 1 decimal. Llama a la función con varias capacidades para ver cuánto aporta cada slot extra. Hay hasta un millón de solicitudes.
Ejemplos
Input: feed = ["p1", "p2", "p1", "p3", "p1", "p2", "p4", "p1", "p5", "p2", "p1", "p3"],
capacities 1, 2, 3 and 4
Output: [0.0, 16.7, 41.7, 50.0]
Por qué: el tercer slot es el que más aporta, porque alcanza para mantener las dos publicaciones populares, p1 y p2
Input: feed = ["a", "b", "c", "a", "b", "c"], capacity = 2
Output: 0.0
Por qué: un ciclo una publicación más largo que la caché desaloja cada publicación justo antes de que se vuelva a necesitar
Input: feed = ["x", "x", "x"], capacity = 1
Output: 66.7
Por qué: caso límite: solo la primera solicitud de una publicación puede fallar
Pistas
0 / 3
Una caché LRU necesita que dos operaciones sean rápidas: buscar una publicación y encontrar la usada menos recientemente para desalojarla.
El OrderedDict de Python mantiene el orden de inserción y puede mover una clave al final. Trata el final como lo usado más recientemente y el frente como lo próximo que se desaloja.
En un acierto, cuéntalo y mueve la publicación al final. En un fallo, insértala y, si la caché ahora supera su capacidad, saca el primer elemento. Al final, divide los aciertos entre las solicitudes.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(c)
Restricciones
- at most 10⁶ requests
Solución
El tráfico de un feed está sesgado: unas pocas publicaciones reciben la mayoría de las vistas, y ese sesgo es lo que hace que valga la pena tener una caché pequeña. La simulación es una caché LRU sobre un OrderedDict: un acierto mueve la publicación al extremo de lo usado más recientemente, y un fallo la inserta y desaloja por el otro extremo cuando la caché se desborda. Correr la misma traza con varias capacidades da la curva de tasa de aciertos sobre la que debe razonar una buena respuesta de entrevista: en el primer ejemplo, la curva da un salto en cuanto la caché puede guardar las dos publicaciones populares y luego se aplana. El segundo ejemplo es el punto débil conocido de LRU, un recorrido cíclico apenas más grande que la caché, en el que la tasa de aciertos cae a cero. Cada solicitud es O(1), así que el tiempo es O(n) por capacidad y el espacio es O(c) para c publicaciones en caché.
from collections import OrderedDict
def hit_ratio(requests, capacity):
cache, hits = OrderedDict(), 0 # front = least recently used
for post in requests:
if post in cache:
hits += 1
cache.move_to_end(post) # now the most recently used
else:
cache[post] = True
if len(cache) > capacity:
cache.popitem(last=False) # evict the least recently used
return round(100 * hits / len(requests), 1)
feed = ["p1", "p2", "p1", "p3", "p1", "p2", "p4", "p1", "p5", "p2", "p1", "p3"]
print([hit_ratio(feed, c) for c in (1, 2, 3, 4)]) # -> [0.0, 16.7, 41.7, 50.0]
print(hit_ratio(["a", "b", "c", "a", "b", "c"], 2)) # -> 0.0
print(hit_ratio(["x", "x", "x"], 1)) # -> 66.7¿Lo que te frena es la idea y no el código? Diseña una caché distribuida lo explica.