11.10.2011 17:57, Christoph Groth kirjoitti: [clip]
My question was about ways to achieve a speedup without modifying the algorithm. I was hoping that there is some numpy-like library for python which for small arrays achieves a performance at least on par with the implementation using tuples. This should be possible technically.
I'm not aware of such a library. Writing one e.g. with Cython should be quite straightforward, however. [clip]
To generate the output, the algorithm (flood-fill) recursively examines the starting point and its neighbors, calling for each of them the shape function. There are various variants of this algorithm, but all of them rely on the same basic operations.
To my knowledge, it is not possible to vectorize this algorithm using numpy. One can vectorize it if a bounding box for the shape is known in advance, but this is not very efficient as all the lattice points inside the bounding box are checked.
The only way to vectorize this I see is to do write the floodfill algorithm on rectangular supercells, so that the constant costs are amortized. Sounds a bit messy to do, though. -- Pauli Virtanen