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] = 2i
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} #{elapsed2000}
#{out_d}"
size *= 4
end
end
