Hi Folks, Given a sorted enumeration I need to find the first gap in a sequence. e.g. 3 == find_gap [1,2,4,5] nil == find_gap [1,2,3,4] Here's the best I can come up with def first_gap( seq ) seq.each_cons(2) do |l,r| _next = l.next return _next if r!= _next end nil end but it seems rather ugly. Anyone have a more elegant implementation? Cheers, Pete

on 2008-11-06 19:41

on 2008-11-06 20:07

On Thu, Nov 6, 2008 at 12:39 PM, Pete H. <removed_email_address@domain.invalid> wrote: > Given a sorted enumeration I need to find the first gap in a sequence. > > e.g. > 3 == find_gap [1,2,4,5] > nil == find_gap [1,2,3,4] $ cat bar.rb def find_gap array f = array.first l = array.last s = l - f + 1 return nil if s == array.size if array.size == 2 return f + 1 end c = array.size / 2 if array[c] != f + c a = find_gap(array[0..c]) else b = find_gap(array[c..-1]) end a ? a : b end p find_gap([1,2,4,5]) p find_gap([1,2,3,4]) p find_gap([1,2,3,4,5,6,7,11,12]) p find_gap([2,3,4,5,6,7,11,12]) $ ruby bar.rb 3 nil 8 8

on 2008-11-06 22:52

Pete H. wrote: > Hi Folks, > > Given a sorted enumeration I need to find the first gap in a sequence. > > e.g. > 3 == find_gap [1,2,4,5] > nil == find_gap [1,2,3,4] > > Here's the best I can come up with > > def first_gap( seq ) > seq.each_cons(2) do |l,r| > _next = l.next > return _next if r!= _next > end > nil > end > > but it seems rather ugly. Anyone have a more elegant implementation? > > Cheers, > Pete The following does not quite meet your specs (it returns an array with all gaps, empty if there are no gaps). Anyway, here is my try: def find_gaps( ar ) (ar.first .. ar.last).to_a - ar end p find_gaps( [1,2,4,5] ) p find_gaps( ["a", "b", "d", "e", "h"] ) require 'date' d1 = Date.new(2008,11,6) d2 = Date.new(2008,11,7) d3 = Date.new(2008,11,9) puts find_gaps( [d1,d2,d3] ) => [3] => ["c", "f", "g"] => 2008-11-08 hth, Siep

on 2008-11-07 00:25

PH = Pete H. SK = Siep K. PH> Given a sorted enumeration I need to find the first gap in a sequence. PH> e.g. PH> 3 == find_gap [1,2,4,5] PH> nil == find_gap [1,2,3,4] SK> The following does not quite meet your specs (it returns an array with SK> all gaps, empty if there are no gaps). Anyway, here is my try: > > def find_gaps( ar ) > (ar.first .. ar.last).to_a - ar > end Given the above definition, it's easy to get Pete's behavior exactly: def find_gap( ar ) find_gaps(ar).first end And then you have a choice of methods to use, depending on whether you need the full list or just the first gap.

on 2008-11-07 06:22

Pete H. <removed_email_address@domain.invalid> writes: > def first_gap( seq ) > seq.each_cons(2) do |l,r| > _next = l.next > return _next if r!= _next > end > nil > end > > but it seems rather ugly. Anyone have a more elegant implementation? I think your version is pretty readable. However, it appears you do pay a 60% speed penalty with the Enumerator version. So I guess it depends on whether conciseness and readability are more important than efficiency, or not. --- snip --- require 'enumerator' require 'benchmark' include Benchmark def first_gap list list.each_cons(2) do |l,r| _next = l.next return _next unless r == _next end nil end def other_gap list prev = nil list.each do |e| if prev && (n = prev.next) != e return n end prev = e end nil end t = (1..100).to_a [100, 250, 500].each do |n| t = (1..n).to_a bm(5) do |x| x.report('first') { 1_000.times { first_gap(t) } } x.report('other') { 1_000.times { other_gap(t) } } end end --- snip --- ~/temp$ ruby first_gap.rb user system total real first 0.700000 0.250000 0.950000 ( 0.957255) other 0.430000 0.170000 0.600000 ( 0.604145) user system total real first 1.720000 0.630000 2.350000 ( 2.354915) other 1.070000 0.420000 1.490000 ( 1.490321) user system total real first 3.470000 1.250000 4.720000 ( 4.838116) other 2.120000 0.840000 2.960000 ( 3.018840)

on 2008-11-07 09:21

On Thu, Nov 6, 2008 at 9:39 AM, Pete H. <removed_email_address@domain.invalid> wrote: > Hi Folks, > > Given a sorted enumeration I need to find the first gap in a sequence. > > e.g. > 3 == find_gap [1,2,4,5] > nil == find_gap [1,2,3,4] irb(main):001:0> g = [1,2,3,5,6,8,9,10] => [1, 2, 3, 5, 6, 8, 9, 10] irb(main):002:0> gap = g.inject {|a, e| e == a.next ? e : (break a.next)} => 4 martin

on 2008-11-07 10:32

Martin DeMello <removed_email_address@domain.invalid> writes: > => [1, 2, 3, 5, 6, 8, 9, 10] > > irb(main):002:0> gap = g.inject {|a, e| e == a.next ? e : (break a.next)} > => 4 Beautiful. Excellent use of inject :) I would've thought this would be better performing also, but it lags the 'each' version by quite a bit: user system total real OP 3.490000 1.240000 4.730000 ( 4.755358) Brian 2.170000 0.830000 3.000000 ( 3.000508) Martin 3.320000 1.240000 4.560000 ( 4.582286) I still think I like it best though because it seems to be the most natural Ruby solution to the original problem.

on 2008-11-07 20:17

On Fri, Nov 7, 2008 at 9:28 AM, Brian A. <removed_email_address@domain.invalid> wrote: > Martin DeMello <removed_email_address@domain.invalid> writes: <snip> > I still think I like it best though because it seems to be the most > natural Ruby solution to the original problem. Well not quite, it does not return nil if there is no gap, one has to check if the return value is the last element of the array and replace it with nil in that case. One should know that inject is quite slow, but no reason not to use it unless performance is a problem. Cheers Robert -- C'est véritablement utile puisque c'est joli. Antoine de Saint Exupéry

on 2008-11-07 23:45

Robert D. <removed_email_address@domain.invalid> writes: > On Fri, Nov 7, 2008 at 9:28 AM, Brian A. <removed_email_address@domain.invalid> wrote: >> Martin DeMello <removed_email_address@domain.invalid> writes: > <snip> >> I still think I like it best though because it seems to be the most >> natural Ruby solution to the original problem. > Well not quite, it does not return nil if there is no gap, D'oh! I missed that. Ok, I guess I like my version best again then :)