From: Pit Capitain <pit@...>
Date: 2005-08-02T16:50:11+09:00
Subject: Re: algorithm help

Martin DeMello schrieb:
> Ara.T.Howard <Ara.T.Howard@noaa.gov> wrote:
> 
>>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...
> 
> This might work better: binary search for {x | (x - min) == (i_x - i_min)},
> set i_min to i_x+1 and repeat. For an added optimisation, run two loops
> in parallel, searching from each end.

Just in case you haven't implemented Martin's binary search idea yet:

   def gap?( data, min, max )
     data[ max ] - data[ min ] > max - min
   end

   def find_gaps( data, min, max, acc )
     if gap?( data, min, max )
       if max - min == 1
         acc << max
       else
         mid = ( max + min ) / 2
         find_gaps( data, min, mid, acc )
         find_gaps( data, mid, max, acc )
       end
     end
   end

   def gaps( data )
     acc = [ 0 ]
     find_gaps( data, 0, data.size - 1, acc )
     acc << data.size
   end

   def ranges( *data )
     gaps = gaps( data )
     ( 1 ... gaps.size ).map { |idx|
       data[ gaps[ idx - 1 ] ] .. data[ gaps[ idx ] - 1 ]
     }
   end

   p ranges( 1, 2, 3, 6789, 6790, 6791 )
   # => [1..3, 6789..6791]

Regards,
Pit