From: 7stud -- <dolgun@...>
Date: 2007-10-03T22:24:51+09:00
Subject: Re: Searching through a sorted array

FireAphis wrote:
>
> Neat. Not space efficient
>

Yes, you're right. I wouldn't recommend it for really large arrays.  The 
original sorted array could also be abandoned in favor of a hash to 
begin with.


> But if the IDs
> have large gaps ([10000, 20000, 30000]) do you think it still will be
> more efficient compared to a simple iteration?
>

Depending on how you write the simple iteration, the hash method can be 
a lot slower.

>
> a simple loop will have three iterations whereas your implementation
> will have 30000 iteration.
> 

What if a simple iteration has 3 iterations x 3,000 range checks, e.g.:

  dogs_in_range = []

  dogs.each do |dog|
    range.each do |r|
      if dog.id == r
        dogs_in_range << dog
      end
    end
  end
-- 
Posted via http://www.ruby-forum.com/.