Pauli Virtanen <pav@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