«

Martin DeMello schrieb:
> Ara.T.Howard <> 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

On Tue, 2 Aug 2005, Pit Capitain wrote:

>> 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]

sorry it took me so long to respond pit and martin... got sidetracked. your
binary search idea was perfect! for the actual data i'll be working with this
should be either O(1) or O(log(n)) - thought it can obviously degrade in the
general case. i used your idea in essentially the reverse pit, here's what i
ended up with:


harp:~ > cat a.rb

def sequences list
distance = lambda do |a,b|
(b - a).abs
end

continuous = lambda do |range, list|
first, last = range.first, range.last
a, b = list[first], list[last]
(list.empty? or (distance[a,b] == distance[first,last])) ? (a .. b) : nil
end

discrete = lambda do |range, list|
first, last = range.first, range.last
edge = last + 1
edge >= list.length or distance[list[last], list[edge]] > 1
end

sequence = lambda do |range, list|
first, last = range.first, range.last
list[first] .. list[last]
end

last = list.length - 1
a, b = 0, last

accum = []

while a <= b and a < list.length and b < list.length
range = a .. b

if continuous[ range, list ]
if discrete[ range, list ]
accum << sequence[ range, list ]
a, b = b + 1, last # move a and b up
else
b = b + distance[b, last] / 2 # move b up
end
else
b = a + distance[a, b] / 2 # move b down
end
end

accum
end

tests = [
[],
[0],
[0,1],
[0,1,2],
[0,1,2,3],
[0,3],
[0,3,5],
[0,3,5,7],
[0,1,3,4],
[0,1,3,4,6,7],
[0,1,3,4,6,7,9,10],
[0,1,3,4,6,7,10],
[0,3,4,6,7,9,10],
[0,1,3],
[0,3,4],
[0,-1],
[0,-1,-2],
[0,-1,-3,-4],
[0,-1,-3,-4,-6],
[0,-1,-3,-4,-6,-7],
[-1,-3,-4,-6,-7],
[-3,-4],
[-3,-4,-6, *(-42 .. -.to_a.reverse],
]

tests.each do |a|
printf "%-37.37s => %37.37s\n", a.inspect, sequences(a).inspect
a.reverse!
printf "%-37.37s => %37.37s\n", a.inspect, sequences(a).inspect
end



harp:~ > ruby a.rb
[] => []
[] => []
[0] => [0..0]
[0] => [0..0]
[0, 1] => [0..1]
[1, 0] => [1..0]
[0, 1, 2] => [0..2]
[2, 1, 0] => [2..0]
[0, 1, 2, 3] => [0..3]
[3, 2, 1, 0] => [3..0]
[0, 3] => [0..0, 3..3]
[3, 0] => [3..3, 0..0]
[0, 3, 5] => [0..0, 3..3, 5..5]
[5, 3, 0] => [5..5, 3..3, 0..0]
[0, 3, 5, 7] => [0..0, 3..3, 5..5, 7..7]
[7, 5, 3, 0] => [7..7, 5..5, 3..3, 0..0]
[0, 1, 3, 4] => [0..1, 3..4]
[4, 3, 1, 0] => [4..3, 1..0]
[0, 1, 3, 4, 6, 7] => [0..1, 3..4, 6..7]
[7, 6, 4, 3, 1, 0] => [7..6, 4..3, 1..0]
[0, 1, 3, 4, 6, 7, 9, 10] => [0..1, 3..4, 6..7, 9..10]
[10, 9, 7, 6, 4, 3, 1, 0] => [10..9, 7..6, 4..3, 1..0]
[0, 1, 3, 4, 6, 7, 10] => [0..1, 3..4, 6..7, 10..10]
[10, 7, 6, 4, 3, 1, 0] => [10..10, 7..6, 4..3, 1..0]
[0, 3, 4, 6, 7, 9, 10] => [0..0, 3..4, 6..7, 9..10]
[10, 9, 7, 6, 4, 3, 0] => [10..9, 7..6, 4..3, 0..0]
[0, 1, 3] => [0..1, 3..3]
[3, 1, 0] => [3..3, 1..0]
[0, 3, 4] => [0..0, 3..4]
[4, 3, 0] => [4..3, 0..0]
[0, -1] => [0..-1]
[-1, 0] => [-1..0]
[0, -1, -2] => [0..-2]
[-2, -1, 0] => [-2..0]
[0, -1, -3, -4] => [0..-1, -3..-4]
[-4, -3, -1, 0] => [-4..-3, -1..0]
[0, -1, -3, -4, -6] => [0..-1, -3..-4, -6..-6]
[-6, -4, -3, -1, 0] => [-6..-6, -4..-3, -1..0]
[0, -1, -3, -4, -6, -7] => [0..-1, -3..-4, -6..-7]
[-7, -6, -4, -3, -1, 0] => [-7..-6, -4..-3, -1..0]
[-1, -3, -4, -6, -7] => [-1..-1, -3..-4, -6..-7]
[-7, -6, -4, -3, -1] => [-7..-6, -4..-3, -1..-1]
[-3, -4] => [-3..-4]
[-4, -3] => [-4..-3]
[-3, -4, -6, -8, -9, -10, -11, -12, - => [-3..-4, -6..-6, -8..-42]
[-42, -41, -40, -39, -38, -37, -36, - => [-42..-8, -6..-6, -4..-3]



your ideas were essential to getting the peice of code i'm working on now
running in a reasonable amount of time - thanks to all the contributors!

-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
================================================== =============================

Ara.T.Howard wrote:

<snip>

> your ideas were essential to getting the peice of code i'm working on now
> running in a reasonable amount of time - thanks to all the contributors!
>
> -a

No applause please. Just throw money (at RubyCentral).



Regards,

Dan

On Thu, 4 Aug 2005, Daniel Berger wrote:

> Ara.T.Howard wrote:
>
> <snip>
>
>> your ideas were essential to getting the peice of code i'm working on now
>> running in a reasonable amount of time - thanks to all the contributors!
>>
>> -a
>
> No applause please. Just throw money (at RubyCentral).

how? i bought the new book...

-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
================================================== =============================