[Matrix-SIG] "Sorting" a large array?!

[Rob Hooft]

In my application I have a series (upto hundreds) of 2D arrays
(625x576).  I am interested in one-but-the-lowest or
two-but-the-lowest element at each location of the 2D arrays.

Currently I have programmed this like:

class NthLowestSink(imagesink.AccumulatingSink):
    n=3 # Which element are we interested in. n=1 calculates the "minimum"
    mem=3

    def Frame(self,data):
      data=data.astype('f')
      if not hasattr(self,'arrdata'):
	self.arrdata=data[Numeric.NewAxis,:,:]
      else:
	self.arrdata=Numeric.concatenate((self.arrdata,data[Numeric.NewAxis,:,:]))
	if len(self.arrdata)>=self.mem:
	  self.arrdata=Numeric.sort(self.arrdata,axis=0)[0:self.n]

    def FinalEnd(self):
      self.arrdata=Numeric.sort(self.arrdata,axis=0)[0:self.n]
      self.data=self.arrdata[self.n-1,:,:]

To simplify: for n=1, this just does a Numeric.minimum.reduce along the
frames.

Obviously I do not have enough memory to do everything at
once.  Instead, each time a new frame is added, the array is sorted on
the frame-axis (axis=0) and the lowest element is kept. 

If n>1, more than one element needs to be kept.

To save a bit of time, the "mem" variable is added. If mem is raised,
this reduces the number of sort operations, speeding up the process at
the expense of memory usage.

I have 2 questions:

 1) Am I missing something obvious that might speed this up? It is quite slow
    like this....

 2) The "concatenate" operation currently duplicates memory completely.
    Slow and expensive. Is there a better way?

Thanks for any hints.

Rob

-- 
=====   R.Hooft@EuroMail.net   http://www.xs4all.nl/~hooft/rob/  =====
=====   R&D, Nonius BV, Delft  http://www.nonius.nl/             =====
===== PGPid 0xFA19277D ========================== Use Linux! =========