[Numpy-discussion] speeding up operations on small vectors
Pauli Virtanen
pav@iki...
Tue Oct 11 11:20:39 CDT 2011
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
More information about the NumPy-Discussion
mailing list