From: Brian Adkins <lojicdotcom@...>
Date: 2008-11-07T13:18:06+09:00
Subject: Re: Finding gaps in a sorted sequence

Pete Hodgson <phodgson@lyris.com> writes:

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

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)


-- 
Brian Adkins
http://www.lojic.com/
http://lojic.com/blog/