[Numpy-discussion] In-place fancy selection

[Anne Archibald]

On 01/03/07, Francesc Altet <faltet at carabos.com> wrote:
> Hi,
>
> I don't think there is a solution for this, but perhaps anybody may
> offer some idea. Given:
>
> In [79]:a=numpy.arange(9,-1,-1)
> In [80]:b=numpy.arange(10)
> In [81]:numpy.random.shuffle(b)
> In [82]:b
> Out[82]:array([2, 6, 3, 5, 4, 9, 0, 8, 7, 1])
> In [83]:a=a[b]
> In [84]:a
> Out[84]:array([7, 3, 6, 4, 5, 0, 9, 1, 2, 8])
>
> is there a way to make the step 83 without having to keep 3 arrays
> in-memory at the same time? This is, some way of doing fancy indexing,
> but changing the elements *inplace*. The idea is to keep memory
> requeriments as low as possible when a and b are large arrays.
>
> Thanks!

In general, this is impossible:
a=arange(3)
b=a[[0,1,0,1,0]]

b is bigger than a, so you can't hope to do this in place.

>From the example you gave, though, it's likely that what you want is
to apply a permutation (this turns up frequently with argsorts).
That's possible in principle, though even in C I think you need to
either maintain an array of auxiliary data or destroy the indexing
array. The problem is that every element you move, you need to clear
space for it. You can chase this around one cycle in the permutation
with no difficulty, but as you move from cycle to cycle you need to
keep track of which elements of the array have already been shuffled
and which haven't. You can do this with bitfields, or you can adjust
the indexing array as you go. Since either of these effectively
require O(n) extra storage, they don't have much appeal - except that
you might want to permute just one axis of an array, in which case the
extra storage. could be much smaller than the array itself. I've
attached an implementation of this (in Python, but it might be useful
anyway since the row copies are done by numpy).

Anne
-------------- next part --------------
A non-text attachment was scrubbed...
Name: permute.py
Type: text/x-python
Size: 759 bytes
Desc: not available
URL: <http://mail.python.org/pipermail/numpy-discussion/attachments/20070301/f803eea8/attachment.py>