Iterate through array twice

Discussion in 'Ruby' started by Ruhe, Feb 16, 2008.

  1. Ruhe

    Ruhe Guest

    I have array of horizontal segments and I need to find which of them
    may be sides of a box, so I implemented this method:

    def find_square_sides(horiz_segments)
    squares = Array.new
    horiz_segments.each_with_index do |side, i|
    horiz_segments[(i+1)..(horiz_segments.size - 1)].each do |
    condidate|
    if(## here goes long-long check ##)
    squares << Square.new(side, condidate)
    end
    end
    end
    squares
    end


    Knowing the beauty of Ruby, I hope that there is a better solution. I
    guess that double iterating isn't the best.
     
    Ruhe, Feb 16, 2008
    #1
    1. Advertising

  2. On 16.02.2008 15:46, Ruhe wrote:
    > I have array of horizontal segments and I need to find which of them
    > may be sides of a box, so I implemented this method:
    >
    > def find_square_sides(horiz_segments)
    > squares = Array.new
    > horiz_segments.each_with_index do |side, i|
    > horiz_segments[(i+1)..(horiz_segments.size - 1)].each do |
    > condidate|
    > if(## here goes long-long check ##)
    > squares << Square.new(side, condidate)
    > end
    > end
    > end
    > squares
    > end
    >
    >
    > Knowing the beauty of Ruby, I hope that there is a better solution. I
    > guess that double iterating isn't the best.


    Unfortunately the problem you are trying to solve is O(n*n) and there is
    nothing that will make this go away - at least not with the knowledge we
    have so far. It may be that elements to compare to can be picked more
    efficiently but if you have to compare each with each other your
    solution is probably as good as it gets.

    Kind regards

    robert


    PS: The only small improvement that came to mind was to use -1 as ending
    index for the range of the second iteration.
     
    Robert Klemme, Feb 16, 2008
    #2
    1. Advertising

  3. With Ruby 1.9:

    def find_square_sides(horiz_segments)
    squares = Array.new
    horiz_segments.combination(2) do |side, candidate|
    if (...whatever...)
    squares << Square.new(side, candidate)
    end
    end
    end

    On Feb 16, 2008 6:49 AM, Ruhe <> wrote:
    > I have array of horizontal segments and I need to find which of them
    > may be sides of a box, so I implemented this method:
    >
    > def find_square_sides(horiz_segments)
    > squares = Array.new
    > horiz_segments.each_with_index do |side, i|
    > horiz_segments[(i+1)..(horiz_segments.size - 1)].each do |
    > condidate|
    > if(## here goes long-long check ##)
    > squares << Square.new(side, condidate)
    > end
    > end
    > end
    > squares
    > end
    >
    >
    > Knowing the beauty of Ruby, I hope that there is a better solution. I
    > guess that double iterating isn't the best.
    >
    >
     
    Christopher Dicely, Feb 16, 2008
    #3
  4. Ruhe

    Ruhe Guest

    Yes, Ruby is the most beautiful language!

    On 16 ÆÅ×, 21:20, Christopher Dicely <> wrote:
    > With Ruby 1.9:
    >
    > def find_square_sides(horiz_segments)
    > squares = Array.new
    > horiz_segments.combination(2) do |side, candidate|
    > if (...whatever...)
    > squares << Square.new(side, candidate)
    > end
    > end
    > end
    >
    > On Feb 16, 2008 6:49 AM, Ruhe <> wrote:
     
    Ruhe, Feb 16, 2008
    #4
    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. Gogo
    Replies:
    1
    Views:
    2,106
    Sudsy
    Sep 4, 2003
  2. runescience
    Replies:
    0
    Views:
    1,462
    runescience
    Feb 9, 2006
  3. John
    Replies:
    4
    Views:
    921
    RedGrittyBrick
    Apr 1, 2008
  4. Guest
    Replies:
    1
    Views:
    177
    Bob Barrows [MVP]
    Apr 18, 2005
  5. Skye Weir-mathewes
    Replies:
    3
    Views:
    131
    Stefano Crocco
    Apr 17, 2007
Loading...

Share This Page