2

我有一个纯粹用 Python 编写的 A* 规划算法(使用这个关于路径规划的优秀资源)。具有相关移动和成本方法的网格类定义如下:

class SquareGrid:
      def __init__(self, width, height):
          self.width = width
          self.height = height
          self.walls = []
          self.weights = []

      def in_bounds(self, id):
          (x, y) = id
          return 0 <= x < self.width and 0 <= y < self.height

      def passable(self, id):
          return id not in self.walls

      def neighbors(self, id):
          (x, y) = id
          results = [(x + 1, y), (x + 1, y - 1), (x, y - 1), (x - 1, y - 1), (x - 1, y), (x - 1, y + 1), (x, y + 1), (x + 1, y + 1)]
          if (x + y) % 2 == 0: results.reverse()  # aesthetics

          results = [r for r in results if self.in_bounds(r)]
          results = [r for r in results if self.passable(r)] # this is where things slow down
          return results

      def cost(self, from_node, to_node):
          return (to_node[0] - from_node[0])**2 + (to_node[1] - from_node[1])**2

现在,我想使用 Cython 的静态编译器优势来加快执行速度。一种选择是用 Cython 中的静态类型重写整个事情。我使用 cProfiler 分析了纯 Python 代码以查看瓶颈所在,不出所料,大约 70% 的总执行时间进入了该neighbors方法(计算当前节点周围的有效相邻节点)。更具体地说,对于给定的玩具示例,列表理解行neighbors调用passable了超过 33,000 次。passable通过搜索SquareGrid障碍物的知识来检查其参数中给出的节点是否被标记为“障碍物”(SquareGrid.walls,位置元组列表)并相应地返回一个布尔值。在我看来,只要优化这个特定的方法,我就会在速度上获得显着的提升。所以我开始passable用 Cython 重写。

总的来说,我是 Cython 和 C/C++ 的完全新手,所以如果在理解这件事的实际工作原理方面有任何错误被指出,我将不胜感激。我创建了一个 pyrex 文件passable_cy.pyx,希望使用 Cython/GCC++ 对其进行编译,然后将其绑定到SquareGrid主脚本中的对象就足够了。这就是我定义的方式passable_cy.pyx

cpdef bint passable(object self, tuple id):
    return id not in self.walls

随附setup.py文件:

from distutils.core import setup
from Cython.Build import cythonize

setup(name="cynthonized_passable", ext_modules=cythonize(['passable_cy.pyx']),)

这就是我将新的 cynthonized 方法绑定到SquareGrid主 A* python 脚本中的方式:

 g = SquareGrid(100, 100) # create grid with dimensions 100x100
 g.passable = types.MethodType(passable_cy.passable, g)

一切都正确编译,整个事情执行没有问题。没有任何速度改进,这是我所预料的(似乎太简单了)。我该如何从这里开始?这种方法绑定是最好的方法吗?我确信在 中可以做更多的事情passable_cy.pyx,但是我对 C/C++ 太不熟悉了,不知道该怎么做。

4

0 回答 0