¿Manera idiomática de hacer lista / dictado en Cython?

Mi problema: encontré que el procesamiento de grandes conjuntos de datos con C ++ sin procesar utilizando el mapa STL y el vector a menudo puede ser considerablemente más rápido (y con menor espacio de memoria) que usar Cython.

Me imagino que parte de esta penalización de velocidad se debe al uso de listas y dictados de Python, y que podría haber algunos trucos para usar estructuras de datos menos gravadas en Cython. Por ejemplo, esta página ( http://wiki.cython.org/tutorials/numpy ) muestra cómo hacer matrices numpy muy rápidamente en Cython al predefinir el tamaño y los tipos de la matriz ND.

Pregunta: ¿Hay alguna forma de hacer algo similar con listas / dictados, por ejemplo, indicando aproximadamente cuántos elementos o pares (clave, valor) espera tener en ellos? Es decir, ¿existe una forma idiomática de convertir listas / dictados en estructuras de datos (rápidas) en Cython?

Si no, supongo que tendré que escribirlo en C ++ y envolverlo en una importación de Cython.

Cython ahora tiene soporte para plantillas, y viene con declaraciones para algunos de los contenedores STL.

Consulte http://docs.cython.org/src/userguide/wrapping_CPlusPlus.html#standard-library

Aquí está el ejemplo que dan:

from libcpp.vector cimport vector cdef vector[int] vect cdef int i for i in range(10): vect.push_back(i) for i in range(10): print vect[i] 

Hacer operaciones similares en Python como en C ++ a menudo puede ser más lento. list y el dict se implementan realmente muy bien, pero usted obtiene una gran cantidad de sobrecarga al usar objetos de Python, que son más abstractos que los objetos de C ++ y requieren más búsquedas en el tiempo de ejecución.

Por cierto, std::vector se implementa de una manera bastante similar a la list . std::map , sin embargo, se implementa de manera tal que muchas operaciones son más lentas que las dict medida que aumenta su tamaño. Para ejemplos adecuadamente grandes de cada uno, dict supera el factor constante por el cual es más lento que std::map y en realidad realizará operaciones como búsqueda, inserción, etc. más rápido.

Si quieres usar std::map y std::vector , nada te detiene. Tendrá que envolverlos usted mismo si desea exponerlos a Python. No se sorprenda si esta envoltura consume todo o la mayor parte del tiempo que esperaba ahorrar. No tengo conocimiento de ninguna herramienta que haga esto automáticamente para usted.

Hay llamadas a la API de C para controlar la creación de objetos con algún detalle. Puede decir “Hacer una lista con al menos esta cantidad de elementos”, pero esto no mejora la complejidad general de la operación de creación y llenado de su lista. Ciertamente no cambia mucho más tarde cuando intentas cambiar tu lista.

Mi consejo general es

  • Si quieres una matriz de tamaño fijo (hablas de especificar el tamaño de una lista), es posible que desees algo como una matriz numpy.

  • Dudo que vaya a obtener la aceleración que desee al usar std::vector over list para un reemplazo general en su código. Si desea usarlo detrás de escena, puede brindarle una mejora satisfactoria de tamaño y espacio (por supuesto, no sé sin medir, ni usted.;)).

  • dict realmente hace su trabajo realmente bien. Definitivamente no intentaría introducir un nuevo tipo de uso general para Python basado en std::map , que tiene una complejidad algorítmica peor en el tiempo para muchas operaciones importantes y, al menos en algunas implementaciones, deja algunas optimizaciones al usuario que dict ya tiene.

    Si quisiera algo que funcionara un poco más como std::map , probablemente usaría una base de datos. En general, esto es lo que hago si las cosas que quiero almacenar en un dict (o para el caso, las cosas que almaceno en una list ) son demasiado grandes para que me sienta cómodo almacenando en la memoria. Python tiene sqlite3 en stdlib y controladores para todas las demás bases de datos principales disponibles.

C ++ es rápido, no solo por las declaraciones estáticas del vector y los elementos que lo integran, sino también porque, al usar plantillas / generics, se especifica que el vector solo contendrá elementos de cierto tipo, por ejemplo, vector con tuplas de tres elementos. Cython no puede hacer esto último y suena poco trivial: tendría que ser implementado en el momento de la comstackción, de alguna manera (la comprobación de tipos en el tiempo de ejecución es lo que Python ya hace). Así que ahora mismo, cuando saca algo de una lista en Cython, no hay manera de saber de antemano qué tipo es, y ponerlo en una variable escrita solo agrega una comprobación de tipo, no velocidad. Esto significa que no hay manera de pasar por alto al intérprete de Python en este aspecto, y me parece que es la deficiencia más importante de Cython para las tareas no numéricas.

La forma manual de resolver esto es subclasificar la lista / dict de python (o quizás std :: vector) con una clase cdef para un tipo específico de elemento o combinación de clave-valor. Esto equivaldría a lo mismo que el código que generan las plantillas. Siempre que use la clase resultante en el código de Cython, debería proporcionar una mejora.

El uso de bases de datos o matrices solo resuelve un problema diferente, porque se trata de poner objetos arbitrarios (pero con un tipo específico, y preferiblemente una clase cdef) en contenedores.

Y std :: map no debe compararse con dict; std :: map mantiene las claves en orden ordenado porque es un árbol equilibrado, dict resuelve un problema diferente. Una mejor comparación sería dict y la tabla hash de Google.

Puede ver el módulo de array estándar para Python si esto es apropiado para su configuración de Cython. No estoy seguro ya que nunca he usado Cython.

No hay forma de obtener listas / dictados de Python nativos hasta la velocidad de un mapa / vector C ++ o incluso en cualquier lugar cercano. No tiene nada que ver con la asignación o la statement de tipo, sino que paga los gastos generales del intérprete. El ejemplo que mencionas (numpy) es una extensión de C y está escrito en C precisamente por este motivo.