Visto
NEW
Programación
Google
Gemini 2.5 Flash
VS
OpenAI
GPT-5.4
Implementar una caché LRU concurrente sin bloqueo global
Implementa una caché LRU (Least Recently Used) segura para subprocesos en Python que admita lecturas y escrituras concurrentes sin usar un bloqueo global para cada operación. Tu implementación debe cumplir los siguientes requisitos:
1. **Interfaz**: La caché debe soportar estas operaciones:
- `__init__(self, capacity: int)` — Inicializa la caché con una capacidad máxima dada (entero positivo).
- `get(self, key: str) -> Optional[Any]` — Devuelve el valor asociado a la clave si existe (y lo marca como utilizado recientemente), o devuelve `None` si la clave no está en la caché.
- `put(self, key: str, value: Any) -> None` — Inserta o actualiza el par clave-valor. Si la caché excede la capacidad después de la inserción, expulsa el elemento menos recientemente usado.
- `delete(self, key: str) -> bool` — Elimina la clave de la caché. Devuelve `True` si la clave estaba presente, `False` en caso contrario.
- `keys(self) -> List[str]` — Devuelve una lista de todas las claves actualmente en la caché, ordenadas desde la más recientemente usada hasta la menos recientemente usada.
2. **Concurrencia**: La caché debe ser segura para ser usada desde múltiples hilos simultáneamente. Apunta a un diseño que permita que las lecturas concurrentes procedan sin bloquearse entre sí cuando sea posible (por ejemplo, utilizando locks de lectura/escritura, bloqueo fino por fragmentos, o técnicas lock-free). Un mutex global único que serialice cada operación se considera una solución básica pero subóptima.
3. **Corrección bajo contención**: Bajo acceso concurrente, la caché nunca debe devolver datos obsoletos o corrompidos, nunca debe exceder su capacidad indicada y debe mantener un orden LRU consistente.
4. **Casos límite a manejar**:
- Capacidad de 1
- `put` con una clave que ya existe (debe actualizar el valor y moverla a la más reciente)
- `delete` de una clave que no existe
- `put` y `get` concurrentes sobre la misma clave
- Evicciones secuenciales rápidas cuando muchos hilos insertan simultáneamente
5. **Pruebas**: Incluye una función de prueba `run_tests()` que demuestre la corrección de todas las operaciones tanto en escenarios mono-hilo como multi-hilo. La prueba multi-hilo debe usar al menos 8 hilos que realicen una mezcla de operaciones `get`, `put` y `delete` sobre claves superpuestas, y debe afirmar que la caché nunca excede la capacidad y que `get` nunca devuelve un valor para una clave que nunca fue insertada.
Proporciona tu implementación completa en Python. Usa únicamente la biblioteca estándar (sin paquetes de terceros). Incluye docstrings y comentarios que expliquen tu estrategia de concurrencia y cualquier compensación de diseño que hayas hecho.