From: "Ara.T.Howard" <Ara.T.Howard@...>
Date: 2005-08-02T13:41:04+09:00
Subject: Re: algorithm help

On Tue, 2 Aug 2005, Szymon Rozga wrote:

> What exactly are you trying to do ?
> -s

i have a massive (100-500MB) grid of solar elevations and a coresponding data
set of binary format.

i need to find the areas in the solar elevations file that are less than a
certain amount and, based on those ranges, munge the data file in a certain
way to fix an issue with 'wobbling' sensor aboard the satelite imaging the
data.  basically we have lines that look like

   ------------ | ------------
     ------------ | ------------

where the '|'s are supposed to line up.  as it turns out this is only
happening in 'dark' areas of the data - therefore the solar elevations can be
used to predict where the problem will occur within a few pixels.  (the
problem is caused by a photo-multiplier tube switching on when darkness is
sensed - we think).

so - i currently am munging the data, which is a terrible record based format,
using writable mmap's of the file and this is very fast.  the issue is
constraining the munging to certain regions.  narray allows me to say this
sort of thing __very__ quicky:

   solar_elevations = NArray::sint 'solar_elevations.data', samples, lines

   lines.times |j|
     line = solar_elevations[ true, j ]
     dark = line.lt(-3).where
     ...
     ...
   end

here dark is the array having values like

   [ 1, 2, 3, 6789, 6790, 6791 ]

that i want to reduce to a list of ranges.

in reality the ranges are huge and there will, in amost all cases except
crossing the poles, be only one.  also note that 'dark' is a sorted list.  my
current optimization is

   min, max = dark[0], dark[dark.size - 1]

   ranges =
     if((max - min + 1) != dark.size)
       slow_search dark
     else
       [ min .. max ]
     end

   ranges.each do |range|
     #
     # munge data based on ranges which are small and fast
     #
   end


i can't think of anything better than brute force for the 'slow_search' but
thought i'd throw it out there...

cheers.

-a
-- 
===============================================================================
| email :: ara [dot] t [dot] howard [at] noaa [dot] gov
| phone :: 303.497.6469
| My religion is very simple.  My religion is kindness.
| --Tenzin Gyatso
===============================================================================