с использованием cython или PyPy для оптимизации кортежей/списков (алгоритм теории графов, реализованный в python)

Question

Я работаю над теоретической теоретической проблемой теории, которая включает в себя объединение комбинаций гиперэдров в гиперграфе для анализа различных случаев.

Я реализовал первоначальную версию основного алгоритма в Python, но из-за его комбинаторной структуры (и, вероятно, моей реализации) алгоритм довольно медленный.

Один из способов, с помощью которого я рассматриваю возможность его ускорения - использовать PyPy или Cython.

Глядя на документацию, похоже, Cython не предлагает отличного ускорения, когда дело доходит до кортежей. Это может быть проблематично для реализации, поскольку я представляю гиперссылки как кортежи - поэтому большинство алгоритмов манипулирует кортежами (однако они имеют одинаковую длину, вокруг len 6 каждый).

Поскольку мои умения на C и Python довольно минимальны, я был бы признателен, если бы кто-нибудь мог посоветовать, что было бы лучшим способом для оптимизации кода, учитывая его зависимость от кортежей/списков. Есть ли документация с использованием списков/кортежей с Cython (или PyPy)?

Answer 1

, что было бы лучшим способом, чтобы продолжить в оптимизации кода ...

Profile first. Существует стандартный модуль cProfile, который очень просто профилирует. Оптимизация кода перед профилированием совершенно бессмысленна.

Кроме того, для графиков вы можете попробовать использовать отличный модуль networkx. Кроме того, если вы имеете дело с длинными отсортированными списками, вы можете взглянуть на модули bisect и heapq.

Answer 2

Если ваш алгоритм плох с точки зрения вычислительной сложности, то вы не можете быть сохранены, вам нужно написать его лучше. Проконсультируйтесь с хорошей книгой теории графов или с википедией, это обычно относительно легко, хотя есть некоторые, которые имеют как нетривиальные, так и безумные алгоритмы. Это похоже на то, что PyPy может значительно ускориться, но только с постоянным фактором, однако он не влечет за собой каких-либо изменений в вашем коде. Cython не ускоряет ваш код настолько, что без деклараций типов, и похоже, что подобная проблема не может быть действительно ускорена только по типам.

Постоянная часть - вот что важно здесь - если сложность алгоритма вырастает, скажем, 2^n (что типично для наивного алгоритма), то добавление дополнительного узла в граф удваивает ваше время. Это означает, что 10 узлов добавляют 1024 времени, 20 узлов 1024 * 1024 и т. Д. Если вам повезло, PyPy может ускорить ваш алгоритм на 100x, но это остается постоянным по размеру графика (и вы быстро исчерпаете вселенную время так или иначе).