Visto
Programación
Google
Gemini 2.5 Flash
VS
OpenAI
GPT-5.2
Implementar una skip list concurrente sin bloqueo con consultas por rango
Diseña e implementa una estructura de datos skip list concurrente en el lenguaje de tu elección (C++, Java, Rust, Go o Python) que admita las siguientes operaciones:
1. **insert(key, value)** – Inserta un par clave-valor. Si la clave ya existe, actualiza el valor de forma atómica. Devuelve true si se insertó una clave nueva, false si se actualizó.
2. **remove(key)** – Elimina lógicamente el par clave-valor. Devuelve true si la clave se encontró y fue eliminada, false en caso contrario.
3. **find(key)** – Devuelve el valor asociado a la clave, o indica ausencia.
4. **range_query(low, high)** – Devuelve todos los pares clave-valor donde low <= key <= high, como una lista ordenada por clave. El resultado debe ser una instantánea consistente: no debe incluir claves que nunca estuvieron presentes simultáneamente durante la ejecución de la operación.
5. **size()** – Devuelve el número aproximado de elementos activos (no eliminados).
Requisitos y restricciones:
- La skip list debe ser segura para uso concurrente por múltiples hilos que ejecuten cualquier mezcla de las operaciones anteriores simultáneamente, sin un bloqueo global único. Puedes usar bloqueo de grano fino, técnicas sin bloqueo (CAS) o una combinación.
- La eliminación perezosa es aceptable: los nodos pueden marcarse lógicamente como eliminados antes de su remoción física.
- La generación probabilística de niveles debe usar una distribución geométrica estándar con p=0.5 y un nivel máximo de 32.
- Las claves son enteros de 64 bits; los valores son cadenas.
- Incluye consideraciones adecuadas de seguridad de memoria. Si usas un lenguaje sin recolector de basura, explica o implementa tu estrategia de recuperación de memoria (por ejemplo, reclamación basada en épocas (epoch-based reclamation), hazard pointers).
Entregables:
1. Código fuente completo, compilable/ejecutable, con comentarios que expliquen tu estrategia de concurrencia.
2. Una prueba o demostración que lance múltiples hilos ejecutando inserciones, eliminaciones, búsquedas y consultas por rango concurrentes, y valide la corrección (por ejemplo, sin actualizaciones perdidas, sin lecturas fantasma en las consultas por rango, sin fallos).
3. Una sección breve de análisis (como comentarios o un docstring) que discuta:
- Las garantías de linealizabilidad (o aislamiento por instantánea) que proporciona tu implementación.
- La complejidad temporal esperada de cada operación.
- Limitaciones conocidas o posibles problemas ABA y cómo los abordas.
Tu solución será evaluada en corrección bajo concurrencia, claridad del código, solidez de la estrategia de concurrencia, calidad del mecanismo de instantánea para consultas por rango y exhaustividad del análisis.
