On Sun, Jun 1, 2008 at 1:37 AM, Anne Archibald <[EMAIL PROTECTED]> wrote:
> 2008/5/31 Pauli Virtanen <[EMAIL PROTECTED]>: > > > The reason for the strange behavior of slice assignment is that when the > > left and right sides in a slice assignment are overlapping views of the > > same array, the result is currently effectively undefined. Same is true > > for ndarrays: > > > >>>> import numpy > >>>> a = numpy.array([1, 2, 3, 4, 5]) > >>>> a[::-1] > > array([5, 4, 3, 2, 1]) > >>>> a[:] = a[::-1] > >>>> a > > array([5, 4, 3, 4, 5]) > > I think that the current rule is, slices are walked from low index to > high index. This doesn't help with multidimensional arrays, where the > order of the axes is (and should be) determined by efficiency > considerations. > > Unfortunately there's really no good way to warn about overlapping > copies. Remember that this is a frequent operation, so it has to be > fast for small arrays. > > I think changing base so that it points to the real base and not the > parent would help (and clear up a memory leak: try "while True: A = > A[::-1]" some time) eliminate some cases where overlap cannot occur, > but what about the following cases? > > A[:5] = A[-5:] > A[::2] = A[1::2] > A[1:] = A[-1:] > > The last is actually fairly common (I've needed it), and relies on > numpy's ordering of copies. The middle one is very common, and the > first one would be a royal pain to code around if the slices were not > allowed to overlap. > > I think I at one point wrote an algorithm that would detect many cases > where overlap could not occur (maybe in the smarter reshape code?) but > I came to the conclusion that detecting all the cases was infeasible. > It's a number-theoretic problem - "can you write the same number as > the sum of multiples of these two lists of numbers with nonnegative > integer coefficients less than these other two lists of numbers?" - > and I suspect it's NP-complete. (Ah, yes, you can make a knapsack out > of it - take an array with strides a_1, ... a_n and shape (2,...,2), > and a single-element array starting at position N.) In any case it's > infeasible to solve it every time somebody tries to do a slice > assignment. > Since one could compute all the addresses and check for duplicates, I would guess it is O(n), maybe O(n*log(n)) worst case, but I can't convince myself that it would help much to know about overlaps. As you point out, a lot of times one needs overlapping ranges, it is when the user has designed an algorithm without taking the possibility into account that problems arise. Chuck
_______________________________________________ Numpy-discussion mailing list Numpy-discussion@scipy.org http://projects.scipy.org/mailman/listinfo/numpy-discussion
