From: FireAphis <FireAphis@...>
Date: 2007-10-03T21:15:10+09:00
Subject: Re: Searching through a sorted array

On Oct 3, 1:45 pm, 7stud -- <dol...@excite.com> wrote:
> FireAphis wrote:
> > My problem is that, as far as I know, find_all just iterates through
> > all the elements of the array and that's very inefficient, especially
> > in my case, in which I have a sorted array. Is there any standard way
> > to search efficiently through a sorted array? A binary search for
> > example?
>
> You can also turn your array into a hash, which will work just as well
> for unsorted arrays:
>
> class Dog
>   attr_reader :breed, :id
>
>   def initialize(breed, id)
>     @breed = breed
>     @id = id
>   end
>
> end
>
> #Create sorted array of Dog's:
> #-----------------------------
> dogs = []
> (1..2_000).each do |r|
>   dogs << Dog.new("Akita", r*2)
> end
>
> =begin
> dogs = (1..2000).inject([]) do |arr, r|
>   arr << Dog.new("Akita", r*2)
>   arr
> end
> =end
> #----------------------------+
>
> #Convert array to hash.
> #key: dog.id
> #val: Dog object
> #---------------------
> my_id_dog_hash = {}
>
> class << my_id_dog_hash
>   attr_accessor :highest_id
> end
>
> dogs.each do |dog|
>   my_id_dog_hash[dog.id] = dog
> end
>
> my_id_dog_hash.highest_id = dogs[-1].id
> ----------------------+
>
> #Find Dog's in range:
> #-------------------
> def get_dogs_in_range(id_dog_hash, range)
>
>   high_id = id_dog_hash.highest_id
>   if range.end > high_id
>     range = range.begin..high_id
>   end
>
>   dogs_in_range = []
>
>   range.each do |r|
>     dog = id_dog_hash[r]
>
>     if dog
>       dogs_in_range << id_dog_hash[r]
>     end
>
>   end
> =begin
>   dogs_in_range = range.inject([]) do |arr1, r|
>     if dog = id_dog_hash[r]
>       arr1 << dog
>     end
>
>     arr1
>   end
> =end
>
>   dogs_in_range
> end
> ------------------+
>
> #Test it out:
> ------------
> results = get_dogs_in_range(my_id_dog_hash, 1_990..2000)
> results.each {|dog| p dog}
> -----------+
>
> --output:--
> #<Dog:0x1a70c @id=1990, @breed="Akita">
> #<Dog:0x1a6e4 @id=1992, @breed="Akita">
> #<Dog:0x1a6bc @id=1994, @breed="Akita">
> #<Dog:0x1a694 @id=1996, @breed="Akita">
> #<Dog:0x1a66c @id=1998, @breed="Akita">
> #<Dog:0x1a644 @id=2000, @breed="Akita">
>
> --
> Posted viahttp://www.ruby-forum.com/.

Neat. Not space efficient but undoubtfully more quick. But if the IDs
have large gaps ([10000, 20000, 30000]) do you think it still will be
more efficient compared to a simple iteration? Consider the fact that
a simple loop will have three iterations whereas your implementation
will have 30000 iteration.

Thanks,
FireAphis