Re: Ruby Speed Question

On Sun, Sep 18, 2011 at 10:51 AM, Kevin Anon <[e-mail]>wrote:

> Wrote my first Ruby program recently for a class assignment where we had
> to examine the speed of binary search on various array sizes in 3
> different languages. After a little debugging, I managed to get the code
> working, but the difference in run-time between this and the other 2
> languages is significant enough that I'm wondering if I did something
> wrong.
>
> This takes 13-14 seconds total, while Java runs in just under a quarter
> of a second and C# runs in well under a hundredth of a second. I'm sure
> some of the slowdown for Ruby is that I'm doing it in JRuby on NetBeans,
> but even running it through a command prompt version of Ruby only
> knocked a second or two off the total runtime.
>
> Ruby code is below, Java & C# code are functionally identical.
>
> # recursive binary search
> # array = the array to be searched
> # target = what to look for
> # first = the first index of the range
> # last = the last index of the range
> # returns the index of target value, or -1 if not found
> def search(list, target, first = 0, last = list.length-1)
>  return -1 if first>last  # basis (not found)
>  mid = (first+last)/ 2
>  if list[mid]==target  # basis (mid is target)
>    mid
>  elsif target<list[mid]  # recur on left half
>    search(list, target, first, mid-1)
>  else  # recur on right half
>    search(list, target, mid+1, last)
>  end
> end
>
> # main method, tests binary search speed on arrays of varying sizes
> # for each array size, program does the following:
> #    1) fills array with even numbers (index times two)
> #    2) performs 500,000 unsuccessful searches (odd numbers only)
> #    3) reports total time & average time per search
> #    4) brings the array out of scope to remove it from memory
> if __FILE__ == $0
>  puts "Data Structures & Algorithms - Assignment 1 - Problem 5 -
> Ruby\n\n"
>  out_a = "Performing 500k searches on an array of length"
>  out_b = "required"
>  out_c = "seconds,\n an average of"
>  out_d = "nano-seconds per search."
>  size = 32
>  while size < 530000
>    list = Array.new
>    i = 0
>    while i<size  # fills the array with even numbers
>      list[i] = 2*i
>      i+=1
>    end
>    j = 1
>    check = 0
>    start = Time.now
>    while j<1000000  # search for odd numbers
>      r = search(list,j)
>      check -= r
>      j+=2
>    end
>    elapsed = Time.now - start  # elapsed time in seconds
>    if check!=500000
>      puts "ERROR! Successful search!  checksum = #{check}"
>    end
>    puts "#{out_a} #{size} #{out_b} #{elapsed} #{out_c} #{elapsed*2000}
> #{out_d}"
>    size *= 4
>  end
> end
>
> --
> Posted via http://www.ruby-forum.com/.
>
>
Java and C# are statically typed and compiled (well... more so than Ruby,
anyway). If your main use case is algorithms, those languages are a better
choice because they will much more performant (Fortran or C probably being
the best choice for such a use case). Though a decent compromise might be
Python, which has a pleasant developer experience like Ruby, but also offers
things like primitives, and has some nice libs for scientific use.


Some reasons differences between the Ruby and Java versions are that Ruby
doesn't have primitives, so all those numbers are objects (ie using Java's
Integer rather than int). Also, if you're using primitive Arrays in the
other languages, that can have an impact, as Ruby's arrays are more like
Java's ArrayLists. Also, the way you check your conditions isn't very
efficient (ie its' more likely to be less / greater than the target than
equal to the target, so by rearranging your checks, you can reduce the run
time -- though obviously not the time complexity).

Anyway, if your goal is just to look at time complexities, then Ruby is
fine, but you aren't really taking advantage of what it has to offer :) Some
simple things like:

Array initialization could be done like this
  Array.new(size) { |index| 2 * index }

Target iteration could be done like this
  (1..1_000_000).step 2 do |target|
    check -= search(list, target)
  end

You could put the search method directly on the arrays (some oppose monkey
patching, but I think this is an okay use case. A good compromise would be
creating a module with this method, then add it only to the arrays you want
to binary search)
  class Array
    def binary_search(target, first = 0, last = length-1)
      return -1 if first > last
      mid = (first+last) / 2
      return binary_search(target, first, mid-1) if target < self[mid]
      return binary_search(target, mid+1, last)  if target > self[mid]
      mid
    end
  end

The string thing is really confusing, you can just do it like this:
  puts "Performing 500k searches on an array of length #{size} required
#{elapsed} seconds,"
  puts " an average of #{elapsed*2000} nano-seconds per search"

Of course, this is just scratching the surface, this really isn't Ruby's
primary domain, so it hasn't got much opportunity to shine in this case.