summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--benchmark/bm_app_erb.rb52
-rw-r--r--benchmark/bm_app_uri.rb16
-rw-r--r--benchmark/bm_io_file_create.rb26
-rw-r--r--benchmark/bm_io_file_read.rb30
-rw-r--r--benchmark/bm_io_file_write.rb28
-rw-r--r--benchmark/bm_so_binary_trees.rb114
-rw-r--r--benchmark/bm_so_fannkuch.rb90
-rw-r--r--benchmark/bm_so_fasta.rb162
-rw-r--r--benchmark/bm_so_k_nucleotide.rb96
-rw-r--r--benchmark/bm_so_mandelbrot.rb114
-rw-r--r--benchmark/bm_so_meteor_contest.rb1128
-rw-r--r--benchmark/bm_so_nbody.rb296
-rw-r--r--benchmark/bm_so_nsieve.rb70
-rw-r--r--benchmark/bm_so_nsieve_bits.rb84
-rw-r--r--benchmark/bm_so_partial_sums.rb62
-rw-r--r--benchmark/bm_so_pidigits.rb184
-rw-r--r--benchmark/bm_so_reverse_complement.rb60
-rw-r--r--benchmark/bm_so_spectralnorm.rb100
-rw-r--r--benchmark/bm_vm1_ivar_set.rb12
-rw-r--r--benchmark/bm_vm2_eval.rb12
-rw-r--r--benchmark/driver.rb476
-rw-r--r--benchmark/make_fasta_output.rb38
-rw-r--r--benchmark/prepare_so_count_words.rb30
-rw-r--r--benchmark/prepare_so_k_nucleotide.rb4
-rw-r--r--benchmark/prepare_so_reverse_complement.rb4
-rw-r--r--id.h106
-rw-r--r--test/ruby/test_enumerator.rb94
27 files changed, 1744 insertions, 1744 deletions
diff --git a/benchmark/bm_app_erb.rb b/benchmark/bm_app_erb.rb
index c4fcfac..e58b7a3 100644
--- a/benchmark/bm_app_erb.rb
+++ b/benchmark/bm_app_erb.rb
@@ -1,26 +1,26 @@
-#
-# Create many HTML strings with ERB.
-#
-
-require 'erb'
-
-data = DATA.read
-max = 5_000
-title = "hello world!"
-content = "hello world!\n" * 10
-
-max.times{
- ERB.new(data).result(binding)
-}
-
-__END__
-
-<html>
- <head> <%= title %> </head>
- <body>
- <h1> <%= title %> </h1>
- <p>
- <%= content %>
- </p>
- </body>
-</html>
+#
+# Create many HTML strings with ERB.
+#
+
+require 'erb'
+
+data = DATA.read
+max = 5_000
+title = "hello world!"
+content = "hello world!\n" * 10
+
+max.times{
+ ERB.new(data).result(binding)
+}
+
+__END__
+
+<html>
+ <head> <%= title %> </head>
+ <body>
+ <h1> <%= title %> </h1>
+ <p>
+ <%= content %>
+ </p>
+ </body>
+</html>
diff --git a/benchmark/bm_app_uri.rb b/benchmark/bm_app_uri.rb
index 49fe5a8..586edfd 100644
--- a/benchmark/bm_app_uri.rb
+++ b/benchmark/bm_app_uri.rb
@@ -1,8 +1,8 @@
-require 'uri'
-
-100_000.times{
- uri = URI.parse('http://www.ruby-lang.org')
- uri.scheme
- uri.host
- uri.port
-}
+require 'uri'
+
+100_000.times{
+ uri = URI.parse('http://www.ruby-lang.org')
+ uri.scheme
+ uri.host
+ uri.port
+}
diff --git a/benchmark/bm_io_file_create.rb b/benchmark/bm_io_file_create.rb
index db4e4de..7adbe9e 100644
--- a/benchmark/bm_io_file_create.rb
+++ b/benchmark/bm_io_file_create.rb
@@ -1,13 +1,13 @@
-#
-# Create files
-#
-
-max = 50_000
-file = './tmpfile_of_bm_io_file_create'
-
-max.times{
- f = open(file, 'w')
- f.close#(true)
-}
-File.unlink(file)
-
+#
+# Create files
+#
+
+max = 50_000
+file = './tmpfile_of_bm_io_file_create'
+
+max.times{
+ f = open(file, 'w')
+ f.close#(true)
+}
+File.unlink(file)
+
diff --git a/benchmark/bm_io_file_read.rb b/benchmark/bm_io_file_read.rb
index 488a4e9..2b4212d 100644
--- a/benchmark/bm_io_file_read.rb
+++ b/benchmark/bm_io_file_read.rb
@@ -1,15 +1,15 @@
-#
-# Seek and Read file.
-#
-
-require 'tempfile'
-
-max = 20_000
-str = "Hello world! " * 1000
-f = Tempfile.new('yarv-benchmark')
-f.write str
-
-max.times{
- f.seek 0
- f.read
-}
+#
+# Seek and Read file.
+#
+
+require 'tempfile'
+
+max = 20_000
+str = "Hello world! " * 1000
+f = Tempfile.new('yarv-benchmark')
+f.write str
+
+max.times{
+ f.seek 0
+ f.read
+}
diff --git a/benchmark/bm_io_file_write.rb b/benchmark/bm_io_file_write.rb
index 05c7e7e..3cec58c 100644
--- a/benchmark/bm_io_file_write.rb
+++ b/benchmark/bm_io_file_write.rb
@@ -1,14 +1,14 @@
-#
-# Seek and Write file.
-#
-
-require 'tempfile'
-
-max = 20_000
-str = "Hello world! " * 1000
-f = Tempfile.new('yarv-benchmark')
-
-max.times{
- f.seek 0
- f.write str
-}
+#
+# Seek and Write file.
+#
+
+require 'tempfile'
+
+max = 20_000
+str = "Hello world! " * 1000
+f = Tempfile.new('yarv-benchmark')
+
+max.times{
+ f.seek 0
+ f.write str
+}
diff --git a/benchmark/bm_so_binary_trees.rb b/benchmark/bm_so_binary_trees.rb
index 138c529..6a26465 100644
--- a/benchmark/bm_so_binary_trees.rb
+++ b/benchmark/bm_so_binary_trees.rb
@@ -1,57 +1,57 @@
-# The Computer Language Shootout Benchmarks
-# http://shootout.alioth.debian.org
-#
-# contributed by Jesse Millikan
-
-# disable output
-def STDOUT.write_ *args
-end
-
-def item_check(tree)
- if tree[0] == nil
- tree[1]
- else
- tree[1] + item_check(tree[0]) - item_check(tree[2])
- end
-end
-
-def bottom_up_tree(item, depth)
- if depth > 0
- item_item = 2 * item
- depth -= 1
- [bottom_up_tree(item_item - 1, depth), item, bottom_up_tree(item_item, depth)]
- else
- [nil, item, nil]
- end
-end
-
-max_depth = 12 # 16 # ARGV[0].to_i
-min_depth = 4
-
-max_depth = min_depth + 2 if min_depth + 2 > max_depth
-
-stretch_depth = max_depth + 1
-stretch_tree = bottom_up_tree(0, stretch_depth)
-
-puts "stretch tree of depth #{stretch_depth}\t check: #{item_check(stretch_tree)}"
-stretch_tree = nil
-
-long_lived_tree = bottom_up_tree(0, max_depth)
-
-min_depth.step(max_depth + 1, 2) do |depth|
- iterations = 2**(max_depth - depth + min_depth)
-
- check = 0
-
- for i in 1..iterations
- temp_tree = bottom_up_tree(i, depth)
- check += item_check(temp_tree)
-
- temp_tree = bottom_up_tree(-i, depth)
- check += item_check(temp_tree)
- end
-
- puts "#{iterations * 2}\t trees of depth #{depth}\t check: #{check}"
-end
-
-puts "long lived tree of depth #{max_depth}\t check: #{item_check(long_lived_tree)}"
+# The Computer Language Shootout Benchmarks
+# http://shootout.alioth.debian.org
+#
+# contributed by Jesse Millikan
+
+# disable output
+def STDOUT.write_ *args
+end
+
+def item_check(tree)
+ if tree[0] == nil
+ tree[1]
+ else
+ tree[1] + item_check(tree[0]) - item_check(tree[2])
+ end
+end
+
+def bottom_up_tree(item, depth)
+ if depth > 0
+ item_item = 2 * item
+ depth -= 1
+ [bottom_up_tree(item_item - 1, depth), item, bottom_up_tree(item_item, depth)]
+ else
+ [nil, item, nil]
+ end
+end
+
+max_depth = 12 # 16 # ARGV[0].to_i
+min_depth = 4
+
+max_depth = min_depth + 2 if min_depth + 2 > max_depth
+
+stretch_depth = max_depth + 1
+stretch_tree = bottom_up_tree(0, stretch_depth)
+
+puts "stretch tree of depth #{stretch_depth}\t check: #{item_check(stretch_tree)}"
+stretch_tree = nil
+
+long_lived_tree = bottom_up_tree(0, max_depth)
+
+min_depth.step(max_depth + 1, 2) do |depth|
+ iterations = 2**(max_depth - depth + min_depth)
+
+ check = 0
+
+ for i in 1..iterations
+ temp_tree = bottom_up_tree(i, depth)
+ check += item_check(temp_tree)
+
+ temp_tree = bottom_up_tree(-i, depth)
+ check += item_check(temp_tree)
+ end
+
+ puts "#{iterations * 2}\t trees of depth #{depth}\t check: #{check}"
+end
+
+puts "long lived tree of depth #{max_depth}\t check: #{item_check(long_lived_tree)}"
diff --git a/benchmark/bm_so_fannkuch.rb b/benchmark/bm_so_fannkuch.rb
index 23298a8..a214f2e 100644
--- a/benchmark/bm_so_fannkuch.rb
+++ b/benchmark/bm_so_fannkuch.rb
@@ -1,45 +1,45 @@
-# The Computer Language Shootout
-# http://shootout.alioth.debian.org/
-# Contributed by Sokolov Yura
-# Modified by Ryan Williams
-
-def fannkuch(n)
- maxFlips, m, r, check = 0, n-1, n, 0
- count = (1..n).to_a
- perm = (1..n).to_a
-
- while true
- if check < 30
- puts "#{perm}"
- check += 1
- end
-
- while r != 1
- count[r-1] = r
- r -= 1
- end
-
- if perm[0] != 1 and perm[m] != n
- perml = perm.clone #.dup
- flips = 0
- while (k = perml.first ) != 1
- perml = perml.slice!(0, k).reverse + perml
- flips += 1
- end
- maxFlips = flips if flips > maxFlips
- end
- while true
- if r==n then return maxFlips end
- perm.insert r,perm.shift
- break if (count[r] -= 1) > 0
- r += 1
- end
- end
-end
-
-def puts *args
-end
-
-N = 10 # (ARGV[0] || 1).to_i
-puts "Pfannkuchen(#{N}) = #{fannkuch(N)}"
-
+# The Computer Language Shootout
+# http://shootout.alioth.debian.org/
+# Contributed by Sokolov Yura
+# Modified by Ryan Williams
+
+def fannkuch(n)
+ maxFlips, m, r, check = 0, n-1, n, 0
+ count = (1..n).to_a
+ perm = (1..n).to_a
+
+ while true
+ if check < 30
+ puts "#{perm}"
+ check += 1
+ end
+
+ while r != 1
+ count[r-1] = r
+ r -= 1
+ end
+
+ if perm[0] != 1 and perm[m] != n
+ perml = perm.clone #.dup
+ flips = 0
+ while (k = perml.first ) != 1
+ perml = perml.slice!(0, k).reverse + perml
+ flips += 1
+ end
+ maxFlips = flips if flips > maxFlips
+ end
+ while true
+ if r==n then return maxFlips end
+ perm.insert r,perm.shift
+ break if (count[r] -= 1) > 0
+ r += 1
+ end
+ end
+end
+
+def puts *args
+end
+
+N = 10 # (ARGV[0] || 1).to_i
+puts "Pfannkuchen(#{N}) = #{fannkuch(N)}"
+
diff --git a/benchmark/bm_so_fasta.rb b/benchmark/bm_so_fasta.rb
index b95f5e9..3f759ba 100644
--- a/benchmark/bm_so_fasta.rb
+++ b/benchmark/bm_so_fasta.rb
@@ -1,81 +1,81 @@
-# The Computer Language Shootout
-# http://shootout.alioth.debian.org/
-# Contributed by Sokolov Yura
-
-$last = 42.0
-def gen_random (max,im=139968,ia=3877,ic=29573)
- (max * ($last = ($last * ia + ic) % im)) / im
-end
-
-alu =
- "GGCCGGGCGCGGTGGCTCACGCCTGTAATCCCAGCACTTTGG"+
- "GAGGCCGAGGCGGGCGGATCACCTGAGGTCAGGAGTTCGAGA"+
- "CCAGCCTGGCCAACATGGTGAAACCCCGTCTCTACTAAAAAT"+
- "ACAAAAATTAGCCGGGCGTGGTGGCGCGCGCCTGTAATCCCA"+
- "GCTACTCGGGAGGCTGAGGCAGGAGAATCGCTTGAACCCGGG"+
- "AGGCGGAGGTTGCAGTGAGCCGAGATCGCGCCACTGCACTCC"+
- "AGCCTGGGCGACAGAGCGAGACTCCGTCTCAAAAA"
-
-iub = [
- ["a", 0.27],
- ["c", 0.12],
- ["g", 0.12],
- ["t", 0.27],
-
- ["B", 0.02],
- ["D", 0.02],
- ["H", 0.02],
- ["K", 0.02],
- ["M", 0.02],
- ["N", 0.02],
- ["R", 0.02],
- ["S", 0.02],
- ["V", 0.02],
- ["W", 0.02],
- ["Y", 0.02],
-]
-homosapiens = [
- ["a", 0.3029549426680],
- ["c", 0.1979883004921],
- ["g", 0.1975473066391],
- ["t", 0.3015094502008],
-]
-
-def make_repeat_fasta(id, desc, src, n)
- puts ">#{id} #{desc}"
- v = nil
- width = 60
- l = src.length
- s = src * ((n / l) + 1)
- s.slice!(n, l)
- puts(s.scan(/.{1,#{width}}/).join("\n"))
-end
-
-def make_random_fasta(id, desc, table, n)
- puts ">#{id} #{desc}"
- rand, v = nil,nil
- width = 60
- chunk = 1 * width
- prob = 0.0
- table.each{|v| v[1]= (prob += v[1])}
- for i in 1..(n/width)
- puts((1..width).collect{
- rand = gen_random(1.0)
- table.find{|v| v[1]>rand}[0]
- }.join)
- end
- if n%width != 0
- puts((1..(n%width)).collect{
- rand = gen_random(1.0)
- table.find{|v| v[1]>rand}[0]
- }.join)
- end
-end
-
-
-n = (ARGV[0] or 250_000).to_i
-
-make_repeat_fasta('ONE', 'Homo sapiens alu', alu, n*2)
-make_random_fasta('TWO', 'IUB ambiguity codes', iub, n*3)
-make_random_fasta('THREE', 'Homo sapiens frequency', homosapiens, n*5)
-
+# The Computer Language Shootout
+# http://shootout.alioth.debian.org/
+# Contributed by Sokolov Yura
+
+$last = 42.0
+def gen_random (max,im=139968,ia=3877,ic=29573)
+ (max * ($last = ($last * ia + ic) % im)) / im
+end
+
+alu =
+ "GGCCGGGCGCGGTGGCTCACGCCTGTAATCCCAGCACTTTGG"+
+ "GAGGCCGAGGCGGGCGGATCACCTGAGGTCAGGAGTTCGAGA"+
+ "CCAGCCTGGCCAACATGGTGAAACCCCGTCTCTACTAAAAAT"+
+ "ACAAAAATTAGCCGGGCGTGGTGGCGCGCGCCTGTAATCCCA"+
+ "GCTACTCGGGAGGCTGAGGCAGGAGAATCGCTTGAACCCGGG"+
+ "AGGCGGAGGTTGCAGTGAGCCGAGATCGCGCCACTGCACTCC"+
+ "AGCCTGGGCGACAGAGCGAGACTCCGTCTCAAAAA"
+
+iub = [
+ ["a", 0.27],
+ ["c", 0.12],
+ ["g", 0.12],
+ ["t", 0.27],
+
+ ["B", 0.02],
+ ["D", 0.02],
+ ["H", 0.02],
+ ["K", 0.02],
+ ["M", 0.02],
+ ["N", 0.02],
+ ["R", 0.02],
+ ["S", 0.02],
+ ["V", 0.02],
+ ["W", 0.02],
+ ["Y", 0.02],
+]
+homosapiens = [
+ ["a", 0.3029549426680],
+ ["c", 0.1979883004921],
+ ["g", 0.1975473066391],
+ ["t", 0.3015094502008],
+]
+
+def make_repeat_fasta(id, desc, src, n)
+ puts ">#{id} #{desc}"
+ v = nil
+ width = 60
+ l = src.length
+ s = src * ((n / l) + 1)
+ s.slice!(n, l)
+ puts(s.scan(/.{1,#{width}}/).join("\n"))
+end
+
+def make_random_fasta(id, desc, table, n)
+ puts ">#{id} #{desc}"
+ rand, v = nil,nil
+ width = 60
+ chunk = 1 * width
+ prob = 0.0
+ table.each{|v| v[1]= (prob += v[1])}
+ for i in 1..(n/width)
+ puts((1..width).collect{
+ rand = gen_random(1.0)
+ table.find{|v| v[1]>rand}[0]
+ }.join)
+ end
+ if n%width != 0
+ puts((1..(n%width)).collect{
+ rand = gen_random(1.0)
+ table.find{|v| v[1]>rand}[0]
+ }.join)
+ end
+end
+
+
+n = (ARGV[0] or 250_000).to_i
+
+make_repeat_fasta('ONE', 'Homo sapiens alu', alu, n*2)
+make_random_fasta('TWO', 'IUB ambiguity codes', iub, n*3)
+make_random_fasta('THREE', 'Homo sapiens frequency', homosapiens, n*5)
+
diff --git a/benchmark/bm_so_k_nucleotide.rb b/benchmark/bm_so_k_nucleotide.rb
index c0a5ba5..dadab3e 100644
--- a/benchmark/bm_so_k_nucleotide.rb
+++ b/benchmark/bm_so_k_nucleotide.rb
@@ -1,48 +1,48 @@
-# The Computer Language Shootout
-# http://shootout.alioth.debian.org
-#
-# contributed by jose fco. gonzalez
-# modified by Sokolov Yura
-
-seq = String.new
-
-def frecuency( seq,length )
- n, table = seq.length - length + 1, Hash.new(0)
- f, i = nil, nil
- (0 ... length).each do |f|
- (f ... n).step(length) do |i|
- table[seq[i,length]] += 1
- end
- end
- [n,table]
-
-end
-
-def sort_by_freq( seq,length )
- n,table = frecuency( seq,length )
- a, b, v = nil, nil, nil
- table.sort{|a,b| b[1] <=> a[1]}.each do |v|
- puts "%s %.3f" % [v[0].upcase,((v[1]*100).to_f/n)]
- end
- puts
-end
-
-def find_seq( seq,s )
- n,table = frecuency( seq,s.length )
- puts "#{table[s].to_s}\t#{s.upcase}"
-end
-
-input = open(File.join(File.dirname($0), 'fasta.output.100000'), 'rb')
-
-line = input.gets while line !~ /^>THREE/
-line = input.gets
-
-while (line !~ /^>/) & line do
- seq << line.chomp
- line = input.gets
-end
-
-[1,2].each {|i| sort_by_freq( seq,i ) }
-
-%w(ggt ggta ggtatt ggtattttaatt ggtattttaatttatagt).each{|s| find_seq( seq,s) }
-
+# The Computer Language Shootout
+# http://shootout.alioth.debian.org
+#
+# contributed by jose fco. gonzalez
+# modified by Sokolov Yura
+
+seq = String.new
+
+def frecuency( seq,length )
+ n, table = seq.length - length + 1, Hash.new(0)
+ f, i = nil, nil
+ (0 ... length).each do |f|
+ (f ... n).step(length) do |i|
+ table[seq[i,length]] += 1
+ end
+ end
+ [n,table]
+
+end
+
+def sort_by_freq( seq,length )
+ n,table = frecuency( seq,length )
+ a, b, v = nil, nil, nil
+ table.sort{|a,b| b[1] <=> a[1]}.each do |v|
+ puts "%s %.3f" % [v[0].upcase,((v[1]*100).to_f/n)]
+ end
+ puts
+end
+
+def find_seq( seq,s )
+ n,table = frecuency( seq,s.length )
+ puts "#{table[s].to_s}\t#{s.upcase}"
+end
+
+input = open(File.join(File.dirname($0), 'fasta.output.100000'), 'rb')
+
+line = input.gets while line !~ /^>THREE/
+line = input.gets
+
+while (line !~ /^>/) & line do
+ seq << line.chomp
+ line = input.gets
+end
+
+[1,2].each {|i| sort_by_freq( seq,i ) }
+
+%w(ggt ggta ggtatt ggtattttaatt ggtattttaatttatagt).each{|s| find_seq( seq,s) }
+
diff --git a/benchmark/bm_so_mandelbrot.rb b/benchmark/bm_so_mandelbrot.rb
index 2c05878..76331c6 100644
--- a/benchmark/bm_so_mandelbrot.rb
+++ b/benchmark/bm_so_mandelbrot.rb
@@ -1,57 +1,57 @@
-# The Computer Language Benchmarks Game
-# http://shootout.alioth.debian.org/
-#
-# contributed by Karl von Laudermann
-# modified by Jeremy Echols
-
-size = 600 # ARGV[0].to_i
-
-puts "P4\n#{size} #{size}"
-
-ITER = 49 # Iterations - 1 for easy for..in looping
-LIMIT_SQUARED = 4.0 # Presquared limit
-
-byte_acc = 0
-bit_num = 0
-
-count_size = size - 1 # Precomputed size for easy for..in looping
-
-# For..in loops are faster than .upto, .downto, .times, etc.
-for y in 0..count_size
- for x in 0..count_size
- zr = 0.0
- zi = 0.0
- cr = (2.0*x/size)-1.5
- ci = (2.0*y/size)-1.0
- escape = false
-
- # To make use of the for..in code, we use a dummy variable,
- # like one would in C
- for dummy in 0..ITER
- tr = zr*zr - zi*zi + cr
- ti = 2*zr*zi + ci
- zr, zi = tr, ti
-
- if (zr*zr+zi*zi) > LIMIT_SQUARED
- escape = true
- break
- end
- end
-
- byte_acc = (byte_acc << 1) | (escape ? 0b0 : 0b1)
- bit_num += 1
-
- # Code is very similar for these cases, but using separate blocks
- # ensures we skip the shifting when it's unnecessary, which is most cases.
- if (bit_num == 8)
- print byte_acc.chr
- byte_acc = 0
- bit_num = 0
- elsif (x == count_size)
- byte_acc <<= (8 - bit_num)
- print byte_acc.chr
- byte_acc = 0
- bit_num = 0
- end
- end
-end
+# The Computer Language Benchmarks Game
+# http://shootout.alioth.debian.org/
+#
+# contributed by Karl von Laudermann
+# modified by Jeremy Echols
+
+size = 600 # ARGV[0].to_i
+
+puts "P4\n#{size} #{size}"
+
+ITER = 49 # Iterations - 1 for easy for..in looping
+LIMIT_SQUARED = 4.0 # Presquared limit
+
+byte_acc = 0
+bit_num = 0
+
+count_size = size - 1 # Precomputed size for easy for..in looping
+
+# For..in loops are faster than .upto, .downto, .times, etc.
+for y in 0..count_size
+ for x in 0..count_size
+ zr = 0.0
+ zi = 0.0
+ cr = (2.0*x/size)-1.5
+ ci = (2.0*y/size)-1.0
+ escape = false
+
+ # To make use of the for..in code, we use a dummy variable,
+ # like one would in C
+ for dummy in 0..ITER
+ tr = zr*zr - zi*zi + cr
+ ti = 2*zr*zi + ci
+ zr, zi = tr, ti
+
+ if (zr*zr+zi*zi) > LIMIT_SQUARED
+ escape = true
+ break
+ end
+ end
+
+ byte_acc = (byte_acc << 1) | (escape ? 0b0 : 0b1)
+ bit_num += 1
+
+ # Code is very similar for these cases, but using separate blocks
+ # ensures we skip the shifting when it's unnecessary, which is most cases.
+ if (bit_num == 8)
+ print byte_acc.chr
+ byte_acc = 0
+ bit_num = 0
+ elsif (x == count_size)
+ byte_acc <<= (8 - bit_num)
+ print byte_acc.chr
+ byte_acc = 0
+ bit_num = 0
+ end
+ end
+end
diff --git a/benchmark/bm_so_meteor_contest.rb b/benchmark/bm_so_meteor_contest.rb
index 5dd720c..30b9971 100644
--- a/benchmark/bm_so_meteor_contest.rb
+++ b/benchmark/bm_so_meteor_contest.rb
@@ -1,564 +1,564 @@
-#!/usr/bin/env ruby
-#
-# The Computer Language Shootout
-# http://shootout.alioth.debian.org
-# contributed by Kevin Barnes (Ruby novice)
-
-# PROGRAM: the main body is at the bottom.
-# 1) read about the problem here: http://www-128.ibm.com/developerworks/java/library/j-javaopt/
-# 2) see how I represent a board as a bitmask by reading the blank_board comments
-# 3) read as your mental paths take you
-
-def print *args
-end
-
-# class to represent all information about a particular rotation of a particular piece
-class Rotation
- # an array (by location) containing a bit mask for how the piece maps at the given location.
- # if the rotation is illegal at that location the mask will contain false
- attr_reader :start_masks
-
- # maps a direction to a relative location. these differ depending on whether it is an even or
- # odd row being mapped from
- @@rotation_even_adder = { :west => -1, :east => 1, :nw => -7, :ne => -6, :sw => 5, :se => 6 }
- @@rotation_odd_adder = { :west => -1, :east => 1, :nw => -6, :ne => -5, :sw => 6, :se => 7 }
-
- def initialize( directions )
- @even_offsets, @odd_offsets = normalize_offsets( get_values( directions ))
-
- @even_mask = mask_for_offsets( @even_offsets)
- @odd_mask = mask_for_offsets( @odd_offsets)
-
- @start_masks = Array.new(60)
-
- # create the rotational masks by placing the base mask at the location and seeing if
- # 1) it overlaps the boundries and 2) it produces a prunable board. if either of these
- # is true the piece cannot be placed
- 0.upto(59) do | offset |
- mask = is_even(offset) ? (@even_mask << offset) : (@odd_mask << offset)
- if (blank_board & mask == 0 && !prunable(blank_board | mask, 0, true)) then
- imask = compute_required( mask, offset)
- @start_masks[offset] = [ mask, imask, imask | mask ]
- else
- @start_masks[offset] = false
- end
- end
- end
-
- def compute_required( mask, offset )
- board = blank_board
- 0.upto(offset) { | i | board |= 1 << i }
- board |= mask
- return 0 if (!prunable(board | mask, offset))
- board = flood_fill(board,58)
- count = 0
- imask = 0
- 0.upto(59) do | i |
- if (board[i] == 0) then
- imask |= (1 << i)
- count += 1
- end
- end
- (count > 0 && count < 5) ? imask : 0
- end
-
- def flood_fill( board, location)
- return board if (board[location] == 1)
- board |= 1 << location
- row, col = location.divmod(6)
- board = flood_fill( board, location - 1) if (col > 0)
- board = flood_fill( board, location + 1) if (col < 4)
- if (row % 2 == 0) then
- board = flood_fill( board, location - 7) if (col > 0 && row > 0)
- board = flood_fill( board, location - 6) if (row > 0)
- board = flood_fill( board, location + 6) if (row < 9)
- board = flood_fill( board, location + 5) if (col > 0 && row < 9)
- else
- board = flood_fill( board, location - 5) if (col < 4 && row > 0)
- board = flood_fill( board, location - 6) if (row > 0)
- board = flood_fill( board, location + 6) if (row < 9)
- board = flood_fill( board, location + 7) if (col < 4 && row < 9)
- end
- board
- end
-
- # given a location, produces a list of relative locations covered by the piece at this rotation
- def offsets( location)
- if is_even( location) then
- @even_offsets.collect { | value | value + location }
- else
- @odd_offsets.collect { | value | value + location }
- end
- end
-
- # returns a set of offsets relative to the top-left most piece of the rotation (by even or odd rows)
- # this is hard to explain. imagine we have this partial board:
- # 0 0 0 0 0 x [positions 0-5]
- # 0 0 1 1 0 x [positions 6-11]
- # 0 0 1 0 0 x [positions 12-17]
- # 0 1 0 0 0 x [positions 18-23]
- # 0 1 0 0 0 x [positions 24-29]
- # 0 0 0 0 0 x [positions 30-35]
- # ...
- # The top-left of the piece is at position 8, the
- # board would be passed as a set of positions (values array) containing [8,9,14,19,25] not necessarily in that
- # sorted order. Since that array starts on an odd row, the offsets for an odd row are: [0,1,6,11,17] obtained
- # by subtracting 8 from everything. Now imagine the piece shifted up and to the right so it's on an even row:
- # 0 0 0 1 1 x [positions 0-5]
- # 0 0 1 0 0 x [positions 6-11]
- # 0 0 1 0 0 x [positions 12-17]
- # 0 1 0 0 0 x [positions 18-23]
- # 0 0 0 0 0 x [positions 24-29]
- # 0 0 0 0 0 x [positions 30-35]
- # ...
- # Now the positions are [3,4,8,14,19] which after subtracting the lowest value (3) gives [0,1,5,11,16] thus, the
- # offsets for this particular piece are (in even, odd order) [0,1,5,11,16],[0,1,6,11,17] which is what
- # this function would return
- def normalize_offsets( values)
- min = values.min
- even_min = is_even(min)
- other_min = even_min ? min + 6 : min + 7
- other_values = values.collect do | value |
- if is_even(value) then
- value + 6 - other_min
- else
- value + 7 - other_min
- end
- end
- values.collect! { | value | value - min }
-
- if even_min then
- [values, other_values]
- else
- [other_values, values]
- end
- end
-
- # produce a bitmask representation of an array of offset locations
- def mask_for_offsets( offsets )
- mask = 0
- offsets.each { | value | mask = mask + ( 1 << value ) }
- mask
- end
-
- # finds a "safe" position that a position as described by a list of directions can be placed
- # without falling off any edge of the board. the values returned a location to place the first piece
- # at so it will fit after making the described moves
- def start_adjust( directions )
- south = east = 0;
- directions.each do | direction |
- east += 1 if ( direction == :sw || direction == :nw || direction == :west )
- south += 1 if ( direction == :nw || direction == :ne )
- end
- south * 6 + east
- end
-
- # given a set of directions places the piece (as defined by a set of directions) on the board at
- # a location that will not take it off the edge
- def get_values ( directions )
- start = start_adjust(directions)
- values = [ start ]
- directions.each do | direction |
- if (start % 12 >= 6) then
- start += @@rotation_odd_adder[direction]
- else
- start += @@rotation_even_adder[direction]
- end
- values += [ start ]
- end
-
- # some moves take you back to an existing location, we'll strip duplicates
- values.uniq
- end
-end
-
-# describes a piece and caches information about its rotations to as to be efficient for iteration
-# ATTRIBUTES:
-# rotations -- all the rotations of the piece
-# type -- a numeic "name" of the piece
-# masks -- an array by location of all legal rotational masks (a n inner array) for that location
-# placed -- the mask that this piece was last placed at (not a location, but the actual mask used)
-class Piece
- attr_reader :rotations, :type, :masks
- attr_accessor :placed
-
- # transform hashes that change one direction into another when you either flip or rotate a set of directions
- @@flip_converter = { :west => :west, :east => :east, :nw => :sw, :ne => :se, :sw => :nw, :se => :ne }
- @@rotate_converter = { :west => :nw, :east => :se, :nw => :ne, :ne => :east, :sw => :west, :se => :sw }
-
- def initialize( directions, type )
- @type = type
- @rotations = Array.new();
- @map = {}
-
- generate_rotations( directions )
- directions.collect! { | value | @@flip_converter[value] }
- generate_rotations( directions )
-
- # creates the masks AND a map that returns [location, rotation] for any given mask
- # this is used when a board is found and we want to draw it, otherwise the map is unused
- @masks = Array.new();
- 0.upto(59) do | i |
- even = true
- @masks[i] = @rotations.collect do | rotation |
- mask = rotation.start_masks[i]
- @map[mask[0]] = [ i, rotation ] if (mask)
- mask || nil
- end
- @masks[i].compact!
- end
- end
-
- # rotates a set of directions through all six angles and adds a Rotation to the list for each one
- def generate_rotations( directions )
- 6.times do
- rotations.push( Rotation.new(directions))
- directions.collect! { | value | @@rotate_converter[value] }
- end
- end
-
- # given a board string, adds this piece to the board at whatever location/rotation
- # important: the outbound board string is 5 wide, the normal location notation is six wide (padded)
- def fill_string( board_string)
- location, rotation = @map[@placed]
- rotation.offsets(location).each do | offset |
- row, col = offset.divmod(6)
- board_string[ row*5 + col, 1 ] = @type.to_s
- end
- end
-end
-
-# a blank bit board having this form:
-#
-# 0 0 0 0 0 1
-# 0 0 0 0 0 1
-# 0 0 0 0 0 1
-# 0 0 0 0 0 1
-# 0 0 0 0 0 1
-# 0 0 0 0 0 1
-# 0 0 0 0 0 1
-# 0 0 0 0 0 1
-# 0 0 0 0 0 1
-# 0 0 0 0 0 1
-# 1 1 1 1 1 1
-#
-# where left lest significant bit is the top left and the most significant is the lower right
-# the actual board only consists of the 0 places, the 1 places are blockers to keep things from running
-# off the edges or bottom
-def blank_board
- 0b111111100000100000100000100000100000100000100000100000100000100000
-end
-
-def full_board
- 0b111111111111111111111111111111111111111111111111111111111111111111
-end
-
-# determines if a location (bit position) is in an even row
-def is_even( location)
- (location % 12) < 6
-end
-
-# support function that create three utility maps:
-# $converter -- for each row an array that maps a five bit row (via array mapping)
-# to the a a five bit representation of the bits below it
-# $bit_count -- maps a five bit row (via array mapping) to the number of 1s in the row
-# @@new_regions -- maps a five bit row (via array mapping) to an array of "region" arrays
-# a region array has three values the first is a mask of bits in the region,
-# the second is the count of those bits and the third is identical to the first
-# examples:
-# 0b10010 => [ 0b01100, 2, 0b01100 ], [ 0b00001, 1, 0b00001]
-# 0b01010 => [ 0b10000, 1, 0b10000 ], [ 0b00100, 1, 0b00100 ], [ 0b00001, 1, 0b00001]
-# 0b10001 => [ 0b01110, 3, 0b01110 ]
-def create_collector_support
- odd_map = [0b11, 0b110, 0b1100, 0b11000, 0b10000]
- even_map = [0b1, 0b11, 0b110, 0b1100, 0b11000]
-
- all_odds = Array.new(0b100000)
- all_evens = Array.new(0b100000)
- bit_counts = Array.new(0b100000)
- new_regions = Array.new(0b100000)
- 0.upto(0b11111) do | i |
- bit_count = odd = even = 0
- 0.upto(4) do | bit |
- if (i[bit] == 1) then
- bit_count += 1
- odd |= odd_map[bit]
- even |= even_map[bit]
- end
- end
- all_odds[i] = odd
- all_evens[i] = even
- bit_counts[i] = bit_count
- new_regions[i] = create_regions( i)
- end
-
- $converter = []
- 10.times { | row | $converter.push((row % 2 == 0) ? all_evens : all_odds) }
- $bit_counts = bit_counts
- $regions = new_regions.collect { | set | set.collect { | value | [ value, bit_counts[value], value] } }
-end
-
-# determines if a board is punable, meaning that there is no possibility that it
-# can be filled up with pieces. A board is prunable if there is a grouping of unfilled spaces
-# that are not a multiple of five. The following board is an example of a prunable board:
-# 0 0 1 0 0
-# 0 1 0 0 0
-# 1 1 0 0 0
-# 0 1 0 0 0
-# 0 0 0 0 0
-# ...
-#
-# This board is prunable because the top left corner is only 3 bits in area, no piece will ever fit it
-# parameters:
-# board -- an initial bit board (6 bit padded rows, see blank_board for format)
-# location -- starting location, everything above and to the left is already full
-# slotting -- set to true only when testing initial pieces, when filling normally
-# additional assumptions are possible
-#
-# Algorithm:
-# The algorithm starts at the top row (as determined by location) and iterates a row at a time
-# maintainng counts of active open areas (kept in the collector array) each collector contains
-# three values at the start of an iteration:
-# 0: mask of bits that would be adjacent to the collector in this row
-# 1: the number of bits collected so far
-# 2: a scratch space starting as zero, but used during the computation to represent
-# the empty bits in the new row that are adjacent (position 0)
-# The exact procedure is described in-code
-def prunable( board, location, slotting = false)
- collectors = []
- # loop accross the rows
- (location / 6).to_i.upto(9) do | row_on |
- # obtain a set of regions representing the bits of the curent row.
- regions = $regions[(board >> (row_on * 6)) & 0b11111]
- converter = $converter[row_on]
-
- # track the number of collectors at the start of the cycle so that
- # we don't compute against newly created collectors, only existing collectors
- initial_collector_count = collectors.length
-
- # loop against the regions. For each region of the row
- # we will see if it connects to one or more existing collectors.
- # if it connects to 1 collector, the bits from the region are added to the
- # bits of the collector and the mask is placed in collector[2]
- # If the region overlaps more than one collector then all the collectors
- # it overlaps with are merged into the first one (the others are set to nil in the array)
- # if NO collectors are found then the region is copied as a new collector
- regions.each do | region |
- collector_found = nil
- region_mask = region[2]
- initial_collector_count.times do | collector_num |
- collector = collectors[collector_num]
- if (collector) then
- collector_mask = collector[0]
- if (collector_mask & region_mask != 0) then
- if (collector_found) then
- collector_found[0] |= collector_mask
- collector_found[1] += collector[1]
- collector_found[2] |= collector[2]
- collectors[collector_num] = nil
- else
- collector_found = collector
- collector[1] += region[1]
- collector[2] |= region_mask
- end
- end
- end
- end
- if (collector_found == nil) then
- collectors.push(Array.new(region))
- end
- end
-
- # check the existing collectors, if any collector overlapped no bits in the region its [2] value will
- # be zero. The size of any such reaason is tested if it is not a muliple of five true is returned since
- # the board is prunable. if it is a multiple of five it is removed.
- # Collector that are still active have a new adjacent value [0] set based n the matched bits
- # and have [2] cleared out for the next cycle.
- collectors.length.times do | collector_num |
- collector = collectors[collector_num]
- if (collector) then
- if (collector[2] == 0) then
- return true if (collector[1] % 5 != 0)
- collectors[collector_num] = nil
- else
- # if a collector matches all bits in the row then we can return unprunable early for the
- # follwing reasons:
- # 1) there can be no more unavailable bits bince we fill from the top left downward
- # 2) all previous regions have been closed or joined so only this region can fail
- # 3) this region must be good since there can never be only 1 region that is nuot
- # a multiple of five
- # this rule only applies when filling normally, so we ignore the rule if we are "slotting"
- # in pieces to see what configurations work for them (the only other time this algorithm is used).
- return false if (collector[2] == 0b11111 && !slotting)
- collector[0] = converter[collector[2]]
- collector[2] = 0
- end
- end
- end
-
- # get rid of all the empty converters for the next round
- collectors.compact!
- end
- return false if (collectors.length <= 1) # 1 collector or less and the region is fine
- collectors.any? { | collector | (collector[1] % 5) != 0 } # more than 1 and we test them all for bad size
-end
-
-# creates a region given a row mask. see prunable for what a "region" is
-def create_regions( value )
- regions = []
- cur_region = 0
- 5.times do | bit |
- if (value[bit] == 0) then
- cur_region |= 1 << bit
- else
- if (cur_region != 0 ) then
- regions.push( cur_region)
- cur_region = 0;
- end
- end
- end
- regions.push(cur_region) if (cur_region != 0)
- regions
-end
-
-# find up to the counted number of solutions (or all solutions) and prints the final result
-def find_all
- find_top( 1)
- find_top( 0)
- print_results
-end
-
-# show the board
-def print_results
- print "#{@boards_found} solutions found\n\n"
- print_full_board( @min_board)
- print "\n"
- print_full_board( @max_board)
- print "\n"
-end
-
-# finds solutions. This special version of the main function is only used for the top level
-# the reason for it is basically to force a particular ordering on how the rotations are tested for
-# the first piece. It is called twice, first looking for placements of the odd rotations and then
-# looking for placements of the even locations.
-#
-# WHY?
-# Since any found solution has an inverse we want to maximize finding solutions that are not already found
-# as an inverse. The inverse will ALWAYS be 3 one of the piece configurations that is exactly 3 rotations away
-# (an odd number). Checking even vs odd then produces a higher probability of finding more pieces earlier
-# in the cycle. We still need to keep checking all the permutations, but our probability of finding one will
-# diminsh over time. Since we are TOLD how many to search for this lets us exit before checking all pieces
-# this bennifit is very great when seeking small numbers of solutions and is 0 when looking for more than the
-# maximum number
-def find_top( rotation_skip)
- board = blank_board
- (@pieces.length-1).times do
- piece = @pieces.shift
- piece.masks[0].each do | mask, imask, cmask |
- if ((rotation_skip += 1) % 2 == 0) then
- piece.placed = mask
- find( 1, 1, board | mask)
- end
- end
- @pieces.push(piece)
- end
- piece = @pieces.shift
- @pieces.push(piece)
-end
-
-# the normail find routine, iterates through the available pieces, checks all rotations at the current location
-# and adds any boards found. depth is acheived via recursion. the overall approach is described
-# here: http://www-128.ibm.com/developerworks/java/library/j-javaopt/
-# parameters:
-# start_location -- where to start looking for place for the next piece at
-# placed -- number of pieces placed
-# board -- current state of the board
-#
-# see in-code comments
-def find( start_location, placed, board)
- # find the next location to place a piece by looking for an empty bit
- while board[start_location] == 1
- start_location += 1
- end
-
- @pieces.length.times do
- piece = @pieces.shift
- piece.masks[start_location].each do | mask, imask, cmask |
- if ( board & cmask == imask) then
- piece.placed = mask
- if (placed == 9) then
- add_board
- else
- find( start_location + 1, placed + 1, board | mask)
- end
- end
- end
- @pieces.push(piece)
- end
-end
-
-# print the board
-def print_full_board( board_string)
- 10.times do | row |
- print " " if (row % 2 == 1)
- 5.times do | col |
- print "#{board_string[row*5 + col,1]} "
- end
- print "\n"
- end
-end
-
-# when a board is found we "draw it" into a string and then flip that string, adding both to
-# the list (hash) of solutions if they are unique.
-def add_board
- board_string = "99999999999999999999999999999999999999999999999999"
- @all_pieces.each { | piece | piece.fill_string( board_string ) }
- save( board_string)
- save( board_string.reverse)
-end
-
-# adds a board string to the list (if new) and updates the current best/worst board
-def save( board_string)
- if (@all_boards[board_string] == nil) then
- @min_board = board_string if (board_string < @min_board)
- @max_board = board_string if (board_string > @max_board)
- @all_boards.store(board_string,true)
- @boards_found += 1
-
- # the exit motif is a time saver. Ideally the function should return, but those tests
- # take noticable time (performance).
- if (@boards_found == @stop_count) then
- print_results
- exit(0)
- end
- end
-end
-
-
-##
-## MAIN BODY :)
-##
-create_collector_support
-@pieces = [
- Piece.new( [ :nw, :ne, :east, :east ], 2),
- Piece.new( [ :ne, :se, :east, :ne ], 7),
- Piece.new( [ :ne, :east, :ne, :nw ], 1),
- Piece.new( [ :east, :sw, :sw, :se ], 6),
- Piece.new( [ :east, :ne, :se, :ne ], 5),
- Piece.new( [ :east, :east, :east, :se ], 0),
- Piece.new( [ :ne, :nw, :se, :east, :se ], 4),
- Piece.new( [ :se, :se, :se, :west ], 9),
- Piece.new( [ :se, :se, :east, :se ], 8),
- Piece.new( [ :east, :east, :sw, :se ], 3)
- ];
-
-@all_pieces = Array.new( @pieces)
-
-@min_board = "99999999999999999999999999999999999999999999999999"
-@max_board = "00000000000000000000000000000000000000000000000000"
-@stop_count = ARGV[0].to_i || 2089
-@all_boards = {}
-@boards_found = 0
-
-find_all ######## DO IT!!!
-
+#!/usr/bin/env ruby
+#
+# The Computer Language Shootout
+# http://shootout.alioth.debian.org
+# contributed by Kevin Barnes (Ruby novice)
+
+# PROGRAM: the main body is at the bottom.
+# 1) read about the problem here: http://www-128.ibm.com/developerworks/java/library/j-javaopt/
+# 2) see how I represent a board as a bitmask by reading the blank_board comments
+# 3) read as your mental paths take you
+
+def print *args
+end
+
+# class to represent all information about a particular rotation of a particular piece
+class Rotation
+ # an array (by location) containing a bit mask for how the piece maps at the given location.
+ # if the rotation is illegal at that location the mask will contain false
+ attr_reader :start_masks
+
+ # maps a direction to a relative location. these differ depending on whether it is an even or
+ # odd row being mapped from
+ @@rotation_even_adder = { :west => -1, :east => 1, :nw => -7, :ne => -6, :sw => 5, :se => 6 }
+ @@rotation_odd_adder = { :west => -1, :east => 1, :nw => -6, :ne => -5, :sw => 6, :se => 7 }
+
+ def initialize( directions )
+ @even_offsets, @odd_offsets = normalize_offsets( get_values( directions ))
+
+ @even_mask = mask_for_offsets( @even_offsets)
+ @odd_mask = mask_for_offsets( @odd_offsets)
+
+ @start_masks = Array.new(60)
+
+ # create the rotational masks by placing the base mask at the location and seeing if
+ # 1) it overlaps the boundries and 2) it produces a prunable board. if either of these
+ # is true the piece cannot be placed
+ 0.upto(59) do | offset |
+ mask = is_even(offset) ? (@even_mask << offset) : (@odd_mask << offset)
+ if (blank_board & mask == 0 && !prunable(blank_board | mask, 0, true)) then
+ imask = compute_required( mask, offset)
+ @start_masks[offset] = [ mask, imask, imask | mask ]
+ else
+ @start_masks[offset] = false
+ end
+ end
+ end
+
+ def compute_required( mask, offset )
+ board = blank_board
+ 0.upto(offset) { | i | board |= 1 << i }
+ board |= mask
+ return 0 if (!prunable(board | mask, offset))
+ board = flood_fill(board,58)
+ count = 0
+ imask = 0
+ 0.upto(59) do | i |
+ if (board[i] == 0) then
+ imask |= (1 << i)
+ count += 1
+ end
+ end
+ (count > 0 && count < 5) ? imask : 0
+ end
+
+ def flood_fill( board, location)
+ return board if (board[location] == 1)
+ board |= 1 << location
+ row, col = location.divmod(6)
+ board = flood_fill( board, location - 1) if (col > 0)
+ board = flood_fill( board, location + 1) if (col < 4)
+ if (row % 2 == 0) then
+ board = flood_fill( board, location - 7) if (col > 0 && row > 0)
+ board = flood_fill( board, location - 6) if (row > 0)
+ board = flood_fill( board, location + 6) if (row < 9)
+ board = flood_fill( board, location + 5) if (col > 0 && row < 9)
+ else
+ board = flood_fill( board, location - 5) if (col < 4 && row > 0)
+ board = flood_fill( board, location - 6) if (row > 0)
+ board = flood_fill( board, location + 6) if (row < 9)
+ board = flood_fill( board, location + 7) if (col < 4 && row < 9)
+ end
+ board
+ end
+
+ # given a location, produces a list of relative locations covered by the piece at this rotation
+ def offsets( location)
+ if is_even( location) then
+ @even_offsets.collect { | value | value + location }
+ else
+ @odd_offsets.collect { | value | value + location }
+ end
+ end
+
+ # returns a set of offsets relative to the top-left most piece of the rotation (by even or odd rows)
+ # this is hard to explain. imagine we have this partial board:
+ # 0 0 0 0 0 x [positions 0-5]
+ # 0 0 1 1 0 x [positions 6-11]
+ # 0 0 1 0 0 x [positions 12-17]
+ # 0 1 0 0 0 x [positions 18-23]
+ # 0 1 0 0 0 x [positions 24-29]
+ # 0 0 0 0 0 x [positions 30-35]
+ # ...
+ # The top-left of the piece is at position 8, the
+ # board would be passed as a set of positions (values array) containing [8,9,14,19,25] not necessarily in that
+ # sorted order. Since that array starts on an odd row, the offsets for an odd row are: [0,1,6,11,17] obtained
+ # by subtracting 8 from everything. Now imagine the piece shifted up and to the right so it's on an even row:
+ # 0 0 0 1 1 x [positions 0-5]
+ # 0 0 1 0 0 x [positions 6-11]
+ # 0 0 1 0 0 x [positions 12-17]
+ # 0 1 0 0 0 x [positions 18-23]
+ # 0 0 0 0 0 x [positions 24-29]
+ # 0 0 0 0 0 x [positions 30-35]
+ # ...
+ # Now the positions are [3,4,8,14,19] which after subtracting the lowest value (3) gives [0,1,5,11,16] thus, the
+ # offsets for this particular piece are (in even, odd order) [0,1,5,11,16],[0,1,6,11,17] which is what
+ # this function would return
+ def normalize_offsets( values)
+ min = values.min
+ even_min = is_even(min)
+ other_min = even_min ? min + 6 : min + 7
+ other_values = values.collect do | value |
+ if is_even(value) then
+ value + 6 - other_min
+ else
+ value + 7 - other_min
+ end
+ end
+ values.collect! { | value | value - min }
+
+ if even_min then
+ [values, other_values]
+ else
+ [other_values, values]
+ end
+ end
+
+ # produce a bitmask representation of an array of offset locations
+ def mask_for_offsets( offsets )
+ mask = 0
+ offsets.each { | value | mask = mask + ( 1 << value ) }
+ mask
+ end
+
+ # finds a "safe" position that a position as described by a list of directions can be placed
+ # without falling off any edge of the board. the values returned a location to place the first piece
+ # at so it will fit after making the described moves
+ def start_adjust( directions )
+ south = east = 0;
+ directions.each do | direction |
+ east += 1 if ( direction == :sw || direction == :nw || direction == :west )
+ south += 1 if ( direction == :nw || direction == :ne )
+ end
+ south * 6 + east
+ end
+
+ # given a set of directions places the piece (as defined by a set of directions) on the board at
+ # a location that will not take it off the edge
+ def get_values ( directions )
+ start = start_adjust(directions)
+ values = [ start ]
+ directions.each do | direction |
+ if (start % 12 >= 6) then
+ start += @@rotation_odd_adder[direction]
+ else
+ start += @@rotation_even_adder[direction]
+ end
+ values += [ start ]
+ end
+
+ # some moves take you back to an existing location, we'll strip duplicates
+ values.uniq
+ end
+end
+
+# describes a piece and caches information about its rotations to as to be efficient for iteration
+# ATTRIBUTES:
+# rotations -- all the rotations of the piece
+# type -- a numeic "name" of the piece
+# masks -- an array by location of all legal rotational masks (a n inner array) for that location
+# placed -- the mask that this piece was last placed at (not a location, but the actual mask used)
+class Piece
+ attr_reader :rotations, :type, :masks
+ attr_accessor :placed
+
+ # transform hashes that change one direction into another when you either flip or rotate a set of directions
+ @@flip_converter = { :west => :west, :east => :east, :nw => :sw, :ne => :se, :sw => :nw, :se => :ne }
+ @@rotate_converter = { :west => :nw, :east => :se, :nw => :ne, :ne => :east, :sw => :west, :se => :sw }
+
+ def initialize( directions, type )
+ @type = type
+ @rotations = Array.new();
+ @map = {}
+
+ generate_rotations( directions )
+ directions.collect! { | value | @@flip_converter[value] }
+ generate_rotations( directions )
+
+ # creates the masks AND a map that returns [location, rotation] for any given mask
+ # this is used when a board is found and we want to draw it, otherwise the map is unused
+ @masks = Array.new();
+ 0.upto(59) do | i |
+ even = true
+ @masks[i] = @rotations.collect do | rotation |
+ mask = rotation.start_masks[i]
+ @map[mask[0]] = [ i, rotation ] if (mask)
+ mask || nil
+ end
+ @masks[i].compact!
+ end
+ end
+
+ # rotates a set of directions through all six angles and adds a Rotation to the list for each one
+ def generate_rotations( directions )
+ 6.times do
+ rotations.push( Rotation.new(directions))
+ directions.collect! { | value | @@rotate_converter[value] }
+ end
+ end
+
+ # given a board string, adds this piece to the board at whatever location/rotation
+ # important: the outbound board string is 5 wide, the normal location notation is six wide (padded)
+ def fill_string( board_string)
+ location, rotation = @map[@placed]
+ rotation.offsets(location).each do | offset |
+ row, col = offset.divmod(6)
+ board_string[ row*5 + col, 1 ] = @type.to_s
+ end
+ end
+end
+
+# a blank bit board having this form:
+#
+# 0 0 0 0 0 1
+# 0 0 0 0 0 1
+# 0 0 0 0 0 1
+# 0 0 0 0 0 1
+# 0 0 0 0 0 1
+# 0 0 0 0 0 1
+# 0 0 0 0 0 1
+# 0 0 0 0 0 1
+# 0 0 0 0 0 1
+# 0 0 0 0 0 1
+# 1 1 1 1 1 1
+#
+# where left lest significant bit is the top left and the most significant is the lower right
+# the actual board only consists of the 0 places, the 1 places are blockers to keep things from running
+# off the edges or bottom
+def blank_board
+ 0b111111100000100000100000100000100000100000100000100000100000100000
+end
+
+def full_board
+ 0b111111111111111111111111111111111111111111111111111111111111111111
+end
+
+# determines if a location (bit position) is in an even row
+def is_even( location)
+ (location % 12) < 6
+end
+
+# support function that create three utility maps:
+# $converter -- for each row an array that maps a five bit row (via array mapping)
+# to the a a five bit representation of the bits below it
+# $bit_count -- maps a five bit row (via array mapping) to the number of 1s in the row
+# @@new_regions -- maps a five bit row (via array mapping) to an array of "region" arrays
+# a region array has three values the first is a mask of bits in the region,
+# the second is the count of those bits and the third is identical to the first
+# examples:
+# 0b10010 => [ 0b01100, 2, 0b01100 ], [ 0b00001, 1, 0b00001]
+# 0b01010 => [ 0b10000, 1, 0b10000 ], [ 0b00100, 1, 0b00100 ], [ 0b00001, 1, 0b00001]
+# 0b10001 => [ 0b01110, 3, 0b01110 ]
+def create_collector_support
+ odd_map = [0b11, 0b110, 0b1100, 0b11000, 0b10000]
+ even_map = [0b1, 0b11, 0b110, 0b1100, 0b11000]
+
+ all_odds = Array.new(0b100000)
+ all_evens = Array.new(0b100000)
+ bit_counts = Array.new(0b100000)
+ new_regions = Array.new(0b100000)
+ 0.upto(0b11111) do | i |
+ bit_count = odd = even = 0
+ 0.upto(4) do | bit |
+ if (i[bit] == 1) then
+ bit_count += 1
+ odd |= odd_map[bit]
+ even |= even_map[bit]
+ end
+ end
+ all_odds[i] = odd
+ all_evens[i] = even
+ bit_counts[i] = bit_count
+ new_regions[i] = create_regions( i)
+ end
+
+ $converter = []
+ 10.times { | row | $converter.push((row % 2 == 0) ? all_evens : all_odds) }
+ $bit_counts = bit_counts
+ $regions = new_regions.collect { | set | set.collect { | value | [ value, bit_counts[value], value] } }
+end
+
+# determines if a board is punable, meaning that there is no possibility that it
+# can be filled up with pieces. A board is prunable if there is a grouping of unfilled spaces
+# that are not a multiple of five. The following board is an example of a prunable board:
+# 0 0 1 0 0
+# 0 1 0 0 0
+# 1 1 0 0 0
+# 0 1 0 0 0
+# 0 0 0 0 0
+# ...
+#
+# This board is prunable because the top left corner is only 3 bits in area, no piece will ever fit it
+# parameters:
+# board -- an initial bit board (6 bit padded rows, see blank_board for format)
+# location -- starting location, everything above and to the left is already full
+# slotting -- set to true only when testing initial pieces, when filling normally
+# additional assumptions are possible
+#
+# Algorithm:
+# The algorithm starts at the top row (as determined by location) and iterates a row at a time
+# maintainng counts of active open areas (kept in the collector array) each collector contains
+# three values at the start of an iteration:
+# 0: mask of bits that would be adjacent to the collector in this row
+# 1: the number of bits collected so far
+# 2: a scratch space starting as zero, but used during the computation to represent
+# the empty bits in the new row that are adjacent (position 0)
+# The exact procedure is described in-code
+def prunable( board, location, slotting = false)
+ collectors = []
+ # loop accross the rows
+ (location / 6).to_i.upto(9) do | row_on |
+ # obtain a set of regions representing the bits of the curent row.
+ regions = $regions[(board >> (row_on * 6)) & 0b11111]
+ converter = $converter[row_on]
+
+ # track the number of collectors at the start of the cycle so that
+ # we don't compute against newly created collectors, only existing collectors
+ initial_collector_count = collectors.length
+
+ # loop against the regions. For each region of the row
+ # we will see if it connects to one or more existing collectors.
+ # if it connects to 1 collector, the bits from the region are added to the
+ # bits of the collector and the mask is placed in collector[2]
+ # If the region overlaps more than one collector then all the collectors
+ # it overlaps with are merged into the first one (the others are set to nil in the array)
+ # if NO collectors are found then the region is copied as a new collector
+ regions.each do | region |
+ collector_found = nil
+ region_mask = region[2]
+ initial_collector_count.times do | collector_num |
+ collector = collectors[collector_num]
+ if (collector) then
+ collector_mask = collector[0]
+ if (collector_mask & region_mask != 0) then
+ if (collector_found) then
+ collector_found[0] |= collector_mask
+ collector_found[1] += collector[1]
+ collector_found[2] |= collector[2]
+ collectors[collector_num] = nil
+ else
+ collector_found = collector
+ collector[1] += region[1]
+ collector[2] |= region_mask
+ end
+ end
+ end
+ end
+ if (collector_found == nil) then
+ collectors.push(Array.new(region))
+ end
+ end
+
+ # check the existing collectors, if any collector overlapped no bits in the region its [2] value will
+ # be zero. The size of any such reaason is tested if it is not a muliple of five true is returned since
+ # the board is prunable. if it is a multiple of five it is removed.
+ # Collector that are still active have a new adjacent value [0] set based n the matched bits
+ # and have [2] cleared out for the next cycle.
+ collectors.length.times do | collector_num |
+ collector = collectors[collector_num]
+ if (collector) then
+ if (collector[2] == 0) then
+ return true if (collector[1] % 5 != 0)
+ collectors[collector_num] = nil
+ else
+ # if a collector matches all bits in the row then we can return unprunable early for the
+ # follwing reasons:
+ # 1) there can be no more unavailable bits bince we fill from the top left downward
+ # 2) all previous regions have been closed or joined so only this region can fail
+ # 3) this region must be good since there can never be only 1 region that is nuot
+ # a multiple of five
+ # this rule only applies when filling normally, so we ignore the rule if we are "slotting"
+ # in pieces to see what configurations work for them (the only other time this algorithm is used).
+ return false if (collector[2] == 0b11111 && !slotting)
+ collector[0] = converter[collector[2]]
+ collector[2] = 0
+ end
+ end
+ end
+
+ # get rid of all the empty converters for the next round
+ collectors.compact!
+ end
+ return false if (collectors.length <= 1) # 1 collector or less and the region is fine
+ collectors.any? { | collector | (collector[1] % 5) != 0 } # more than 1 and we test them all for bad size
+end
+
+# creates a region given a row mask. see prunable for what a "region" is
+def create_regions( value )
+ regions = []
+ cur_region = 0
+ 5.times do | bit |
+ if (value[bit] == 0) then
+ cur_region |= 1 << bit
+ else
+ if (cur_region != 0 ) then
+ regions.push( cur_region)
+ cur_region = 0;
+ end
+ end
+ end
+ regions.push(cur_region) if (cur_region != 0)
+ regions
+end
+
+# find up to the counted number of solutions (or all solutions) and prints the final result
+def find_all
+ find_top( 1)
+ find_top( 0)
+ print_results
+end
+
+# show the board
+def print_results
+ print "#{@boards_found} solutions found\n\n"
+ print_full_board( @min_board)
+ print "\n"
+ print_full_board( @max_board)
+ print "\n"
+end
+
+# finds solutions. This special version of the main function is only used for the top level
+# the reason for it is basically to force a particular ordering on how the rotations are tested for
+# the first piece. It is called twice, first looking for placements of the odd rotations and then
+# looking for placements of the even locations.
+#
+# WHY?
+# Since any found solution has an inverse we want to maximize finding solutions that are not already found
+# as an inverse. The inverse will ALWAYS be 3 one of the piece configurations that is exactly 3 rotations away
+# (an odd number). Checking even vs odd then produces a higher probability of finding more pieces earlier
+# in the cycle. We still need to keep checking all the permutations, but our probability of finding one will
+# diminsh over time. Since we are TOLD how many to search for this lets us exit before checking all pieces
+# this bennifit is very great when seeking small numbers of solutions and is 0 when looking for more than the
+# maximum number
+def find_top( rotation_skip)
+ board = blank_board
+ (@pieces.length-1).times do
+ piece = @pieces.shift
+ piece.masks[0].each do | mask, imask, cmask |
+ if ((rotation_skip += 1) % 2 == 0) then
+ piece.placed = mask
+ find( 1, 1, board | mask)
+ end
+ end
+ @pieces.push(piece)
+ end
+ piece = @pieces.shift
+ @pieces.push(piece)
+end
+
+# the normail find routine, iterates through the available pieces, checks all rotations at the current location
+# and adds any boards found. depth is acheived via recursion. the overall approach is described
+# here: http://www-128.ibm.com/developerworks/java/library/j-javaopt/
+# parameters:
+# start_location -- where to start looking for place for the next piece at
+# placed -- number of pieces placed
+# board -- current state of the board
+#
+# see in-code comments
+def find( start_location, placed, board)
+ # find the next location to place a piece by looking for an empty bit
+ while board[start_location] == 1
+ start_location += 1
+ end
+
+ @pieces.length.times do
+ piece = @pieces.shift
+ piece.masks[start_location].each do | mask, imask, cmask |
+ if ( board & cmask == imask) then
+ piece.placed = mask
+ if (placed == 9) then
+ add_board
+ else
+ find( start_location + 1, placed + 1, board | mask)
+ end
+ end
+ end
+ @pieces.push(piece)
+ end
+end
+
+# print the board
+def print_full_board( board_string)
+ 10.times do | row |
+ print " " if (row % 2 == 1)
+ 5.times do | col |
+ print "#{board_string[row*5 + col,1]} "
+ end
+ print "\n"
+ end
+end
+
+# when a board is found we "draw it" into a string and then flip that string, adding both to
+# the list (hash) of solutions if they are unique.
+def add_board
+ board_string = "99999999999999999999999999999999999999999999999999"
+ @all_pieces.each { | piece | piece.fill_string( board_string ) }
+ save( board_string)
+ save( board_string.reverse)
+end
+
+# adds a board string to the list (if new) and updates the current best/worst board
+def save( board_string)
+ if (@all_boards[board_string] == nil) then
+ @min_board = board_string if (board_string < @min_board)
+ @max_board = board_string if (board_string > @max_board)
+ @all_boards.store(board_string,true)
+ @boards_found += 1
+
+ # the exit motif is a time saver. Ideally the function should return, but those tests
+ # take noticable time (performance).
+ if (@boards_found == @stop_count) then
+ print_results
+ exit(0)
+ end
+ end
+end
+
+
+##
+## MAIN BODY :)
+##
+create_collector_support
+@pieces = [
+ Piece.new( [ :nw, :ne, :east, :east ], 2),
+ Piece.new( [ :ne, :se, :east, :ne ], 7),
+ Piece.new( [ :ne, :east, :ne, :nw ], 1),
+ Piece.new( [ :east, :sw, :sw, :se ], 6),
+ Piece.new( [ :east, :ne, :se, :ne ], 5),
+ Piece.new( [ :east, :east, :east, :se ], 0),
+ Piece.new( [ :ne, :nw, :se, :east, :se ], 4),
+ Piece.new( [ :se, :se, :se, :west ], 9),
+ Piece.new( [ :se, :se, :east, :se ], 8),
+ Piece.new( [ :east, :east, :sw, :se ], 3)
+ ];
+
+@all_pieces = Array.new( @pieces)
+
+@min_board = "99999999999999999999999999999999999999999999999999"
+@max_board = "00000000000000000000000000000000000000000000000000"
+@stop_count = ARGV[0].to_i || 2089
+@all_boards = {}
+@boards_found = 0
+
+find_all ######## DO IT!!!
+
diff --git a/benchmark/bm_so_nbody.rb b/benchmark/bm_so_nbody.rb
index 709d58b..d6c5bb9 100644
--- a/benchmark/bm_so_nbody.rb
+++ b/benchmark/bm_so_nbody.rb
@@ -1,148 +1,148 @@
-# The Computer Language Shootout
-# http://shootout.alioth.debian.org
-#
-# Optimized for Ruby by Jesse Millikan
-# From version ported by Michael Neumann from the C gcc version,
-# which was written by Christoph Bauer.
-
-SOLAR_MASS = 4 * Math::PI**2
-DAYS_PER_YEAR = 365.24
-
-def _puts *args
-end
-
-class Planet
- attr_accessor :x, :y, :z, :vx, :vy, :vz, :mass
-
- def initialize(x, y, z, vx, vy, vz, mass)
- @x, @y, @z = x, y, z
- @vx, @vy, @vz = vx * DAYS_PER_YEAR, vy * DAYS_PER_YEAR, vz * DAYS_PER_YEAR
- @mass = mass * SOLAR_MASS
- end
-
- def move_from_i(bodies, nbodies, dt, i)
- while i < nbodies
- b2 = bodies[i]
- dx = @x - b2.x
- dy = @y - b2.y
- dz = @z - b2.z
-
- distance = Math.sqrt(dx * dx + dy * dy + dz * dz)
- mag = dt / (distance * distance * distance)
- b_mass_mag, b2_mass_mag = @mass * mag, b2.mass * mag
-
- @vx -= dx * b2_mass_mag
- @vy -= dy * b2_mass_mag
- @vz -= dz * b2_mass_mag
- b2.vx += dx * b_mass_mag
- b2.vy += dy * b_mass_mag
- b2.vz += dz * b_mass_mag
- i += 1
- end
-
- @x += dt * @vx
- @y += dt * @vy
- @z += dt * @vz
- end
-end
-
-def energy(bodies)
- e = 0.0
- nbodies = bodies.size
-
- for i in 0 ... nbodies
- b = bodies[i]
- e += 0.5 * b.mass * (b.vx * b.vx + b.vy * b.vy + b.vz * b.vz)
- for j in (i + 1) ... nbodies
- b2 = bodies[j]
- dx = b.x - b2.x
- dy = b.y - b2.y
- dz = b.z - b2.z
- distance = Math.sqrt(dx * dx + dy * dy + dz * dz)
- e -= (b.mass * b2.mass) / distance
- end
- end
- e
-end
-
-def offset_momentum(bodies)
- px, py, pz = 0.0, 0.0, 0.0
-
- for b in bodies
- m = b.mass
- px += b.vx * m
- py += b.vy * m
- pz += b.vz * m
- end
-
- b = bodies[0]
- b.vx = - px / SOLAR_MASS
- b.vy = - py / SOLAR_MASS
- b.vz = - pz / SOLAR_MASS
-end
-
-BODIES = [
- # sun
- Planet.new(0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0),
-
- # jupiter
- Planet.new(
- 4.84143144246472090e+00,
- -1.16032004402742839e+00,
- -1.03622044471123109e-01,
- 1.66007664274403694e-03,
- 7.69901118419740425e-03,
- -6.90460016972063023e-05,
- 9.54791938424326609e-04),
-
- # saturn
- Planet.new(
- 8.34336671824457987e+00,
- 4.12479856412430479e+00,
- -4.03523417114321381e-01,
- -2.76742510726862411e-03,
- 4.99852801234917238e-03,
- 2.30417297573763929e-05,
- 2.85885980666130812e-04),
-
- # uranus
- Planet.new(
- 1.28943695621391310e+01,
- -1.51111514016986312e+01,
- -2.23307578892655734e-01,
- 2.96460137564761618e-03,
- 2.37847173959480950e-03,
- -2.96589568540237556e-05,
- 4.36624404335156298e-05),
-
- # neptune
- Planet.new(
- 1.53796971148509165e+01,
- -2.59193146099879641e+01,
- 1.79258772950371181e-01,
- 2.68067772490389322e-03,
- 1.62824170038242295e-03,
- -9.51592254519715870e-05,
- 5.15138902046611451e-05)
-]
-
-init = 200_000 # ARGV[0]
-n = Integer(init)
-
-offset_momentum(BODIES)
-
-puts "%.9f" % energy(BODIES)
-
-nbodies = BODIES.size
-dt = 0.01
-
-n.times do
- i = 0
- while i < nbodies
- b = BODIES[i]
- b.move_from_i(BODIES, nbodies, dt, i + 1)
- i += 1
- end
-end
-
-puts "%.9f" % energy(BODIES)
+# The Computer Language Shootout
+# http://shootout.alioth.debian.org
+#
+# Optimized for Ruby by Jesse Millikan
+# From version ported by Michael Neumann from the C gcc version,
+# which was written by Christoph Bauer.
+
+SOLAR_MASS = 4 * Math::PI**2
+DAYS_PER_YEAR = 365.24
+
+def _puts *args
+end
+
+class Planet
+ attr_accessor :x, :y, :z, :vx, :vy, :vz, :mass
+
+ def initialize(x, y, z, vx, vy, vz, mass)
+ @x, @y, @z = x, y, z
+ @vx, @vy, @vz = vx * DAYS_PER_YEAR, vy * DAYS_PER_YEAR, vz * DAYS_PER_YEAR
+ @mass = mass * SOLAR_MASS
+ end
+
+ def move_from_i(bodies, nbodies, dt, i)
+ while i < nbodies
+ b2 = bodies[i]
+ dx = @x - b2.x
+ dy = @y - b2.y
+ dz = @z - b2.z
+
+ distance = Math.sqrt(dx * dx + dy * dy + dz * dz)
+ mag = dt / (distance * distance * distance)
+ b_mass_mag, b2_mass_mag = @mass * mag, b2.mass * mag
+
+ @vx -= dx * b2_mass_mag
+ @vy -= dy * b2_mass_mag
+ @vz -= dz * b2_mass_mag
+ b2.vx += dx * b_mass_mag
+ b2.vy += dy * b_mass_mag
+ b2.vz += dz * b_mass_mag
+ i += 1
+ end
+
+ @x += dt * @vx
+ @y += dt * @vy
+ @z += dt * @vz
+ end
+end
+
+def energy(bodies)
+ e = 0.0
+ nbodies = bodies.size
+
+ for i in 0 ... nbodies
+ b = bodies[i]
+ e += 0.5 * b.mass * (b.vx * b.vx + b.vy * b.vy + b.vz * b.vz)
+ for j in (i + 1) ... nbodies
+ b2 = bodies[j]
+ dx = b.x - b2.x
+ dy = b.y - b2.y
+ dz = b.z - b2.z
+ distance = Math.sqrt(dx * dx + dy * dy + dz * dz)
+ e -= (b.mass * b2.mass) / distance
+ end
+ end
+ e
+end
+
+def offset_momentum(bodies)
+ px, py, pz = 0.0, 0.0, 0.0
+
+ for b in bodies
+ m = b.mass
+ px += b.vx * m
+ py += b.vy * m
+ pz += b.vz * m
+ end
+
+ b = bodies[0]
+ b.vx = - px / SOLAR_MASS
+ b.vy = - py / SOLAR_MASS
+ b.vz = - pz / SOLAR_MASS
+end
+
+BODIES = [
+ # sun
+ Planet.new(0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0),
+
+ # jupiter
+ Planet.new(
+ 4.84143144246472090e+00,
+ -1.16032004402742839e+00,
+ -1.03622044471123109e-01,
+ 1.66007664274403694e-03,
+ 7.69901118419740425e-03,
+ -6.90460016972063023e-05,
+ 9.54791938424326609e-04),
+
+ # saturn
+ Planet.new(
+ 8.34336671824457987e+00,
+ 4.12479856412430479e+00,
+ -4.03523417114321381e-01,
+ -2.76742510726862411e-03,
+ 4.99852801234917238e-03,
+ 2.30417297573763929e-05,
+ 2.85885980666130812e-04),
+
+ # uranus
+ Planet.new(
+ 1.28943695621391310e+01,
+ -1.51111514016986312e+01,
+ -2.23307578892655734e-01,
+ 2.96460137564761618e-03,
+ 2.37847173959480950e-03,
+ -2.96589568540237556e-05,
+ 4.36624404335156298e-05),
+
+ # neptune
+ Planet.new(
+ 1.53796971148509165e+01,
+ -2.59193146099879641e+01,
+ 1.79258772950371181e-01,
+ 2.68067772490389322e-03,
+ 1.62824170038242295e-03,
+ -9.51592254519715870e-05,
+ 5.15138902046611451e-05)
+]
+
+init = 200_000 # ARGV[0]
+n = Integer(init)
+
+offset_momentum(BODIES)
+
+puts "%.9f" % energy(BODIES)
+
+nbodies = BODIES.size
+dt = 0.01
+
+n.times do
+ i = 0
+ while i < nbodies
+ b = BODIES[i]
+ b.move_from_i(BODIES, nbodies, dt, i + 1)
+ i += 1
+ end
+end
+
+puts "%.9f" % energy(BODIES)
diff --git a/benchmark/bm_so_nsieve.rb b/benchmark/bm_so_nsieve.rb
index 59aead5..a65cc78 100644
--- a/benchmark/bm_so_nsieve.rb
+++ b/benchmark/bm_so_nsieve.rb
@@ -1,35 +1,35 @@
-# The Computer Language Shootout
-# http://shootout.alioth.debian.org/
-#
-# contributed by Glenn Parker, March 2005
-# modified by Evan Phoenix, Sept 2006
-
-def sieve(m)
- flags = Flags.dup[0,m]
- count = 0
- pmax = m - 1
- p = 2
- while p <= pmax
- unless flags[p].zero?
- count += 1
- mult = p
- while mult <= pmax
- flags[mult] = 0
- mult += p
- end
- end
- p += 1
- end
- count
-end
-
-n = 9 # (ARGV[0] || 2).to_i
-Flags = ("\x1" * ( 2 ** n * 10_000)).unpack("c*")
-
-n.downto(n-2) do |exponent|
- break if exponent < 0
- m = (1 << exponent) * 10_000
- # m = (2 ** exponent) * 10_000
- count = sieve(m)
- printf "Primes up to %8d %8d\n", m, count
-end
+# The Computer Language Shootout
+# http://shootout.alioth.debian.org/
+#
+# contributed by Glenn Parker, March 2005
+# modified by Evan Phoenix, Sept 2006
+
+def sieve(m)
+ flags = Flags.dup[0,m]
+ count = 0
+ pmax = m - 1
+ p = 2
+ while p <= pmax
+ unless flags[p].zero?
+ count += 1
+ mult = p
+ while mult <= pmax
+ flags[mult] = 0
+ mult += p
+ end
+ end
+ p += 1
+ end
+ count
+end
+
+n = 9 # (ARGV[0] || 2).to_i
+Flags = ("\x1" * ( 2 ** n * 10_000)).unpack("c*")
+
+n.downto(n-2) do |exponent|
+ break if exponent < 0
+ m = (1 << exponent) * 10_000
+ # m = (2 ** exponent) * 10_000
+ count = sieve(m)
+ printf "Primes up to %8d %8d\n", m, count
+end
diff --git a/benchmark/bm_so_nsieve_bits.rb b/benchmark/bm_so_nsieve_bits.rb
index 693b2f2..019b8b6 100644
--- a/benchmark/bm_so_nsieve_bits.rb
+++ b/benchmark/bm_so_nsieve_bits.rb
@@ -1,42 +1,42 @@
-#!/usr/bin/ruby
-#
-# The Great Computer Language Shootout
-# http://shootout.alioth.debian.org/
-#
-# nsieve-bits in Ruby
-# Contributed by Glenn Parker, March 2005
-
-CharExponent = 3
-BitsPerChar = 1 << CharExponent
-LowMask = BitsPerChar - 1
-
-def sieve(m)
- items = "\xFF" * ((m / BitsPerChar) + 1)
- masks = ""
- BitsPerChar.times do |b|
- masks << (1 << b).chr
- end
-
- count = 0
- pmax = m - 1
- 2.step(pmax, 1) do |p|
- if items[p >> CharExponent][p & LowMask] == 1
- count += 1
- p.step(pmax, p) do |mult|
- a = mult >> CharExponent
- b = mult & LowMask
- items[a] -= masks[b] if items[a][b] != 0
- end
- end
- end
- count
-end
-
-n = 9 # (ARGV[0] || 2).to_i
-n.step(n - 2, -1) do |exponent|
- break if exponent < 0
- m = 2 ** exponent * 10_000
- count = sieve(m)
- printf "Primes up to %8d %8d\n", m, count
-end
-
+#!/usr/bin/ruby
+#
+# The Great Computer Language Shootout
+# http://shootout.alioth.debian.org/
+#
+# nsieve-bits in Ruby
+# Contributed by Glenn Parker, March 2005
+
+CharExponent = 3
+BitsPerChar = 1 << CharExponent
+LowMask = BitsPerChar - 1
+
+def sieve(m)
+ items = "\xFF" * ((m / BitsPerChar) + 1)
+ masks = ""
+ BitsPerChar.times do |b|
+ masks << (1 << b).chr
+ end
+
+ count = 0
+ pmax = m - 1
+ 2.step(pmax, 1) do |p|
+ if items[p >> CharExponent][p & LowMask] == 1
+ count += 1
+ p.step(pmax, p) do |mult|
+ a = mult >> CharExponent
+ b = mult & LowMask
+ items[a] -= masks[b] if items[a][b] != 0
+ end
+ end
+ end
+ count
+end
+
+n = 9 # (ARGV[0] || 2).to_i
+n.step(n - 2, -1) do |exponent|
+ break if exponent < 0
+ m = 2 ** exponent * 10_000
+ count = sieve(m)
+ printf "Primes up to %8d %8d\n", m, count
+end
+
diff --git a/benchmark/bm_so_partial_sums.rb b/benchmark/bm_so_partial_sums.rb
index 41f0a5f..630b45c 100644
--- a/benchmark/bm_so_partial_sums.rb
+++ b/benchmark/bm_so_partial_sums.rb
@@ -1,31 +1,31 @@
-n = 2_500_000 # (ARGV.shift || 1).to_i
-
-alt = 1.0 ; s0 = s1 = s2 = s3 = s4 = s5 = s6 = s7 = s8 = 0.0
-
-1.upto(n) do |d|
- d = d.to_f ; d2 = d * d ; d3 = d2 * d ; ds = Math.sin(d) ; dc = Math.cos(d)
-
- s0 += (2.0 / 3.0) ** (d - 1.0)
- s1 += 1.0 / Math.sqrt(d)
- s2 += 1.0 / (d * (d + 1.0))
- s3 += 1.0 / (d3 * ds * ds)
- s4 += 1.0 / (d3 * dc * dc)
- s5 += 1.0 / d
- s6 += 1.0 / d2
- s7 += alt / d
- s8 += alt / (2.0 * d - 1.0)
-
- alt = -alt
-end
-
-if false
- printf("%.9f\t(2/3)^k\n", s0)
- printf("%.9f\tk^-0.5\n", s1)
- printf("%.9f\t1/k(k+1)\n", s2)
- printf("%.9f\tFlint Hills\n", s3)
- printf("%.9f\tCookson Hills\n", s4)
- printf("%.9f\tHarmonic\n", s5)
- printf("%.9f\tRiemann Zeta\n", s6)
- printf("%.9f\tAlternating Harmonic\n", s7)
- printf("%.9f\tGregory\n", s8)
-end
+n = 2_500_000 # (ARGV.shift || 1).to_i
+
+alt = 1.0 ; s0 = s1 = s2 = s3 = s4 = s5 = s6 = s7 = s8 = 0.0
+
+1.upto(n) do |d|
+ d = d.to_f ; d2 = d * d ; d3 = d2 * d ; ds = Math.sin(d) ; dc = Math.cos(d)
+
+ s0 += (2.0 / 3.0) ** (d - 1.0)
+ s1 += 1.0 / Math.sqrt(d)
+ s2 += 1.0 / (d * (d + 1.0))
+ s3 += 1.0 / (d3 * ds * ds)
+ s4 += 1.0 / (d3 * dc * dc)
+ s5 += 1.0 / d
+ s6 += 1.0 / d2
+ s7 += alt / d
+ s8 += alt / (2.0 * d - 1.0)
+
+ alt = -alt
+end
+
+if false
+ printf("%.9f\t(2/3)^k\n", s0)
+ printf("%.9f\tk^-0.5\n", s1)
+ printf("%.9f\t1/k(k+1)\n", s2)
+ printf("%.9f\tFlint Hills\n", s3)
+ printf("%.9f\tCookson Hills\n", s4)
+ printf("%.9f\tHarmonic\n", s5)
+ printf("%.9f\tRiemann Zeta\n", s6)
+ printf("%.9f\tAlternating Harmonic\n", s7)
+ printf("%.9f\tGregory\n", s8)
+end
diff --git a/benchmark/bm_so_pidigits.rb b/benchmark/bm_so_pidigits.rb
index acffe71..c7d6fbf 100644
--- a/benchmark/bm_so_pidigits.rb
+++ b/benchmark/bm_so_pidigits.rb
@@ -1,92 +1,92 @@
-# The Great Computer Language Shootout
-# http://shootout.alioth.debian.org/
-#
-# contributed by Gabriele Renzi
-
-class PiDigitSpigot
-
- def initialize()
- @z = Transformation.new 1,0,0,1
- @x = Transformation.new 0,0,0,0
- @inverse = Transformation.new 0,0,0,0
- end
-
- def next!
- @y = @z.extract(3)
- if safe? @y
- @z = produce(@y)
- @y
- else
- @z = consume @x.next!()
- next!()
- end
- end
-
- def safe?(digit)
- digit == @z.extract(4)
- end
-
- def produce(i)
- @inverse.qrst(10,-10*i,0,1).compose(@z)
- end
-
- def consume(a)
- @z.compose(a)
- end
-end
-
-
-class Transformation
- attr_reader :q, :r, :s, :t
- def initialize (q, r, s, t)
- @q,@r,@s,@t,@k = q,r,s,t,0
- end
-
- def next!()
- @q = @k = @k + 1
- @r = 4 * @k + 2
- @s = 0
- @t = 2 * @k + 1
- self
- end
-
- def extract(j)
- (@q * j + @r) / (@s * j + @t)
- end
-
- def compose(a)
- self.class.new( @q * a.q,
- @q * a.r + r * a.t,
- @s * a.q + t * a.s,
- @s * a.r + t * a.t
- )
- end
-
- def qrst *args
- initialize *args
- self
- end
-
-
-end
-
-
-WIDTH = 10
-n = 2_500 # Integer(ARGV[0])
-j = 0
-
-digits = PiDigitSpigot.new
-
-while n > 0
- if n >= WIDTH
- WIDTH.times {print digits.next!}
- j += WIDTH
- else
- n.times {print digits.next!}
- (WIDTH-n).times {print " "}
- j += n
- end
- puts "\t:"+j.to_s
- n -= WIDTH
-end
-
+# The Great Computer Language Shootout
+# http://shootout.alioth.debian.org/
+#
+# contributed by Gabriele Renzi
+
+class PiDigitSpigot
+
+ def initialize()
+ @z = Transformation.new 1,0,0,1
+ @x = Transformation.new 0,0,0,0
+ @inverse = Transformation.new 0,0,0,0
+ end
+
+ def next!
+ @y = @z.extract(3)
+ if safe? @y
+ @z = produce(@y)
+ @y
+ else
+ @z = consume @x.next!()
+ next!()
+ end
+ end
+
+ def safe?(digit)
+ digit == @z.extract(4)
+ end
+
+ def produce(i)
+ @inverse.qrst(10,-10*i,0,1).compose(@z)
+ end
+
+ def consume(a)
+ @z.compose(a)
+ end
+end
+
+
+class Transformation
+ attr_reader :q, :r, :s, :t
+ def initialize (q, r, s, t)
+ @q,@r,@s,@t,@k = q,r,s,t,0
+ end
+
+ def next!()
+ @q = @k = @k + 1
+ @r = 4 * @k + 2
+ @s = 0
+ @t = 2 * @k + 1
+ self
+ end
+
+ def extract(j)
+ (@q * j + @r) / (@s * j + @t)
+ end
+
+ def compose(a)
+ self.class.new( @q * a.q,
+ @q * a.r + r * a.t,
+ @s * a.q + t * a.s,
+ @s * a.r + t * a.t
+ )
+ end
+
+ def qrst *args
+ initialize *args
+ self
+ end
+
+
+end
+
+
+WIDTH = 10
+n = 2_500 # Integer(ARGV[0])
+j = 0
+
+digits = PiDigitSpigot.new
+
+while n > 0
+ if n >= WIDTH
+ WIDTH.times {print digits.next!}
+ j += WIDTH
+ else
+ n.times {print digits.next!}
+ (WIDTH-n).times {print " "}
+ j += n
+ end
+ puts "\t:"+j.to_s
+ n -= WIDTH
+end
+
diff --git a/benchmark/bm_so_reverse_complement.rb b/benchmark/bm_so_reverse_complement.rb
index 5cf1a86..82ea666 100644
--- a/benchmark/bm_so_reverse_complement.rb
+++ b/benchmark/bm_so_reverse_complement.rb
@@ -1,30 +1,30 @@
-#!/usr/bin/ruby
-# The Great Computer Language Shootout
-# http://shootout.alioth.debian.org/
-#
-# Contributed by Peter Bjarke Olsen
-# Modified by Doug King
-
-seq=Array.new
-
-def revcomp(seq)
- seq.reverse!.tr!('wsatugcyrkmbdhvnATUGCYRKMBDHVN','WSTAACGRYMKVHDBNTAACGRYMKVHDBN')
- stringlen=seq.length
- 0.step(stringlen-1,60) {|x| print seq.slice(x,60) , "\n"}
-end
-
-input = open(File.join(File.dirname($0), 'fasta.output.2500000'), 'rb')
-
-while input.gets
- if $_ =~ />/
- if seq.length != 0
- revcomp(seq.join)
- seq=Array.new
- end
- puts $_
- else
- $_.sub(/\n/,'')
- seq.push $_
- end
-end
-revcomp(seq.join)
+#!/usr/bin/ruby
+# The Great Computer Language Shootout
+# http://shootout.alioth.debian.org/
+#
+# Contributed by Peter Bjarke Olsen
+# Modified by Doug King
+
+seq=Array.new
+
+def revcomp(seq)
+ seq.reverse!.tr!('wsatugcyrkmbdhvnATUGCYRKMBDHVN','WSTAACGRYMKVHDBNTAACGRYMKVHDBN')
+ stringlen=seq.length
+ 0.step(stringlen-1,60) {|x| print seq.slice(x,60) , "\n"}
+end
+
+input = open(File.join(File.dirname($0), 'fasta.output.2500000'), 'rb')
+
+while input.gets
+ if $_ =~ />/
+ if seq.length != 0
+ revcomp(seq.join)
+ seq=Array.new
+ end
+ puts $_
+ else
+ $_.sub(/\n/,'')
+ seq.push $_
+ end
+end
+revcomp(seq.join)
diff --git a/benchmark/bm_so_spectralnorm.rb b/benchmark/bm_so_spectralnorm.rb
index 3617da5..6b97206 100644
--- a/benchmark/bm_so_spectralnorm.rb
+++ b/benchmark/bm_so_spectralnorm.rb
@@ -1,50 +1,50 @@
-# The Computer Language Shootout
-# http://shootout.alioth.debian.org/
-# Contributed by Sokolov Yura
-
-def eval_A(i,j)
- return 1.0/((i+j)*(i+j+1)/2+i+1)
-end
-
-def eval_A_times_u(u)
- v, i = nil, nil
- (0..u.length-1).collect { |i|
- v = 0
- for j in 0..u.length-1
- v += eval_A(i,j)*u[j]
- end
- v
- }
-end
-
-def eval_At_times_u(u)
- v, i = nil, nil
- (0..u.length-1).collect{|i|
- v = 0
- for j in 0..u.length-1
- v += eval_A(j,i)*u[j]
- end
- v
- }
-end
-
-def eval_AtA_times_u(u)
- return eval_At_times_u(eval_A_times_u(u))
-end
-
-n = 500 # ARGV[0].to_i
-
-u=[1]*n
-for i in 1..10
- v=eval_AtA_times_u(u)
- u=eval_AtA_times_u(v)
-end
-vBv=0
-vv=0
-for i in 0..n-1
- vBv += u[i]*v[i]
- vv += v[i]*v[i]
-end
-
-str = "%0.9f" % (Math.sqrt(vBv/vv)), "\n"
-# print str
+# The Computer Language Shootout
+# http://shootout.alioth.debian.org/
+# Contributed by Sokolov Yura
+
+def eval_A(i,j)
+ return 1.0/((i+j)*(i+j+1)/2+i+1)
+end
+
+def eval_A_times_u(u)
+ v, i = nil, nil
+ (0..u.length-1).collect { |i|
+ v = 0
+ for j in 0..u.length-1
+ v += eval_A(i,j)*u[j]
+ end
+ v
+ }
+end
+
+def eval_At_times_u(u)
+ v, i = nil, nil
+ (0..u.length-1).collect{|i|
+ v = 0
+ for j in 0..u.length-1
+ v += eval_A(j,i)*u[j]
+ end
+ v
+ }
+end
+
+def eval_AtA_times_u(u)
+ return eval_At_times_u(eval_A_times_u(u))
+end
+
+n = 500 # ARGV[0].to_i
+
+u=[1]*n
+for i in 1..10
+ v=eval_AtA_times_u(u)
+ u=eval_AtA_times_u(v)
+end
+vBv=0
+vv=0
+for i in 0..n-1
+ vBv += u[i]*v[i]
+ vv += v[i]*v[i]
+end
+
+str = "%0.9f" % (Math.sqrt(vBv/vv)), "\n"
+# print str
diff --git a/benchmark/bm_vm1_ivar_set.rb b/benchmark/bm_vm1_ivar_set.rb
index 023e397..c8076c6 100644
--- a/benchmark/bm_vm1_ivar_set.rb
+++ b/benchmark/bm_vm1_ivar_set.rb
@@ -1,6 +1,6 @@
-i = 0
-while i<30_000_000 # while loop 1
- i+= 1
- @a = 1
- @b = 2
-end
+i = 0
+while i<30_000_000 # while loop 1
+ i+= 1
+ @a = 1
+ @b = 2
+end
diff --git a/benchmark/bm_vm2_eval.rb b/benchmark/bm_vm2_eval.rb
index 9ab781e..375dccc 100644
--- a/benchmark/bm_vm2_eval.rb
+++ b/benchmark/bm_vm2_eval.rb
@@ -1,6 +1,6 @@
-i=0
-while i<6000000 # benchmark loop 2
- i+=1
- eval("1")
-end
-
+i=0
+while i<6000000 # benchmark loop 2
+ i+=1
+ eval("1")
+end
+
diff --git a/benchmark/driver.rb b/benchmark/driver.rb
index dd6e1bf..861d54f 100644
--- a/benchmark/driver.rb
+++ b/benchmark/driver.rb
@@ -1,238 +1,238 @@
-#
-# Ruby Benchmark driver
-#
-
-require 'optparse'
-require 'benchmark'
-require 'pp'
-
-class BenchmarkDriver
- def self.benchmark(opt)
- driver = self.new(opt[:execs], opt[:dir], opt)
- begin
- driver.run
- ensure
- driver.show_results
- end
- end
-
- def output *args
- puts(*args)
- @output and @output.puts(*args)
- end
-
- def message *args
- output(*args) if @verbose
- end
-
- def message_print *args
- if @verbose
- print(*args)
- STDOUT.flush
- @output and @output.print(*args)
- end
- end
-
- def progress_message *args
- unless STDOUT.tty?
- STDERR.print(*args)
- STDERR.flush
- end
- end
-
- def initialize execs, dir, opt = {}
- @execs = execs.map{|e|
- e.strip!
- next if e.empty?
-
- if /(.+)::(.+)/ =~ e
- # ex) ruby-a::/path/to/ruby-a
- v = $1.strip
- e = $2
- else
- v = `#{e} -v`.chomp
- v.sub!(/ patchlevel \d+/, '')
- end
- [e, v]
- }.compact
-
- @dir = dir
- @repeat = opt[:repeat] || 1
- @repeat = 1 if @repeat < 1
- @pattern = opt[:pattern] || nil
- @verbose = opt[:quiet] ? false : (opt[:verbose] || false)
- @output = opt[:output] ? open(opt[:output], 'w') : nil
- @loop_wl1 = @loop_wl2 = nil
- @opt = opt
-
- # [[name, [[r-1-1, r-1-2, ...], [r-2-1, r-2-2, ...]]], ...]
- @results = []
-
- if @verbose
- @start_time = Time.now
- message @start_time
- @execs.each_with_index{|(e, v), i|
- message "target #{i}: #{v}"
- }
- end
- end
-
- def show_results
- output
-
- if @verbose
- message '-----------------------------------------------------------'
- message 'raw data:'
- message
- message PP.pp(@results, "", 79)
- message
- message "Elapesed time: #{Time.now - @start_time} (sec)"
- end
-
- output '-----------------------------------------------------------'
- output 'benchmark results:'
-
- if @verbose and @repeat > 1
- output "minimum results in each #{@repeat} measurements."
- end
-
- output "name\t#{@execs.map{|(e, v)| v}.join("\t")}"
- @results.each{|v, result|
- rets = []
- s = nil
- result.each_with_index{|e, i|
- r = e.min
- case v
- when /^vm1_/
- if @loop_wl1
- r -= @loop_wl1[i]
- s = '*'
- end
- when /^vm2_/
- if @loop_wl2
- r -= @loop_wl2[i]
- s = '*'
- end
- end
- rets << sprintf("%.3f", r)
- }
- output "#{v}#{s}\t#{rets.join("\t")}"
- }
- end
-
- def files
- flag = {}
- vm1 = vm2 = wl1 = wl2 = false
- @files = Dir.glob(File.join(@dir, 'bm*.rb')).map{|file|
- next if @pattern && /#{@pattern}/ !~ File.basename(file)
- case file
- when /bm_(vm[12])_/, /bm_loop_(whileloop2?).rb/
- flag[$1] = true
- end
- file
- }.compact
-
- if flag['vm1'] && !flag['whileloop']
- @files << File.join(@dir, 'bm_loop_whileloop.rb')
- elsif flag['vm2'] && !flag['whileloop2']
- @files << File.join(@dir, 'bm_loop_whileloop2.rb')
- end
-
- @files.sort!
- progress_message "total: #{@files.size * @repeat} trial(s) (#{@repeat} trial(s) for #{@files.size} benchmark(s))\n"
- @files
- end
-
- def run
- files.each_with_index{|file, i|
- @i = i
- r = measure_file(file)
-
- if /bm_loop_whileloop.rb/ =~ file
- @loop_wl1 = r[1].map{|e| e.min}
- elsif /bm_loop_whileloop2.rb/ =~ file
- @loop_wl2 = r[1].map{|e| e.min}
- end
- }
- end
-
- def measure_file file
- name = File.basename(file, '.rb').sub(/^bm_/, '')
- prepare_file = File.join(File.dirname(file), "prepare_#{name}.rb")
- load prepare_file if FileTest.exist?(prepare_file)
-
- if @verbose
- output
- output '-----------------------------------------------------------'
- output name
- output
- output File.read(file)
- output
- end
-
- result = [name]
- result << @execs.map{|(e, v)|
- (0...@repeat).map{
- message_print "#{v}\t"
- progress_message '.'
-
- m = measure(e, file)
- message "#{m}"
- m
- }
- }
- @results << result
- result
- end
-
- def measure executable, file
- cmd = "#{executable} #{file}"
- m = Benchmark.measure{
- `#{cmd}`
- }
-
- if $? != 0
- raise "Benchmark process exited with abnormal status (#{$?})"
- end
-
- m.real
- end
-end
-
-if __FILE__ == $0
- opt = {
- :execs => ['ruby'],
- :dir => './',
- :repeat => 1,
- :output => "bmlog-#{Time.now.strftime('%Y%m%d-%H%M%S')}.#{$$}",
- }
-
- parser = OptionParser.new{|o|
- o.on('-e', '--executables [EXECS]',
- "Specify benchmark one or more targets. (exec1; exec2; exec3, ...)"){|e|
- opt[:execs] = e.split(/;/)
- }
- o.on('-d', '--directory [DIRECTORY]', "Benchmark suites directory"){|d|
- opt[:dir] = d
- }
- o.on('-p', '--pattern [PATTERN]', "Benchmark name pattern"){|p|
- opt[:pattern] = p
- }
- o.on('-r', '--repeat-count [NUM]', "Repeat count"){|n|
- opt[:repeat] = n.to_i
- }
- o.on('-o', '--output-file [FILE]', "Output file"){|o|
- opt[:output] = o
- }
- o.on('-q', '--quiet', "Run without notify information except result table."){|q|
- opt[:quiet] = q
- }
- o.on('-v', '--verbose'){|v|
- opt[:verbose] = v
- }
- }
-
- parser.parse!(ARGV)
- BenchmarkDriver.benchmark(opt)
-end
-
+#
+# Ruby Benchmark driver
+#
+
+require 'optparse'
+require 'benchmark'
+require 'pp'
+
+class BenchmarkDriver
+ def self.benchmark(opt)
+ driver = self.new(opt[:execs], opt[:dir], opt)
+ begin
+ driver.run
+ ensure
+ driver.show_results
+ end
+ end
+
+ def output *args
+ puts(*args)
+ @output and @output.puts(*args)
+ end
+
+ def message *args
+ output(*args) if @verbose
+ end
+
+ def message_print *args
+ if @verbose
+ print(*args)
+ STDOUT.flush
+ @output and @output.print(*args)
+ end
+ end
+
+ def progress_message *args
+ unless STDOUT.tty?
+ STDERR.print(*args)
+ STDERR.flush
+ end
+ end
+
+ def initialize execs, dir, opt = {}
+ @execs = execs.map{|e|
+ e.strip!
+ next if e.empty?
+
+ if /(.+)::(.+)/ =~ e
+ # ex) ruby-a::/path/to/ruby-a
+ v = $1.strip
+ e = $2
+ else
+ v = `#{e} -v`.chomp
+ v.sub!(/ patchlevel \d+/, '')
+ end
+ [e, v]
+ }.compact
+
+ @dir = dir
+ @repeat = opt[:repeat] || 1
+ @repeat = 1 if @repeat < 1
+ @pattern = opt[:pattern] || nil
+ @verbose = opt[:quiet] ? false : (opt[:verbose] || false)
+ @output = opt[:output] ? open(opt[:output], 'w') : nil
+ @loop_wl1 = @loop_wl2 = nil
+ @opt = opt
+
+ # [[name, [[r-1-1, r-1-2, ...], [r-2-1, r-2-2, ...]]], ...]
+ @results = []
+
+ if @verbose
+ @start_time = Time.now
+ message @start_time
+ @execs.each_with_index{|(e, v), i|
+ message "target #{i}: #{v}"
+ }
+ end
+ end
+
+ def show_results
+ output
+
+ if @verbose
+ message '-----------------------------------------------------------'
+ message 'raw data:'
+ message
+ message PP.pp(@results, "", 79)
+ message
+ message "Elapesed time: #{Time.now - @start_time} (sec)"
+ end
+
+ output '-----------------------------------------------------------'
+ output 'benchmark results:'
+
+ if @verbose and @repeat > 1
+ output "minimum results in each #{@repeat} measurements."
+ end
+
+ output "name\t#{@execs.map{|(e, v)| v}.join("\t")}"
+ @results.each{|v, result|
+ rets = []
+ s = nil
+ result.each_with_index{|e, i|
+ r = e.min
+ case v
+ when /^vm1_/
+ if @loop_wl1
+ r -= @loop_wl1[i]
+ s = '*'
+ end
+ when /^vm2_/
+ if @loop_wl2
+ r -= @loop_wl2[i]
+ s = '*'
+ end
+ end
+ rets << sprintf("%.3f", r)
+ }
+ output "#{v}#{s}\t#{rets.join("\t")}"
+ }
+ end
+
+ def files
+ flag = {}
+ vm1 = vm2 = wl1 = wl2 = false
+ @files = Dir.glob(File.join(@dir, 'bm*.rb')).map{|file|
+ next if @pattern && /#{@pattern}/ !~ File.basename(file)
+ case file
+ when /bm_(vm[12])_/, /bm_loop_(whileloop2?).rb/
+ flag[$1] = true
+ end
+ file
+ }.compact
+
+ if flag['vm1'] && !flag['whileloop']
+ @files << File.join(@dir, 'bm_loop_whileloop.rb')
+ elsif flag['vm2'] && !flag['whileloop2']
+ @files << File.join(@dir, 'bm_loop_whileloop2.rb')
+ end
+
+ @files.sort!
+ progress_message "total: #{@files.size * @repeat} trial(s) (#{@repeat} trial(s) for #{@files.size} benchmark(s))\n"
+ @files
+ end
+
+ def run
+ files.each_with_index{|file, i|
+ @i = i
+ r = measure_file(file)
+
+ if /bm_loop_whileloop.rb/ =~ file
+ @loop_wl1 = r[1].map{|e| e.min}
+ elsif /bm_loop_whileloop2.rb/ =~ file
+ @loop_wl2 = r[1].map{|e| e.min}
+ end
+ }
+ end
+
+ def measure_file file
+ name = File.basename(file, '.rb').sub(/^bm_/, '')
+ prepare_file = File.join(File.dirname(file), "prepare_#{name}.rb")
+ load prepare_file if FileTest.exist?(prepare_file)
+
+ if @verbose
+ output
+ output '-----------------------------------------------------------'
+ output name
+ output
+ output File.read(file)
+ output
+ end
+
+ result = [name]
+ result << @execs.map{|(e, v)|
+ (0...@repeat).map{
+ message_print "#{v}\t"
+ progress_message '.'
+
+ m = measure(e, file)
+ message "#{m}"
+ m
+ }
+ }
+ @results << result
+ result
+ end
+
+ def measure executable, file
+ cmd = "#{executable} #{file}"
+ m = Benchmark.measure{
+ `#{cmd}`
+ }
+
+ if $? != 0
+ raise "Benchmark process exited with abnormal status (#{$?})"
+ end
+
+ m.real
+ end
+end
+
+if __FILE__ == $0
+ opt = {
+ :execs => ['ruby'],
+ :dir => './',
+ :repeat => 1,
+ :output => "bmlog-#{Time.now.strftime('%Y%m%d-%H%M%S')}.#{$$}",
+ }
+
+ parser = OptionParser.new{|o|
+ o.on('-e', '--executables [EXECS]',
+ "Specify benchmark one or more targets. (exec1; exec2; exec3, ...)"){|e|
+ opt[:execs] = e.split(/;/)
+ }
+ o.on('-d', '--directory [DIRECTORY]', "Benchmark suites directory"){|d|
+ opt[:dir] = d
+ }
+ o.on('-p', '--pattern [PATTERN]', "Benchmark name pattern"){|p|
+ opt[:pattern] = p
+ }
+ o.on('-r', '--repeat-count [NUM]', "Repeat count"){|n|
+ opt[:repeat] = n.to_i
+ }
+ o.on('-o', '--output-file [FILE]', "Output file"){|o|
+ opt[:output] = o
+ }
+ o.on('-q', '--quiet', "Run without notify information except result table."){|q|
+ opt[:quiet] = q
+ }
+ o.on('-v', '--verbose'){|v|
+ opt[:verbose] = v
+ }
+ }
+
+ parser.parse!(ARGV)
+ BenchmarkDriver.benchmark(opt)
+end
+
diff --git a/benchmark/make_fasta_output.rb b/benchmark/make_fasta_output.rb
index 158d8fd..b6d787a 100644
--- a/benchmark/make_fasta_output.rb
+++ b/benchmark/make_fasta_output.rb
@@ -1,19 +1,19 @@
-# prepare 'fasta.output'
-
-def prepare_fasta_output n
- filebase = File.join(File.dirname($0), 'fasta.output')
- script = File.join(File.dirname($0), 'bm_so_fasta.rb')
- file = "#{filebase}.#{n}"
-
- unless FileTest.exist?(file)
- STDERR.puts "preparing #{file}"
-
- open(file, 'w'){|f|
- ARGV[0] = n
- $stdout = f
- load script
- $stdout = STDOUT
- }
- end
-end
-
+# prepare 'fasta.output'
+
+def prepare_fasta_output n
+ filebase = File.join(File.dirname($0), 'fasta.output')
+ script = File.join(File.dirname($0), 'bm_so_fasta.rb')
+ file = "#{filebase}.#{n}"
+
+ unless FileTest.exist?(file)
+ STDERR.puts "preparing #{file}"
+
+ open(file, 'w'){|f|
+ ARGV[0] = n
+ $stdout = f
+ load script
+ $stdout = STDOUT
+ }
+ end
+end
+
diff --git a/benchmark/prepare_so_count_words.rb b/benchmark/prepare_so_count_words.rb
index 54ea72b..ee2138c 100644
--- a/benchmark/prepare_so_count_words.rb
+++ b/benchmark/prepare_so_count_words.rb
@@ -1,15 +1,15 @@
-# prepare 'wc.input'
-
-def prepare_wc_input
- wcinput = File.join(File.dirname($0), 'wc.input')
- wcbase = File.join(File.dirname($0), 'wc.input.base')
- unless FileTest.exist?(wcinput)
- data = File.read(wcbase)
- 13.times{
- data << data
- }
- open(wcinput, 'w'){|f| f.write data}
- end
-end
-
-prepare_wc_input
+# prepare 'wc.input'
+
+def prepare_wc_input
+ wcinput = File.join(File.dirname($0), 'wc.input')
+ wcbase = File.join(File.dirname($0), 'wc.input.base')
+ unless FileTest.exist?(wcinput)
+ data = File.read(wcbase)
+ 13.times{
+ data << data
+ }
+ open(wcinput, 'w'){|f| f.write data}
+ end
+end
+
+prepare_wc_input
diff --git a/benchmark/prepare_so_k_nucleotide.rb b/benchmark/prepare_so_k_nucleotide.rb
index 62e0c76..f28f446 100644
--- a/benchmark/prepare_so_k_nucleotide.rb
+++ b/benchmark/prepare_so_k_nucleotide.rb
@@ -1,2 +1,2 @@
-require File.join(File.dirname(__FILE__), 'make_fasta_output')
-prepare_fasta_output(100_000)
+require File.join(File.dirname(__FILE__), 'make_fasta_output')
+prepare_fasta_output(100_000)
diff --git a/benchmark/prepare_so_reverse_complement.rb b/benchmark/prepare_so_reverse_complement.rb
index b1cd837..7f08910 100644
--- a/benchmark/prepare_so_reverse_complement.rb
+++ b/benchmark/prepare_so_reverse_complement.rb
@@ -1,2 +1,2 @@
-require File.join(File.dirname(__FILE__), 'make_fasta_output')
-prepare_fasta_output(2_500_000)
+require File.join(File.dirname(__FILE__), 'make_fasta_output')
+prepare_fasta_output(2_500_000)
diff --git a/id.h b/id.h
index 4990dcd..fa22d8c 100644
--- a/id.h
+++ b/id.h
@@ -1,53 +1,53 @@
-/**********************************************************************
-
- id.h -
-
- $Author: ko1 $
- $Date: $
- created at: Thu Jul 12 04:38:07 2007
-
- Copyright (C) 2007 Koichi Sasada
-
-**********************************************************************/
-
-extern VALUE symIFUNC;
-extern VALUE symCFUNC;
-
-extern ID idPLUS;
-extern ID idMINUS;
-extern ID idMULT;
-extern ID idDIV;
-extern ID idMOD;
-extern ID idLT;
-extern ID idLTLT;
-extern ID idLE;
-extern ID idGT;
-extern ID idGE;
-extern ID idEq;
-extern ID idEqq;
-extern ID idBackquote;
-extern ID idEqTilde;
-extern ID idThrowState;
-extern ID idAREF;
-extern ID idASET;
-extern ID idIntern;
-extern ID idMethodMissing;
-extern ID idLength;
-extern ID idGets;
-extern ID idSucc;
-extern ID idEach;
-extern ID idLambda;
-extern ID idRangeEachLT;
-extern ID idRangeEachLE;
-extern ID idArrayEach;
-extern ID idTimes;
-extern ID idEnd;
-extern ID idBitblt;
-extern ID idAnswer;
-extern ID idSend;
-extern ID idSendBang;
-extern ID id__send;
-extern ID id__send_bang;
-extern ID id__send__;
-
-
+/**********************************************************************
+
+ id.h -
+
+ $Author: ko1 $
+ $Date: $
+ created at: Thu Jul 12 04:38:07 2007
+
+ Copyright (C) 2007 Koichi Sasada
+
+**********************************************************************/
+
+extern VALUE symIFUNC;
+extern VALUE symCFUNC;
+
+extern ID idPLUS;
+extern ID idMINUS;
+extern ID idMULT;
+extern ID idDIV;
+extern ID idMOD;
+extern ID idLT;
+extern ID idLTLT;
+extern ID idLE;
+extern ID idGT;
+extern ID idGE;
+extern ID idEq;
+extern ID idEqq;
+extern ID idBackquote;
+extern ID idEqTilde;
+extern ID idThrowState;
+extern ID idAREF;
+extern ID idASET;
+extern ID idIntern;
+extern ID idMethodMissing;
+extern ID idLength;
+extern ID idGets;
+extern ID idSucc;
+extern ID idEach;
+extern ID idLambda;
+extern ID idRangeEachLT;
+extern ID idRangeEachLE;
+extern ID idArrayEach;
+extern ID idTimes;
+extern ID idEnd;
+extern ID idBitblt;
+extern ID idAnswer;
+extern ID idSend;
+extern ID idSendBang;
+extern ID id__send;
+extern ID id__send_bang;
+extern ID id__send__;
+
+
diff --git a/test/ruby/test_enumerator.rb b/test/ruby/test_enumerator.rb
index 27a71e4..cb0c393 100644
--- a/test/ruby/test_enumerator.rb
+++ b/test/ruby/test_enumerator.rb
@@ -1,47 +1,47 @@
-require 'test/unit'
-
-class TestEnumerator < Test::Unit::TestCase
- def enum_test obj
- i = 0
- obj.map{|e|
- e
- }.sort
- end
-
- def test_iterators
- assert_equal [0, 1, 2], enum_test(3.times)
- assert_equal [:x, :y, :z], enum_test([:x, :y, :z].each)
- assert_equal [[:x, 1], [:y, 2]], enum_test({:x=>1, :y=>2})
- end
-
- ## Enumerator as Iterator
-
- def test_next
- e = 3.times
- 3.times{|i|
- assert_equal i, e.next
- }
- assert_raise(StopIteration){e.next}
- end
-
- def test_loop
- e = 3.times
- i = 0
- loop{
- assert_equal(i, e.next)
- i += 1
- }
- end
-
- def test_nested_itaration
- def (o = Object.new).each
- yield :ok1
- yield [:ok2, :x].each.next
- end
- e = o.to_enum
- assert_equal :ok1, e.next
- assert_equal :ok2, e.next
- assert_raise(StopIteration){e.next}
- end
-end
-
+require 'test/unit'
+
+class TestEnumerator < Test::Unit::TestCase
+ def enum_test obj
+ i = 0
+ obj.map{|e|
+ e
+ }.sort
+ end
+
+ def test_iterators
+ assert_equal [0, 1, 2], enum_test(3.times)
+ assert_equal [:x, :y, :z], enum_test([:x, :y, :z].each)
+ assert_equal [[:x, 1], [:y, 2]], enum_test({:x=>1, :y=>2})
+ end
+
+ ## Enumerator as Iterator
+
+ def test_next
+ e = 3.times
+ 3.times{|i|
+ assert_equal i, e.next
+ }
+ assert_raise(StopIteration){e.next}
+ end
+
+ def test_loop
+ e = 3.times
+ i = 0
+ loop{
+ assert_equal(i, e.next)
+ i += 1
+ }
+ end
+
+ def test_nested_itaration
+ def (o = Object.new).each
+ yield :ok1
+ yield [:ok2, :x].each.next
+ end
+ e = o.to_enum
+ assert_equal :ok1, e.next
+ assert_equal :ok2, e.next
+ assert_raise(StopIteration){e.next}
+ end
+end
+