From: Robert Klemme <shortcutter@...>
Date: 2008-02-17T00:19:56+09:00
Subject: Re: Iterate through array twice

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.