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