views:

675

answers:

3

I asked a question yesterday about comparing ranges for overlap and its been stuck in my throat ever since.

The consensus seems to be that my preferred answer which involves using the array intersection operator (&), is inefficient because comparing arrays is costly.

I wonder then, why this feature is in the language? Could it be that the language creators believed that sometimes you need an elegant way to achieve a solution even if it's expensive to do so? Is comparing arrays so costly that you should avoid it whenever possible? The whole attraction of Ruby for me is the focus on syntactic elegance over premature optimization.

+4  A: 

Yesterday's question's wording made it sound like you were computing a binary condition: do these ranges overlap? The answers that were given can be computed in constant time, so if they work for you, it makes sense to stick with them.

The & operator would be appropriate if you need to know the extent of the overlap, but that wasn't what you were asking about.

As for why it exists at all, I can only speculate: Not only does it add convenience, but it's not hard to imagine ways in which an array conjunction operation could be optimized by the language environment -- even if its computation might still require linear or n*log(n) time in the worst cases. (If every operation has to have a constant-time result, we'd have to get rid of quite a few methods!)

Dan Breslau
+7  A: 

& is not a particularly inefficient method. I think you misunderstood the criticism of the accepted answer.

Your preferred solution is inefficient because it converts the ranges to arrays.

A range such as 1..10000 has a relatively small memory footprint - it only stores the start and end points. But if you convert it to an array, you allocate memory for all 10,000 entries.

Sarah Mei
So we should be concerned about working with large arrays? Ok, you make a good point - I started out with a more efficient storage structure - a range - and switched to using a less efficient structure. I'm just skeptical whether we should be so concerned with this optimization.
I don't think it's premature optimization to use what's available on the Range objects instead of doing a (potentially) costly conversion. MarkusQ's answer is simple, easy to read, one line, and efficient for any size Range.
Sarah Mei
Point taken. Thanks.
A: 

Arrays in Ruby are untyped: they can contain a mix of types including hashes, other arrays, symbols, whatever. In a typed array sorting and comparison is much simpler. Comparing untyped collections (especially collections containing collections) is more costly by nature.

Demi