Manipulación de cadenas en Cython

Question

Tengo un código que hace algunas manipulaciones de cadenas con uso intensivo de la CPU y estaba buscando formas de mejorar el rendimiento.

(EDIT:. Estoy haciendo cosas como encontrar subcadena común más larga, corriendo un montón de expresiones regulares que podrían ser mejor expresan como máquinas de estado en C, pelar los comentarios de HTML, cosas por el estilo)

soy Actualmente se está estudiando la posibilidad de portar parte del código al Cython después de escuchar muchas cosas buenas al respecto. Sin embargo, parece que el foco principal de Cython son los cálculos numéricos y el trabajo con cadenas apenas está documentado.

Unicode también podría ser un gran problema.

Mis preguntas son:

1. Debería de molestarse con el Cython para la materia de la cadena? ¿Alguien tiene experiencia con este tipo de procesamiento en cython y puede compartir?
2. ¿Me falta algo en los documentos de Cython? ¿Alguien sabe de un tutorial/referencia/documentación sobre el trabajo con cadenas en Cython?

Answer 1

He votado por la respuesta del 'perfil', pero quería agregar esto: siempre que sea posible, la mejor optimización que puede hacer es usar bibliotecas estándar de Python o funciones integradas para realizar las tareas que desee. Estos se implementan típicamente en C y proporcionarán un rendimiento en general equivalente a cualquier extensión, incluidas las extensiones escritas en Cython. Si tus algoritmos realizan bucles de carácter por carácter en Python, estos deberían ser los primeros en llegar, si es posible.

Pero si tiene algoritmos que no se pueden volver a trabajar en términos de integradas u otras bibliotecas estándar existentes, Cython parece un enfoque razonable. Simplemente compila pseudo-Python hasta código nativo y es tan adecuado para operaciones de cadena como cualquier otra operación, realmente. Pero no estoy convencido de que veas un gran beneficio de usar Cython si solo le das un código idiomático de Python. El beneficio máximo vendrá si puede volver a escribir algunos o todos los algoritmos en C, de modo que las operaciones de bajo nivel no traduzcan constantemente variables a través de la barrera Python/C.

Finalmente, Unicode: ha implicado que podría ser "un gran problema" pero no ha especificado cómo lo está usando. Supuestamente, Cython producirá un código C que llama a las API de Python relevantes que manejan Unicode, por lo que es poco probable que la funcionalidad sea limitada. Sin embargo, manejar cadenas Unicode en C no es trivial y puede significar que la idea de reescribir algunos de sus algoritmos en C para un mejor rendimiento no vale la pena el esfuerzo. Muchos algoritmos de cadenas clásicas simplemente no funcionarán en muchas codificaciones Unicode, que no son 'cadenas' en el sentido tradicional de tener 1 unidad de almacenamiento por carácter.

Answer 2

Este es un problema muy interesante. Cython en su núcleo es una herramienta para integrar python con tipos de datos C. No proporciona ninguna funcionalidad para ayudar en el tratamiento de cadenas, probablemente porque no hay tanta demanda para eso como para la funcionalidad específica de Numpy.

Habiendo dicho eso, podrías usar Cython para interactuar con bibliotecas C/C++ existentes diseñadas para manejar los tipos de problemas que describes. Para procesar HTML/XML, puede buscar en libxml, por ejemplo. Sin embargo, hay (por supuesto) ready-made python bindings ya disponible para eso. He utilizado lxml extensivamente para procesar HTML y hace todo lo que necesito y lo hace rápido, además maneja unicode bastante bien.

En su caso, me imagino que una combinación de lxml y funciones C personalizadas sería lo mejor. Por ejemplo, podría "fácilmente" hacer una función rápida para encontrar subcadenas más largas en C, ya que eso podría hacerse a nivel de byte (recuerde que una cadena en C es solo una char *, que es una matriz de bytes). Entonces podrías mapearlos de vuelta a Python (que Cython te facilitará mucho) y continuar en el cielo unicode abstraído :). Ciertamente, no es trivial, pero puede valer la pena el esfuerzo si el rendimiento de su aplicación se basa en él.

