[Numpy-discussion] speeding up operations on small vectors

[Christoph Groth]

Pauli Virtanen <pav at iki.fi> writes:

>> Thank you for your suggestion.  It doesn't help me however, because
>> the algorithm I'm _really_ trying to speed up cannot be vectorized
>> with numpy in the way you vectorized my toy example.
>> 
>> Any other ideas?
>
> Reformulate the problem so that it can be vectorized. Without knowing
> more about the actual algorithm you are trying to implement, it's not
> easy to give more detailed help.

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.

The actual problem I'm trying to solve is finding those points of a
n-dimensional lattice which belong to an implicitly given shape.

The input is a lattice (specified in the most simple case by n
n-dimensional vectors, i.e. a n-by-n matrix), a starting point on that
lattice, and a shape function which returns True if a point belongs to
the shape, and False if it does not.

The output is an iterable over the lattice points which belong to the
shape.

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.

Christoph