PLY: ¿analiza rápidamente listas largas de elementos?

Estoy trabajando con un programa de análisis bastante simple en PLY, y una de mis reglas adquiere la siguiente forma:PLY: ¿analiza rápidamente listas largas de elementos?

def p_things(p): 
    ''' 
    things : thing things 
    things : thing 
    ''' 
    p[0] = [p[1]] 
    if len(p) == 3: 
     p[0] += p[2]

archivos de entrada son generalmente simples listas de thing s, por lo que el análisis en sí no es compleja . Sin embargo, algunos de mis archivos de entrada son muy grandes (más de 100.000 líneas con bastante regularidad y más de 1.000.000 en casos extremos). En la creación de perfiles (a través de cProfile and pstats), la mayor parte del tiempo de ejecución se utiliza para llamadas repetidas al p_things, presumiblemente, una llamada para cada elemento en una lista things.

¿Hay alguna manera de reducir este tiempo, o una forma más eficiente de estructurar esta regla? La mayoría de las respuestas que he visto hasta ahora (y la información de los compiladores canónicos que he encontrado) han enumerado este método como la forma generalmente aceptada de construir una lista de elementos analizables, sin importar la longitud.

Fuente

2011-06-20 Tim

Resulta que estoy olvidando parte de mi teoría básica de compiladores. PLY es un LALR (1) analizador, y lo que es mejor escribir la regla como:

def p_things(p): 
    ''' 
    things : things thing 
    things : thing 
    ''' 
    if len(p) == 2: 
     p[0] = [p[1]] 
    else: 
     p[0] = p[1] 
     p[0].append(p[2])

Aunque puede parecer más prolija, en realidad hay una mejora significativa - en algún lugar, ya sea en capas o Python, el analizador fue capaz para aplicar alguna optimización en la forma recursiva izquierda. He visto caer el rendimiento de exponencial a lineal en mis archivos de entrada más grandes; una muestra, con más de un millón de elementos en la lista things, se ejecutó en menos del 20% del tiempo.

Fuente

2011-06-21 18:21:30 Tim

Esto no es un problema de análisis en sí mismo - en su método original 'p [0] + = p [2]' se ejecuta linealmente a la longitud de la lista cada vez que agrega una nueva 'cosa', por lo que se analiza una lista toma tiempo cuadrático, mientras que en su nuevo método, al agregar un nuevo elemento 'p [0] .append (p [2])' se ejecuta el tiempo constante amortizado, por lo que, en general, el análisis de la lista requiere tiempo lineal. – math4tots

Secundario: divida su regla en dos, digamos una con el sufijo '_iter' y la otra con' _end'. Como los documentos de PLY ya lo recomiendan, la declaración de selección simplemente duplica el trabajo ya realizado por el mismo analizador para distinguir entre los dos casos en la regla de producción. Esto ahorrará algo de cálculo, pero no está relacionado con la observación de una mejora en la eficiencia. –

Si tiene un archivo de datos con un encabezado complejo que requiere PLY y una cola enorme de datos muy simples, entonces considere dividir la entrada en dos partes. Pase el primero (pequeño) a PLY, y maneje el segundo en una iteración simple por línea, que divide cada línea de forma léxica (por ejemplo, si es una tupla de 3 coordenadas). –

Sin cambiar su código, podría intentar usar la versión "PyPy" de python con compilación just-in-time; podría ejecutar su código mucho más rápido que el CPython normal.

Fuente

2011-06-20 20:39:46

Si se gasta "la mayor parte del tiempo" en esa función, es mucho más un problema de complejidad, que la implementación de lenguaje * no * puede resolver (excepciones para * muy * analizadores inteligentes que miran * muy * casos simples). – delnan

buena sugerencia, pero desafortunadamente me encuentro con algunos problemas de compatibilidad con PyPy (PLY es, en este caso, incrustado bastante profundo en algunos otros paquetes que como CPython tal vez más de lo que deberían). Además, @delnan probablemente tenga un punto: esto me parece más un problema de complejidad en tiempo de ejecución que compilación. – Tim

PLY: ¿analiza rápidamente listas largas de elementos?

Respuesta

Cuestiones relacionadas