Por supuesto, existen métodos agradables (aunque no triviales) para trabajar con Unicode en C/C++. This article por Evan Jones puede ayudarlo a decidir si vale la pena el esfuerzo.

Answer 3

simplemente para la corrección, lo que terminó haciendo es simplemente escribir (algunos de) el código de manipulación de cadenas en C.

Como resultado, es ridiculously easy para empezar a escribir extensiones C a pitón. Las cadenas Unicode son solo arreglos de Py_UNICODE, que es un int o un short dependiendo de la construcción de python.

me dieron una mejora x20 conversión de código como

s = re.sub(r' +', ' ', s) 

ac. Obtuve mejoras similares con expresiones regulares más complicadas, pero el código c se vuelve loco complejo muy rápidamente.

En general, mi rendimiento aumentó un 20% después de la reescritura. Ahora estoy buscando más cosas para reescribir ...

Answer 4

"Ridiculously easy" es un término muy relativo. "Comenzar" es solo eso. Escribir extensiones robustas en C requiere una atención muy cuidadosa a cosas como el recuento de referencias, asignación/liberación de memoria y manejo de errores. Cython hace mucho de eso por ti.

Una cadena no unicode en Cython es un objeto Python str, o es una matriz de caracteres, como en C. ¿Qué documentación específica de Cython crees que necesitas?

Te recomiendo que pruebes Cython por ti mismo. PERO antes de hacer eso, le recomiendo que examine su código Python en busca de ineficiencias. A veces puedes obtener grandes aceleraciones ridículamente fácilmente.

Por ejemplo, la compresión de carreras de caracteres de espacio ... usando

re.sub(' +', ' ', s) # one space in pattern 

significa que en el caso de suponer que no infrecuente en una carrera tiene una longitud de 1, será la sustitución de un espacio con un espacio. Si todas las ejecuciones tienen una longitud 1, creará una nueva cadena de reemplazo cuando podría simplemente incrementar (o no decrecer, o lo que sea) el conteo de referencia de la cadena de entrada y pasarla de nuevo.

re.sub(' +', ' ', s) # two spaces in pattern 

produce exactamente los mismos resultados y puede correr más rápido ... vamos a ver:

Todo corre longitud 1: Se ejecuta en 3,4 veces la velocidad. No se muestra: cuanto más larga es la cadena de entrada, mejor se pone.

\python26\python -mtimeit -s"s='now is the winter of our discontent'; import re; x = re.compile(' +').sub" "x(' ', s)" 
100000 loops, best of 3: 8.26 usec per loop 

\python26\python -mtimeit -s"s='now is the winter of our discontent'; import re; x = re.compile(' +').sub" "x(' ', s)" 
100000 loops, best of 3: 2.41 usec per loop 

Con una carrera que tiene longitud 2, la relación de velocidad es 2.5. Con todas las ejecuciones tienen longitud 2, la relación de velocidad es 1.2. Considerado todo, no es un mal rendimiento en una inversión de 1 golpe de teclado.

Answer 5

Tenga en cuenta que Cython en realidad tiene soporte para el tipo Py_UNICODE de CPython, por lo que, por ejemplo, puede iterar directamente sobre cadenas Unicode o comparar caracteres a velocidad C. Veo

http://docs.cython.org/src/tutorial/strings.html

Answer 6

Me han introducido recientemente a Cython y han tenido gran éxito envolver grandes bibliotecas de C y C++ para su uso en proyectos importantes. Algunas de las extensiones de Python generadas ya se están ejecutando en nuestro entorno de producción. Entonces, primero, Cython es, definitivamente, definitivamente una buena opción.

Dicho esto, debe considerar si realmente desea escribir todo su código en Cython o si desea escribir el código C/C++ y simplemente hacer que esas funciones sean accesibles desde Cython. Obviamente, esto dependerá en parte de su nivel de comodidad con C y/o C++.

Como su trabajo con cadenas, probablemente podría hacer que su vida sea más simple usando std::string de C++ en comparación con char*. Se puede importar a cython muy fácilmente con from libcpp.string cimport string y luego las variables se pueden declarar con el tipo de cadena a través del cython estándar cdef string ...