From: Kevin Anon <oblivious.sage@...>
Date: 2011-09-19T00:51:53+09:00
Subject: Ruby Speed Question

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/.