From: Charles Oliver Nutter Date: 2008-06-21T08:12:12+09:00 Subject: Re: Ruby vs JRuby Performance --Boundary_(ID_A0ZfXFZqzcxrj8itQwvLsw) Content-type: text/plain; format=flowed; charset=UTF-8 Content-transfer-encoding: 7BIT Victor Reyes wrote: > The code is attached to this thread. > However, I will send it to your email. > Also, remember that this is code written by a Rubist wannabe and not > necessary by one who knows the ins and outs of the language. > I'll be interested in knowing what you find! Ok, I managed to get it to run a few times in a cycle. First here's MRI's time for me: Elapsed time: around 0.191s Now the time running "jruby sudoku01final.rb" (all using JRuby trunk, "soylatte" Java 6 on OS X) Elapsed time: anywhere from 0.491s to 0.525s If I specify --server, it degrades on this short run: Elapsed time: 1.6s to 1.65s However, trying both runs ten times produces a very different result: Ten times without --server: Elapsed time (final result): 0.105s Ten times with --server: Elapsed time (final result): 0.212s So there's some interesting slowdown for this short benchmark running under server. Let's try 100 iterations: 100 times without --server: Elapsed time (final result): 0.103 100 times with --server: Elapsed time (final result): 0.065s It seems like the run is just too short for the server VM to really do much optimization, which is why we have JRuby run with the client VM by default. I've attached the modified source. - Charlie --Boundary_(ID_A0ZfXFZqzcxrj8itQwvLsw) Content-type: text/plain; name=sudoku01Final.rb; x-mac-creator=68446D70; x-mac-type=42494E41 Content-transfer-encoding: 7BIT Content-disposition: inline; filename=sudoku01Final.rb class Sudoku def initialize # This array contents, @ga, should be replaced with your puzzle or one of the # puzzles below. @ga = [ [0,0,2,0,5,0,0,0,0], [0,3,0,0,1,0,6,5,0], [0,6,0,7,2,9,0,0,0], [0,0,4,0,0,0,3,2,7], [0,0,0,0,0,0,0,0,0], [7,2,8,0,0,0,1,0,0], [0,0,0,5,4,8,0,7,0], [0,4,9,0,7,0,0,1,0], [0,0,0,0,3,0,4,0,0] ] # This is considered HARD # @ga = [ # [0,0,8,0,6,0,3,0,0], # [5,7,0,0,0,0,0,0,2], # [0,3,0,7,0,0,0,0,0], # [0,0,0,9,0,5,0,0,6], # [0,9,0,0,7,0,0,8,0], # [6,0,0,3,0,4,0,0,0], # [0,0,0,0,0,8,0,6,0], # [2,0,0,0,0,0,0,5,8], # [0,0,9,0,1,0,7,0,0] # ] @gam = [ # This is a mirror of @ga when first given. [0,0,0,0,1,9,0,4,0], [0,0,4,8,0,0,6,0,0], [7,5,0,0,0,0,0,0,2], [0,9,0,1,0,2,0,0,4], [0,0,0,0,0,3,0,0,0], [5,0,0,4,0,6,0,3,0], [8,0,0,0,0,0,0,7,3], [0,0,6,0,0,8,4,0,0], [0,1,0,2,9,0,0,0,0] ] # @done = [ # [2,1,8,4,9,7,5,3,6], # [3,6,9,8,2,5,1,4,7], # [7,5,4,1,6,3,9,8,2], # [8,2,6,3,5,4,7,1,9], # [9,3,5,2,7,1,8,6,4], # [4,7,1,9,8,6,3,2,5], # [1,9,3,5,4,2,6,7,8], # [5,4,7,6,1,8,2,9,3], # [6,8,2,7,3,9,4,5,1] # ] # The following sudoku is from: http://www.life.com/Life/sudoku/0,26379,,00.html # This puzzle is rated as: easy @a = [ [0,0,2,0,5,0,0,0,0], [0,3,0,0,1,0,6,5,0], [0,6,0,7,2,9,0,0,0], [0,0,4,0,0,0,3,2,7], [0,0,0,0,0,0,0,0,0], [7,2,8,0,0,0,1,0,0], [0,0,0,5,4,8,0,7,0], [0,4,9,0,7,0,0,1,0], [0,0,0,0,3,0,4,0,0] ] @ab = [ [0,0,0,0,1,0,0,0,0], [0,0,6,0,0,8,9,0,0], [0,1,0,5,2,6,0,0,0], [3,5,0,2,0,0,8,0,0], [0,2,0,0,0,0,0,1,0], [0,0,1,0,0,4,0,2,5], [0,0,0,1,3,2,0,7,0], [0,0,8,9,0,0,1,0,0], [0,0,0,0,6,0,0,0,0] ] @pp = [ [0,1,8,0,9,0,5,3,0], [0,0,9,0,2,0,0,4,7], [0,0,0,0,0,0,0,0,0], [8,0,0,3,0,4,7,0,0], [0,0,0,0,7,0,0,0,0], [0,0,1,9,0,6,0,0,5], [0,0,0,0,0,0,0,0,0], [5,4,0,0,1,0,2,0,0], [0,8,2,0,3,0,4,5,0] ] @aa = [ [123456789,123456789,123456789,123456789,123456789,123456789,123456789,123456789,123456789], [123456789,123456789,123456789,123456789,123456789,123456789,123456789,123456789,123456789], [123456789,123456789,123456789,123456789,123456789,123456789,123456789,123456789,123456789], [123456789,123456789,123456789,123456789,123456789,123456789,123456789,123456789,123456789], [123456789,123456789,123456789,123456789,123456789,123456789,123456789,123456789,123456789], [123456789,123456789,123456789,123456789,123456789,123456789,123456789,123456789,123456789], [123456789,123456789,123456789,123456789,123456789,123456789,123456789,123456789,123456789], [123456789,123456789,123456789,123456789,123456789,123456789,123456789,123456789,123456789], [123456789,123456789,123456789,123456789,123456789,123456789,123456789,123456789,123456789] ] @elem = Array.new @tmp = Array.new @index = Array.new @elapsedTime = Time.now puts @elapsedTime end # End of method initialize ################################## # This method takes an integer as input. # It returns an array of the digits found in the input. # For example, if the input is: 37615 # Th output will be the array [3,7,6,1,5] ################################### def int_split(x) r=[x];r[0,1]=*r[0].divmod(10)while r[0]>9;r end ########################## # This method counts the frequency of a # digit in the input array. ########################## def frequencyOfDigits(arrInput) h = Hash.new(0) arrInput.each {|x| h[x] += 1} return h end ############################################ # This method will set the initial board with the values provided by the user. # ############################################ def setInitialGrid for r in 0..8 do # These are the rows found = 0 # When found = 1, found element, else row is all 0 @tmp = [] @index = [] for c in 0..8 do # These are the colmns if @ga[r][c] == 0 @ga[r][c] = @aa[r][c] # Push all possible values, 123456789, into array else found = 1 @tmp.push@ga[r][c] # @tmp contains given values for that row @index.push c # @index contains index of given values end end # End of for if found == 1 max = @tmp.size - 1 # @tmp contains given values for the row (0..max).each do |v| # Loop through given values (0..8).each do |cc| # Number of elements per row = 9 (0..8) newVal = @ga[r][cc] newVal = eliminateDups(@ga[r][cc], @tmp[v]) @ga[r][cc] = newVal # puts "Received newVal: #{newVal}" end # End do end # End do end # End if end # End outter for pGrid puts " " checkColumns end # End of method setInitialGrid ################################## # Now let's eliminate duplicate cells from the columns. # ################################## def checkColumns for c in 0..8 do # The column will change slower for r in 0..8 do # Columns if @ga[r][c].to_i > 0 and @ga[r][c].to_i < 10 element = @ga[r][c] # column = c for rr in 0..8 do if @ga[rr][c].to_i < 10 next end newVal = eliminateDups(@ga[rr][c], element) @ga[rr][c] = newVal newVal = checkForSingletons(@ga[rr]) @ga[rr]= newVal end # End for end # End if end # End inner loop end # End outter loop pGrid puts " " end # End checkColumns ################################## # Now let's eliminate duplicate cells from the rows. # ################################## def checkRows for r in 0..8 do for c in 0..8 do # Columns if @ga[r][c].to_i > 0 and @ga[r][c].to_i < 10 element = @ga[r][c] row = r for cc in 0..8 do if @ga[r][cc].to_i < 10 next end newVal = eliminateDups(@ga[r][cc], element) @ga[r][cc] = newVal newVal = checkForSingletons(@ga[r]) @ga[r]= newVal end # End for end # End if end # End inner loop end # End outter loop pGrid puts " " end # End checkRows ############################################## ############################################## # This methods, as the name implies, attempts to spot lone elements. # This is accomplished by counting each element frequency in either a row, column # or block. This method takes an array as input. ############################################## ############################################## def checkForSingletons(inA) savedinA = inA va = Array.new (0..8).each do |i| va = va + int_split(inA[i].to_i) # This stmt passes one cell at a time to the splitter end fredig = frequencyOfDigits(va) fredig.each_pair do |key, value| if value == 1 # If we found a singleton, isolate it. (0..8).each do |k| if savedinA[k].to_s.include?(key.to_s) savedinA[k] = key end # End if ... end # End do end # if value end # End do return savedinA end # End method ############################################## # This method scans input for duplicates. It will return a cell without duplicate.# # @ga is the main array. # ############################################## def driver controller = true while controller 0.upto(49) do |n| createBlocks checkColumns checkRows return if checkSolution end # End do end end # End method driver ################################################################# ################################################################# # This method will convert the 9x9 matrix into # smaller 9 elements arrays. Each array represents # a 3x3 block. The blocks are numbered from a to i. # # a, b, c # d, e, f # g, h, i # # Block a = x, y, z # l, m, n # o, p, q # This method will ensure no dups are found, when appropriate. # Also notice that all blocks arrays are created as global. That's to give # full access to other methods without having to pass them as parameters. ################################################################# ################################################################# def createBlocks # Create block a j = 0 @a = Array.new (0..2).each do |r| (0..2).each do |c| @a[j] = @ga[r][c] j += 1 end end ta = Array.new # Temporary array ta = @a.find_all {|e| e.to_i <= 9} (0..8).each do |cell| ta.each do |elem| newCell = eliminateDups(@a[cell], elem) @a[cell] = newCell end # End inner do loop end # End outter do loop newa = checkForSingletons(@a) @a = newa # Rebuild main array from block j = 0 (0..2).each do |r| (0..2).each do |c| @ga[r][c] = @a[j] j += 1 end end ################################ # Create block b j = 0 @b = Array.new (0..2).each do |r| (3..5).each do |c| @b[j] = @ga[r][c] print @b[j].to_s + " " j += 1 end end ta = Array.new # Temporary array ta = @b.find_all {|e| e.to_i <= 9} (0..8).each do |cell| ta.each do |elem| newCell = eliminateDups(@b[cell], elem) @b[cell] = newCell end # End inner do loop end # End outter do loop newb = checkForSingletons(@b) @b = newb # Rebuild main array from block j = 0 (0..2).each do |r| (3..5).each do |c| @ga[r][c] = @b[j] j += 1 end end ################################ # Create block c j = 0 @c = Array.new (0..2).each do |r| (6..8).each do |c| @c[j] = @ga[r][c] j += 1 end end ta = Array.new # Temporary array ta = @c.find_all {|e| e.to_i <= 9} (0..8).each do |cell| ta.each do |elem| newCell = eliminateDups(@c[cell], elem) @c[cell] = newCell end # End inner do loop end # End outter do loop newc = checkForSingletons(@c) @c = newc # Rebuild main array from block j = 0 (0..2).each do |r| (6..8).each do |c| @ga[r][c] = @c[j] j += 1 end end ################################## ############ Next block of 3x3 ## ################################## # Create block d j = 0 @d = Array.new (3..5).each do |r| (0..2).each do |c| @d[j] = @ga[r][c] j += 1 end end ta = Array.new # Temporary array ta = @d.find_all {|e| e.to_i <= 9} (0..8).each do |cell| ta.each do |elem| newCell = eliminateDups(@d[cell], elem) @d[cell] = newCell end # End inner do loop end # End outter do loop newd = checkForSingletons(@d) @d = newd # Rebuild main array from block j = 0 (3..5).each do |r| (0..2).each do |c| @ga[r][c] = @d[j] j += 1 end end ################################ # Create block e j = 0 @e = Array.new (3..5).each do |r| (3..5).each do |c| @e[j] = @ga[r][c] j += 1 end end ta = Array.new # Temporary array ta = @e.find_all {|e| e.to_i <= 9} (0..8).each do |cell| ta.each do |elem| newCell = eliminateDups(@e[cell], elem) @e[cell] = newCell end # End inner do loop end # End outter do loop newe = checkForSingletons(@e) @e = newe # Rebuild main array from block j = 0 (3..5).each do |r| (3..5).each do |c| @ga[r][c] = @e[j] j += 1 end end ################################ # Create block f j = 0 @f = Array.new (3..5).each do |r| (6..8).each do |c| @f[j] = @ga[r][c] j += 1 end end ta = Array.new # Temporary array ta = @f.find_all {|e| e.to_i <= 9} (0..8).each do |cell| ta.each do |elem| newCell = eliminateDups(@f[cell], elem) @f[cell] = newCell end # End inner do loop end # End outter do loop newf = checkForSingletons(@f) @f = newf # Rebuild main array from block j = 0 (3..5).each do |r| (6..8).each do |c| @ga[r][c] = @f[j] j += 1 end end ################################ puts ################################## ############ Next block of 3x3 ## ################################## # Create block g j = 0 @g = Array.new (6..8).each do |r| (0..2).each do |c| @g[j] = @ga[r][c] j += 1 end end ta = Array.new # Temporary array ta = @g.find_all {|e| e.to_i <= 9} (0..8).each do |cell| ta.each do |elem| newCell = eliminateDups(@g[cell], elem) @g[cell] = newCell end # End inner do loop end # End outter do loop newg = checkForSingletons(@g) @g = newg # Rebuild main array from block j = 0 (6..8).each do |r| (0..2).each do |c| @ga[r][c] = @g[j] j += 1 end end ################################ # Create block h j = 0 @h = Array.new (6..8).each do |r| (3..5).each do |c| @h[j] = @ga[r][c] j += 1 end end ta = Array.new # Temporary array ta = @h.find_all {|e| e.to_i <= 9} (0..8).each do |cell| ta.each do |elem| newCell = eliminateDups(@h[cell], elem) @h[cell] = newCell end # End inner do loop end # End outter do loop newh = checkForSingletons(@h) @h = newh # Rebuild main array from block j = 0 (6..8).each do |r| (3..5).each do |c| @ga[r][c] = @h[j] j += 1 end end ################################ j = 0 @i = Array.new (6..8).each do |r| (6..8).each do |c| @i[j] = @ga[r][c] j += 1 end end ta = Array.new # Temporary array ta = @i.find_all {|e| e.to_i <= 9} (0..8).each do |cell| ta.each do |elem| newCell = eliminateDups(@i[cell], elem) @i[cell] = newCell end # End inner do loop end # End outter do loop newi = checkForSingletons(@i) @i = newi # Rebuild main array from block j = 0 (6..8).each do |r| (6..8).each do |c| @ga[r][c] = @i[j] j += 1 end end pGrid ################################ end # End of createBlocks ######################################################### # This method scans a cell removing dumplicate elements, after the initial board and after each find. # cell represents one sudoku square, element is one of the given element. # cell could be: 123456789 or less. # element could be: Any single digit 1..9. ######################################################### def eliminateDups(cell, element) newStr = "" if cell.to_s.scan(element.to_s) # Does cell contains element? str = cell.to_s len = str.length if len == 1 # If length is 1, we have only one digit return cell end else return cell # Return to caller if value does not exist end (0..len-1).each do |f| if str[f,1] == element.to_s # If equal, then skip it and don't save it next else newStr = newStr + str[f,1].to_s # Build new string without dup end end # End do return newStr end # End of method eliminateDups #################### # Print current state of the grid # # The stmt: @ga[r][c] # # Where: # # r = row, c = column # #################### def pGrid for r in 0..8 do outR = "" for c in 0..8 do outR = outR + @ga[r][c].to_s + " " end # End of inner for puts outR end # End outer for end # End of method pGrid ########################## # Check all rows and columns # ########################## def checkSolution solved = 1 # Assume solved # If any element is larger than > 9, puzzle is not solved! (0..8).each do |r| if @ga[r].find {|v| v.to_i > 9} solved = 0 end end if solved == 1 puts "SOLVED!" pGrid # @@gcounter += 1 # puts "Number of iterations: #{@@gcounter}" @elapsedTime = Time.now - @elapsedTime puts "Elapsed Time: #{@elapsedTime}" true end end end # End of Class @@gcounter = 0 # Global variable @@gcounter ####################### # This is the Genesis # ####################### 100.times { ms = Sudoku.new # Output initial settings ms.pGrid # Set puzzle with given values ms.setInitialGrid # Apply the Given Numbers ms.pGrid ms.checkSolution ms.driver } --Boundary_(ID_A0ZfXFZqzcxrj8itQwvLsw)--