[Numpy-discussion] Checking for views (was: Should arr.diagonal() return a copy or aview?)
Nathaniel Smith
njs at pobox.com
Fri May 25 12:59:39 EDT 2012
On Fri, May 25, 2012 at 4:59 PM, Robert Kern <robert.kern at gmail.com> wrote:
> On Fri, May 25, 2012 at 3:55 PM, Nathaniel Smith <njs at pobox.com> wrote:
>> On May 25, 2012 2:21 PM, "Robert Kern" <robert.kern at gmail.com> wrote:
>>>
>>> On Thu, May 24, 2012 at 5:52 PM, Robert Kern <robert.kern at gmail.com> wrote:
>>>
>>> > (Hmm, now that I think about it, the edge cases are when the strides
>>> > are 0 or negative. 0-stride axes can simply be removed, and I think we
>>> > should be able to work back to a first item and flip the sign on the
>>> > negative strides. The typical positive-stride solution can be found in
>>> > an open source C++ global array code, IIRC. Double-hmmm...)
>>>
>>> Except that it's still NP-complete.
>>
>> Huh, is it really? I'm pretty sure checking the existence of a
>> solution to a linear Diophantine equation is cheap, but I guess
>> figuring out whether it falls within the "shape" bounds is less
>> obvious...
>
> If both positive and negative values are allowed, then there is a
> polynomial-time algorithm to solve the linear Diophantine equation,
> but bounding the possible values renders it NP-complete. When you go
> down to {0,1} as the only allowable values, it becomes the SUBSET-SUM
> problem.
Right.
I suspect it's still pretty practical to solve for many of the arrays
we care about (strides that are multiples of each other, etc.); many
NP-hard problems are easy in the typical case, and for a lot of the
cases we care about (e.g. disjoint slices of a contiguous array)
solving the Diophantine equation will show that the bounds are
irrelevant and collisions can never occur.
Oh well, fortunately nothing depends on this :-).
- N
More information about the NumPy-Discussion
mailing list