Modo idiomatico per fare list/dict in Cython?

Question

Il mio problema:Ho scoperto che l'elaborazione di set di dati di grandi dimensioni con C++ grezzo utilizzando la mappa e il vettore STL può spesso essere notevolmente più veloce (e con un ingombro di memoria inferiore) rispetto all'utilizzo di Cython.

Immagino che parte di questa penalità di velocità sia dovuta all'uso di elenchi e dict Python e che potrebbero esserci alcuni trucchi per utilizzare strutture dati meno ingombranti in Cython.Ad esempio, questa pagina (http://wiki.cython.org/tutorials/numpy) mostra come rendere gli array Numpy molto veloci in Cython predefinendo la dimensione e i tipi dell'array ND.

Domanda:Esiste un modo per fare qualcosa di simile con elenchi/dict, ad es.indicando approssimativamente quanti elementi o coppie (chiave, valore) ti aspetti di contenere? Cioè, esiste un modo idiomatico per convertire elenchi/dict in strutture dati (veloci) in Cython?

In caso contrario, immagino che dovrò semplicemente scriverlo in C++ e inserirlo in un'importazione Cython.

Answer 1

Cython ha ora il supporto modello, e viene fornito con le dichiarazioni di alcuni dei contenitori STL.

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

Ecco l'esempio che danno:

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 2

Fare operazioni simili in Python come in C ++ spesso può essere più lento. list e dict siano effettivamente applicate molto bene, ma si guadagna un sacco di overhead utilizzando oggetti Python, che sono più astratti di oggetti C ++ e che richiedono molto di più di ricerca in fase di esecuzione.

Per inciso, std::vector è implementato in un modo molto simile a list. std::map, però, è effettivamente implementata in un modo che molte operazioni sono più lenti dict la sua dimensione diventa grande. Per sufficientemente grandi esempi di ognuno, dict supera il fattore costante che è più lento di std::map e sarà effettivamente fare operazioni come ricerca, inserimento, ecc veloce.

Se si desidera utilizzare std::map e std::vector, nulla si ferma voi. Dovrete avvolgere da soli se si desidera esporre loro di Python. Non essere sconvolto se questo involucro consuma tutto o gran parte del tempo che speravano di salvare. Io non sono a conoscenza di strumenti che rendono questo automaticamente per voi.

Ci sono chiamate API C per controllare la creazione di oggetti con qualche dettaglio. Si può dire "fare una lista con almeno questo molti elementi", ma questo non migliora la complessità generale del funzionamento lista di creazione-e-riempimento. Certamente non cambia molto più tardi, come si tenta di modificare la lista.

Il mio consiglio generale è

• Se si desidera una matrice a dimensione fissa (si parla di specificare il formato di un elenco), è possibile che in realtà vuole qualcosa di simile a una matrice NumPy.

• Dubito che si sta per ottenere qualsiasi aumento di velocità che si desidera di utilizzare std::vector sopra list per un Generale la sostituzione nel codice. Se si desidera utilizzarlo dietro le quinte, si può dare una dimensione e lo spazio soddisfacente miglioramento (I, naturalmente, non lo so senza misurare, né si;.).)

• dict in realtà fa il suo lavoro molto bene. Io sicuramente non avrebbe cercato l'introduzione di un nuovo tipo general-purpose per l'uso in Python sulla base di std::map, che ha peggio complessità algoritmica in tempo per molte operazioni importanti e in almeno alcune implementazioni-lascia alcuni ottimizzazioni per l'utente che ha già dict .

  Se volevo qualcosa che ha funzionato un po 'più simile std::map, probabilmente sarei utilizzare un database. Questo è in genere quello che faccio se roba voglio conservare in un dict (o per quella materia, roba devo conservare in un list) diventa troppo grande per me sentire la memorizzazione agio in memoria. Python ha sqlite3 nel stdlib ei driver per tutte le altre principali banche dati disponibili.

Answer 3

Il C++ è veloce non solo per le dichiarazioni statiche del vettore e degli elementi che vi entrano, ma soprattutto perché utilizzando modelli/generici si specifica che il vettore soltanto contenere elementi di un certo tipo, ad es.vettore con tuple di tre elementi.Cython non può fare quest'ultima cosa e sembra non banale: dovrebbe essere applicato in fase di compilazione, in qualche modo (il controllo del tipo in fase di runtime è ciò che Python già fa).Quindi in questo momento quando si estrae qualcosa da un elenco in Cython non c'è modo di sapere in anticipo di che tipo si tratta e inserirlo in una variabile tipizzata aggiunge solo un controllo del tipo, non una velocità.Ciò significa che non c'è modo di aggirare l'interprete Python a questo riguardo, e mi sembra che sia il difetto più cruciale di Cython per le attività non numeriche.

Il modo manuale per risolvere questo problema è creare una sottoclasse di python list/dict (o forse std::vettore) con una classe cdef per un tipo specifico di elemento o combinazione chiave-valore.Ciò equivarrebbe alla stessa cosa del codice generato dai modelli.Finché utilizzi la classe risultante nel codice Cython, dovrebbe fornire un miglioramento.

L'uso di database o array risolve semplicemente un problema diverso, perché si tratta di inserire oggetti arbitrari (ma con un tipo specifico e preferibilmente una classe cdef) in contenitori.

E std::map non dovrebbe essere paragonato a dict;std::map mantiene le chiavi in ​​ordine perché è un albero bilanciato, dict risolve un problema diverso.Un confronto migliore sarebbe dict e la tabella hash di Google.

Answer 4

È possibile dare un'occhiata alla array modulo standard per Python se questo è appropriata per l'impostazione Cython. Io non sono sicuro perché non ho mai usato Cython.

Answer 5

Non v'è alcun modo per ottenere liste Python native / dicts fino alla velocità di un C ++ mappa / vettore o addirittura nessuna parte vicino. Non ha nulla a che fare con assegnazione o dichiarazione del tipo, ma piuttosto di pagare l'overhead interprete. L'esempio si parla (NumPy) è un'estensione C ed è scritto in C proprio per questo motivo.