[Numpy-discussion] speeding up operations on small vectors

[Pauli Virtanen]

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