perf: optimize nested foldl in Glushkov/Matcher.lean step/initialStep (O(n²) → O(n log n))

Abierto
#14 0 comentarios 0 reacciones 0 asignados Ver en GitHub

Nadie ha tomado este issue todavía.

Evaluación

Dificultad
5/5
Tiempo estimado
Más de una semana
Aptitud para principiantes
35/100
Tipo de issue
Refactorización
Claridad
Bastante claro
Estado de actividad
Estancado
Área
compilers, performance

Línea de trabajo

Comienza en Lck/Regex/Glushkov/Matcher.lean, centrándote en step e initialStep en las líneas citadas y siguiendo sus operaciones foldl anidadas. Compara estructuras de datos candidatas para conjuntos de estados con el comportamiento actual; se considera terminado cuando se conservan los resultados de coincidencia y se reduce la complejidad por paso de O(n²) hacia O(n log n).

Escrito por el modelo de indexación a partir del texto del issue.

Descripción

Problem

The step and initialStep functions in Lck/Regex/Glushkov/Matcher.lean (lines 45-55, 65-75) use nested foldl operations that produce O(n²) complexity for large NFAs.

Impact

For a pattern with n positions, each step scans all active states and for each computes a set union — resulting in O(n²) per character of input.

Suggested Fix

Consider using a more efficient data structure (e.g., a bitset or sorted set with efficient union) to bring the per-step cost to O(n log n).

References

Raised in AI code review.

Lenguaje dominante
Lean
Estrellas
2
Forks
1
Sin PR fusionados en 30 d

Guía de contribución

No hay ninguna guía de contribución indexada para este repositorio

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de lambdaclass/lambda_compiler_kit

Todos los issues de lambdaclass/lambda_compiler_kit

Issues similares

Más issues de Compilers

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.