Finding gaps in a sorted sequence

Discussion in 'Ruby' started by Pete Hodgson, Nov 6, 2008.

  1. Pete Hodgson

    Pete Hodgson Guest

    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
    Pete Hodgson, Nov 6, 2008
    #1
    1. Advertising

  2. Pete Hodgson

    Guest

    On Thu, Nov 6, 2008 at 12:39 PM, Pete Hodgson <> 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
    , Nov 6, 2008
    #2
    1. Advertising

  3. Pete Hodgson 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


    --
    Posted via http://www.ruby-forum.com/.
    Siep Korteling, Nov 6, 2008
    #3
  4. Pete Hodgson

    Zeekar Guest

    PH = Pete Hodgson
    SK = Siep Korteling

    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.
    Zeekar, Nov 6, 2008
    #4
  5. Pete Hodgson

    Brian Adkins Guest

    Pete Hodgson <> 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/
    Brian Adkins, Nov 7, 2008
    #5
  6. On Thu, Nov 6, 2008 at 9:39 AM, Pete Hodgson <> 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
    Martin DeMello, Nov 7, 2008
    #6
  7. Pete Hodgson

    Suninny Guest

    [Note: parts of this message were removed to make it a legal post.]

    unsubscribe
    Suninny, Nov 7, 2008
    #7
  8. Pete Hodgson

    Brian Adkins Guest

    Martin DeMello <> writes:

    > On Thu, Nov 6, 2008 at 9:39 AM, Pete Hodgson <> 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


    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.

    --
    Brian Adkins
    http://www.lojic.com/
    http://lojic.com/blog/
    Brian Adkins, Nov 7, 2008
    #8
  9. Pete Hodgson

    Robert Dober Guest

    On Fri, Nov 7, 2008 at 9:28 AM, Brian Adkins <> wrote:
    > Martin DeMello <> 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=E9ritablement utile puisque c'est joli.

    Antoine de Saint Exup=E9ry
    Robert Dober, Nov 7, 2008
    #9
  10. Pete Hodgson

    Brian Adkins Guest

    Robert Dober <> writes:

    > On Fri, Nov 7, 2008 at 9:28 AM, Brian Adkins <> wrote:
    >> Martin DeMello <> 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 :)

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


    --
    Brian Adkins
    http://www.lojic.com/
    http://lojic.com/blog/
    Brian Adkins, Nov 7, 2008
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Arthur Dent
    Replies:
    1
    Views:
    1,062
    Jim Gibson
    Dec 3, 2003
  2. greg
    Replies:
    4
    Views:
    368
  3. Mark247
    Replies:
    1
    Views:
    618
    Marrow
    Sep 3, 2004
  4. desktop
    Replies:
    7
    Views:
    382
    desktop
    Jun 11, 2007
  5. Tomasz Wegrzanowski
    Replies:
    6
    Views:
    105
    Robert Klemme
    Aug 5, 2006
Loading...

Share This Page