如何为Python实现的A*算法中SquareGrid类的passable方法做Cython优化

Great question! Let's dig into why your current Cython approach isn't giving speedups, and walk through practical fixes—starting with a dead-simple pure Python tweak that'll likely give you most of the speed you need, then moving to proper Cython optimizations.

First: The Real Bottleneck Isn't passable—It's Your walls Data Structure #

Your passable method checks id not in self.walls, where self.walls is a list. Checking membership in a list is O(n) (it has to scan every element until it finds a match), and with 33,000+ calls, that's the real slowdown. Cython can't fix this because it's still calling Python's list __contains__ under the hood.

The easiest fix (no Cython needed!) is to switch self.walls to a set:

class SquareGrid:
    def __init__(self, width, height):
        self.width = width
        self.height = height
        self.walls = set()  # Change list to set
        self.weights = []
    # ... rest of your methods stay the same ...

Set membership checks are O(1), so this alone will drastically reduce the time spent in passable—you'll probably see the 70% runtime drop to something negligible.

Why Your Cython Binding Isn't Helping #

When you bind the Cython passable function to your Python SquareGrid instance with types.MethodType, you're still paying Python's method call overhead, and the core operation (id not in self.walls) is still using Python's list __contains__ method. Cython isn't able to optimize that because it's interacting with a pure Python list.

Proper Cython Optimization (If You Still Want It) #

If you want to go further with Cython, you need to move more of the logic to the C level, especially the wall-checking. Here's how to rewrite your SquareGrid in Cython to eliminate Python overhead:

1. Create a CySquareGrid.pyx file:

cdef class CySquareGrid:
    cdef int width, height
    cdef bint[:,:] _is_wall  # 2D memory view for fast wall checks

    def __init__(self, int width, int height):
        self.width = width
        self.height = height
        # Initialize a 2D array of False (not walls)
        self._is_wall = [[False for _ in range(height)] for _ in range(width)]

    cdef bint _in_bounds(self, int x, int y):
        return 0 <= x < self.width and 0 <= y < self.height

    cdef bint _passable(self, int x, int y):
        # Direct C-level access to the wall array—no Python overhead!
        return not self._is_wall[x][y]

    def add_wall(self, tuple id):
        cdef int x = id[0], y = id[1]
        if self._in_bounds(x, y):
            self._is_wall[x][y] = True

    def neighbors(self, tuple id):
        cdef int x = id[0], y = id[1]
        cdef list 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()
        
        # Filter neighbors in C-level loops to avoid Python list comp overhead
        cdef list filtered = []
        cdef int nx, ny
        for (nx, ny) in results:
            if self._in_bounds(nx, ny) and self._passable(nx, ny):
                filtered.append((nx, ny))
        return filtered

    def cost(self, tuple from_node, tuple to_node):
        cdef int fx = from_node[0], fy = from_node[1]
        cdef int tx = to_node[0], ty = to_node[1]
        return (tx - fx)**2 + (ty - fy)**2

2. Update your setup.py to compile this class:

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

setup(
    name="cythonized_grid",
    ext_modules=cythonize(['CySquareGrid.pyx']),
)

3. Use it in your main script like a normal Python class:

from CySquareGrid import CySquareGrid

g = CySquareGrid(100, 100)
g.add_wall((5,5))  # Add walls using the new method

Key improvements here:

• We use a 2D memory view (bint[:,:]) for walls, so checking if a node is passable is a direct C-level index lookup (no Python list/set operations).
• The _in_bounds and _passable methods are cdef functions, which means they're compiled to pure C and avoid Python's method call overhead.
• The neighbor filtering is done in a C-level loop, which is faster than Python list comprehensions.

Final Notes on Method Binding #

Binding a Cython function to a Python instance (like you did with types.MethodType) is rarely optimal because it doesn't eliminate Python's method dispatch overhead. If you're going to use Cython, it's better to implement the entire class (or at least the performance-critical parts) in Cython to get the full benefit.

Start with switching walls to a set—you'll be shocked at how much faster your code gets without any Cython. If you still need more speed after that, move to the full Cython class implementation.

内容的提问来源于stack exchange，提问作者wheatley