Idiomatiques façon de faire de la liste/dict en Cython?

Question

Mon problème: j'ai trouvé que le traitement de grands ensembles de données brutes C++ à l'aide de la STL carte de vecteur et peuvent souvent être beaucoup plus rapide (et avec la plus faible empreinte mémoire) que l'utilisation de Cython.

Je me figure qu'une partie de cette vitesse de pénalité est due à l'utilisation de Python, les listes et les dicts, et qu'il pourrait y avoir quelques trucs pour utiliser moins encombrée des structures de données en Cython. Par exemple, cette page (http://wiki.cython.org/tutorials/numpy) montre comment faire des tableaux numpy très rapide en Cython par prédéfinir la taille et le type du ND tableau.

Question: Est-il possible de faire quelque chose de similaire avec les listes/dicts, par exemple en disant à peu près combien d'éléments ou (clé,valeur) des paires vous vous attendez à avoir en eux? Ce qui est, est-il un idiomatiques moyen de convertir des listes/dicts à (rapide) des structures de données en Cython?

Si non je pense que je vais avoir à l'écrire en C++ et enveloppez-les dans un Cython d'importation.

Answer 1

Cython a maintenant prise en charge de modèle, et est livré avec les déclarations de certains des conteneurs STL.

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

Voici l'exemple qu'ils donnent:

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

Faire les mêmes opérations en Python qu'en C++ peut souvent être plus lent. list et dict sont effectivement mis en œuvre très bien, mais vous gagner un grand nombre de généraux de l'aide des objets Python, qui sont plus abstraites que des objets en C++ et nécessitent beaucoup plus de recherche au moment de l'exécution.

Incidemment, std::vector est mis en œuvre dans une jolie manière similaire à l' list. std::map, cependant, est en fait mis en œuvre de manière que de nombreuses opérations sont plus lents que d' dict que sa taille est grande. Pour convenablement les grands exemples de chaque, dict surmonte le facteur constant par lequel il est plus lent que l' std::map et sera effectivement faire des opérations comme la recherche, d'insertion, etc. plus rapide.

Si vous souhaitez utiliser std::map et std::vector, rien ne vous en empêche. Vous aurez à emballer vous-même si vous souhaitez exposer à Python. Ne soyez pas choqué si ce habillage consomme la totalité ou la plupart du temps vous avez été dans l'espoir de sauver. Je ne suis pas au courant de tous les outils qui font cela automatiquement pour vous.

Il y a des appels de l'API C pour le contrôle de la création d'objets avec quelque détail. Vous pouvez dire "Faire une liste avec au moins le nombre d'éléments", mais ce n'est pas d'améliorer la complexité globale de votre liste de la création-et-opération de remplissage. Il n'est certainement pas à changer beaucoup plus tard que vous essayez de modifier votre liste.

Mon conseil général est

• Si vous voulez un tableau de taille fixe (vous parlez de la spécification de la taille d'une liste), vous pourriez voulez quelque chose comme un tableau numpy.

• Je doute que vous allez obtenir toute speedup vous voulez de l'aide d' std::vector sur list pour un général de rechange dans votre code. Si vous voulez l'utiliser en coulisse, il peut vous donner une satisfaction espace et de la taille de l'amélioration (bien sûr, je ne sais pas, sans mesure, ni de vous. ;) ).

• dict ne fait son travail très bien. Je certainement ne pas essayer d'introduire un nouvel usage général de type pour une utilisation en Python basé sur std::map, ce qui est pire complexité algorithmique en temps important pour de nombreuses opérations et-au moins dans certaines implémentations de feuilles de certaines optimisations pour l'utilisateur qu' dict a déjà.

  Si je ne veux quelque chose qui a travaillé un peu à la manière d' std::map, je serais probablement utiliser une base de données. C'est généralement ce que je fais si des choses je veux stocker dans un dict (ou, d'ailleurs, des choses que j'magasin en list) devient trop grande pour que je me sente à l'aise, à stocker dans la mémoire. Python a sqlite3 dans la stdlib et des pilotes pour tous les autres principales bases de données disponibles.

Answer 3

C++ est rapide, pas seulement à cause de la statique des déclarations du vecteur et les éléments qui entrent en elle, mais, aussi et surtout, parce que l'utilisation de modèles/les génériques on précise que le vecteur sera uniquement contenir des éléments d'un certain type, par exemple un vecteur de n-uplets de trois éléments. Cython ne pouvez pas faire cette dernière chose et il semble triviale -- il devait être exécutée au moment de la compilation, en quelque sorte (vérification de type à l'exécution, est ce que Python est déjà fait). Donc maintenant, quand vous la pop quelque chose sur une liste en Cython il n'y a aucun moyen de savoir à l'avance quel type il est , et de le mettre dans un typée variable ajoute une typecheck, pas de vitesse. Cela signifie qu'il n'existe aucun moyen de contourner l'interpréteur Python à cet égard, et il me semble que c'est la plus grave lacune de Cython pour les non-numérique tâches.

Le manuel de la façon de résoudre ce est une classe de la liste python/dict (ou peut-être std::vector) avec un cdef classe pour un type spécifique de l'élément ou valeur-clé de la combinaison. Cela reviendrait à la même chose que le code que les modèles sont génératrices. Tant que vous utilisez la classe résultante en Cython code, il devrait fournir une amélioration.

À l'aide de bases de données ou des tableaux résout un autre problème, parce que ce est à propos de mettre des objets arbitraires (mais avec un type spécifique, et de préférence un cdef classe) dans des conteneurs.

Et std::map ne devrait pas être comparé à d'dict; std::map maintient les touches dans l'ordre parce que c'est un arbre équilibré, dict résout un problème différent. Une meilleure comparaison serait dict et Google de table de hachage.

Answer 4

Vous pouvez prendre un coup d'oeil à la norme array module Python si c'est approprié pour votre Cython réglage. Je ne suis pas sûr car je n'ai jamais utilisé Cython.

Answer 5

Il n'y a aucun moyen d'obtenir natif Python listes/dicts jusqu'à la vitesse de C++ map/vecteur ou même n'importe où à proximité. Il n'a rien à voir avec l'allocation ou de la déclaration de type, mais plutôt de payer l'interprète de frais généraux. L'exemple que vous mentionnez (numpy) est une extension de do et est écrit en C, précisément pour cette raison.