c++ - ¿Forma idiomática de hacer una lista/dict en Cython?

cython install

Question

Mi problema: descubrí que el procesamiento de grandes conjuntos de datos con C ++ sin formato usando el mapa y el vector STL a menudo puede ser considerablemente más rápido (y con menor huella 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 crear matrices numpy muy rápido en Cython al predefinir el tamaño y los tipos de la matriz ND.

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

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

Answer 1

C ++ es rápido no solo por las declaraciones estáticas del vector y los elementos que entran en él, sino porque el uso de plantillas / genéricos 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 no trivial: tendría que aplicarse en tiempo de compilación, de alguna manera (la comprobación de tipo en el tiempo de ejecución es lo que Python ya hace). Así que ahora, cuando sacas algo de una lista en Cython, no hay manera de saber de antemano de qué tipo es, y colocarlo en una variable tipeada solo agrega una comprobación de tipo, no de velocidad. Esto significa que no hay forma de eludir el intérprete de Python en este aspecto, y me parece que es la falla más importante de Cython para tareas no numéricas.

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

Usar bases de datos o matrices simplemente 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 se debe comparar con dict; std :: map mantiene las claves ordenadas porque es un árbol equilibrado, dict resuelve un problema diferente. Una mejor comparación sería dict y hashtable de Google.

Answer 2

Cython ahora tiene soporte de plantilla 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]

Answer 3

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

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

Si desea usar std::map y std::vector , nada lo detiene. Tendrás que envolverlos tú mismo si quieres exponerlos a Python. No se sorprenda si este envoltorio consume la mayor parte del tiempo que esperaba salvar. No conozco ninguna herramienta que lo haga automático.

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

Mi consejo general es

• Si desea una matriz de tamaño fijo (usted habla sobre especificar el tamaño de una lista), es posible que realmente desee algo como una matriz numpy.

• Dudo que vayan a obtener la aceleración que quieran usando std::vector over list para un reemplazo general en su código. Si desea utilizarlo detrás de las escenas, puede darle una mejora satisfactoria de tamaño y espacio (por supuesto, no lo sé sin medir, ni usted tampoco;)).

• dict realidad hace su trabajo realmente bien. Definitivamente no trataría de introducir un nuevo tipo de uso general en 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 para el usuario que dict ya tiene.

  Si quisiera algo que funcionara un poco más como std::map , probablemente usaría una base de datos. Esto es generalmente lo que hago si las cosas que quiero almacenar en un dict (o para el caso, cosas que almaceno en una list ) se vuelven 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 importantes disponibles.

Answer 4

No hay forma de obtener listas / dictados nativos de Python 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 declaración de tipo, sino que paga la sobrecarga del intérprete. El ejemplo que mencionas (numpy) es una extensión C y está escrito en C precisamente por esta razón.

Answer 5

Puede echar un vistazo al 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.