From: "Kroeger Simon (ext)" <simon.kroeger.ext@...>
Date: 2005-08-05T21:15:22+09:00
Subject: Re: algorithm help

 
> Hm, my alogorithm analysis is quite rusty but I believe you 
> would have to 
> get rid of m and replace it as an expression of n; reason 
> being that m is 
> part of the result and not part of the input.  So you 
> probably have to 
> calculate something like an average number of range for the 
> set of input 
> range.  Difficult without further knowledge of the data's 
> nature.  My gut 
> guess is that for random numbers the number of ranges is 
> rather close to n 
> so that would make O(n*log n) which doesn't exactly look 
> better than O(n)...

true, this is optimized for the given case (m <= 2).
 
> Anyway with the low numbers of n we're dealing with here 
> other effects are 
> likely more dramatic.  So doing a benchmark of all solutions 
> provided might 
> yield surprising results.
> 
> >> Btw, here's another funny idea:
> >>
> >> -----------------
> >> data = [3, 4, 5, 6, 7, 8, 9, 15, 38, 39, 40, 41, 6789, 6790,
> >> 9998, 9999]
> >> ranges = []
> >>
> >> data.inject(0) {|s,x| s | (1 << x)}.to_s(2).reverse!.scan(/1+/) do
> >>   |m| s = $`.length
> >>   ranges << (s .. (s + m.length - 1))
> >> end
> >>
> >> puts ranges
> >> -----------------
> >>
> >> Kind regards
> >>
> >>     robert
> >
> > Rofl, indead a funny idea. For sure the slowest one mentioned here
> 
> Did you benchmark them?

this creates a BigInt 1250 Bytes width, alocates 10 kByte of memory,
fills it, reverses it, and scans it with a regular expression. All to
look at 17 fixnums, it may be O(C * n) but with a realy huge C. 

> > d = [1, 3, 4, 5, 6, 7, 8, 9, 15, 38, 39, 40, 41, 6789, 6790, 9998,
> > 9999] puts
> d.inject([d[0]..d[0]]){|r,x|r<<(((r.last.end+1>=x)?r.pop.end: x)..x)}
> >
> > lets see if you can beat this :))
> 
> Nah, unlikely.  ATM I don't feel like investing that much 
> time.  Btw, two 
> points of your solution vs. the bit set approach (above):
> 
>  - This solution breaks for the empty array.
> 
> >> [][0] .. [][0]
> ArgumentError: bad value for range
>         from (irb):5
> 
>  - It needs a sorted array.
> 
> So checks to cope with these make your bit a bit longer. :-}

ok, I don't want to invest that much time either, but your code
doesn't cope with negativ numbers :)

it was fun, 

Simon