Loopless syntax for 2d in NumPy (or Numarray)

[Terry Reedy]

"2mc" <mcrider at bigfoot.com> wrote in message
news:500a4565.0310192044.dce705b at posting.google.com...
> "Terry Reedy" <tjreedy at udel.edu> wrote in message
news:<VfqdnZ2_Z8mclg6iRVn-vA at comcast.com>...
> > Just curious: is this a real problem, or one you made up to stump
> > NumPy?
>
> Yes, this is a real problem.  Of course, it involves much more than
> this.  But, yes, I would like to get a running list of highest
values
> within a range of values.

> > I think the way to avoid redoing the max from scratch with each
move
> > of the window is to use a heap augmented by a circular index that
> > enables easy replacement of the departing number with the incoming
> > number.  After the replacement, re-establish the heap property and
> > record the max.  (For more on heaps, see heapq.py in the lib or
> > various algorithm books.)
>
> I didn't know there was a function called heapq.py.

It is a module added to the standard library perhaps in 2.2.  Not
surprised if not in books.

> Your suggestion to use heapq was interesting.  Basically, in my
> current program I use something similar.  I sort, enter new data
into
> oldest data's spot, resort, find the max, and repeat.

Same idea.  I think best resort method should be binary search for
insertion spot followed by shift-1 movement of off-by-1 block toward
empty spot and then insertion of new item in proper place.

The same operation for heaps would be O(logN) instead of O(N), but
with a higher constant, so it might or might not be faster for N=19.
(But I suspect it would be.)

> I have a couple of questions about heapq.  The website says that it
is
> an array but that it works on lists.  So, heapq would not work on
> NumPy arrays, right?  And, it is then a normal Python array rather
> than a NumPy array, right?

The algorithms, with adjustment, can use any type of random access
array, but there would not be any obvious benefit of shifting.  heapq,
as implied by the q for queue, is intended for heap use as priority
queue.  It has a replace_max function but not a
replace-arbitrary-element operation.  Regardless of what array type
you use, you would have to write your own replace function.  But it
should be a straight forward adjustment of the current replace
function -- once you understand heaps.

> Is there a comparable speed increase using
> heapq over explicit Python loops as there is in NumPy over explicit
> Python loops?

No, heapq is written in Python and uses normal looping.  But do keep
in mind that pure Python code, especially when using ints, floats, and
loops, can ofter run several times faster when psyco-ized.

> Thanks for your response.  I appreciate it.

Welcome,

Terry J. Reedy