en utilisant cython ou PyPy pour optimiser les tuples/listes (algorithme de la théorie des graphes implémenté en python)

Question

Je travaille sur un problème de théorie des graphes théorique qui consiste à prendre des combinaisons d'hypercharges dans un hypergrapha pour analyser les différents cas.

J'ai implémenté une version initiale de l'algorithme principal en Python, mais en raison de sa structure combinatoire (et probablement de ma mise en œuvre), l'algorithme est assez lent.

L'un des moyens que j'utilise est d'accélérer PyPy ou Cython.

En regardant la documentation, il semble que Cython n'offre pas une grande rapidité en ce qui concerne les tuples. Cela peut être problématique pour l'implémentation, puisque je représente les hypercharges comme des tuples - donc la majorité de l'algorithme est dans la manipulation des tuples (cependant ils sont tous de la même longueur, environ len 6 chacun). Comme mes compétences C et Python sont assez minimes, j'apprécierais que quelqu'un puisse vous conseiller sur la meilleure façon de procéder pour optimiser le code étant donné sa dépendance aux tuples/listes. Existe-t-il une documentation sur l'utilisation de listes/tuples avec Cython (ou PyPy)?

Answer 1

quelle serait la meilleure façon de procéder à l'optimisation du code ...

Profile first. Il y a un module standard cProfile qui fait très bien le profilage simple. L'optimisation de votre code avant le profilage est inutile. En outre, pour les graphiques, vous pouvez essayer d'utiliser l'excellent module networkx. En outre, si vous traitez avec de longues listes triées, vous pouvez jeter un oeil aux modules bisect et heapq.

Answer 2

Si votre algorithme est mauvais en termes de complexité de calcul, alors vous ne pouvez pas être sauvé, vous devez l'écrire mieux. Consulter un bon livre de théorie des graphes ou wikipedia, c'est généralement relativement facile, bien qu'il y en ait qui ont des algorithmes à la fois non triviaux et fous. Cela ressemble à une chose que PyPy peut accélérer de manière significative, mais seulement par un facteur constant, mais cela n'implique aucune modification de votre code. Cython n'accélère pas tellement votre code sans les déclarations de type et il semble que ce genre de problème ne peut pas être vraiment accéléré par les types. La partie constante est ce qui est crucial ici - si la complexité de l'algorithme s'est développée comme, disons, 2^n (ce qui est typique pour un algorithme naïf), alors ajouter un nœud supplémentaire au graphique double votre temps. Cela signifie que 10 nœuds ajoutent 1024 fois le temps, 20 nœuds 1024 * 1024 etc. Si vous êtes super chanceux, PyPy peut accélérer votre algorithme de 100x, mais cela reste constant sur la taille du graphique (et vous vous retrouvez rapidement hors de l'univers temps d'une manière ou d'une autre). Pouvez-vous envoyer votre code et mettre en évidence les parties qui sont lentes?