From 75feee0968c9345e7ffd2bda9835fcd60b4c0880 Mon Sep 17 00:00:00 2001 From: nobu Date: Fri, 16 Nov 2007 01:30:29 +0000 Subject: * set eol-style. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@13944 b2dd03c8-39d4-4d8f-98ff-823fe69b080e --- benchmark/bm_app_erb.rb | 52 +- benchmark/bm_app_uri.rb | 16 +- benchmark/bm_io_file_create.rb | 26 +- benchmark/bm_io_file_read.rb | 30 +- benchmark/bm_io_file_write.rb | 28 +- benchmark/bm_so_binary_trees.rb | 114 +-- benchmark/bm_so_fannkuch.rb | 90 +-- benchmark/bm_so_fasta.rb | 162 ++-- benchmark/bm_so_k_nucleotide.rb | 96 +-- benchmark/bm_so_mandelbrot.rb | 114 +-- benchmark/bm_so_meteor_contest.rb | 1128 ++++++++++++++-------------- benchmark/bm_so_nbody.rb | 296 ++++---- benchmark/bm_so_nsieve.rb | 70 +- benchmark/bm_so_nsieve_bits.rb | 84 +-- benchmark/bm_so_partial_sums.rb | 62 +- benchmark/bm_so_pidigits.rb | 184 ++--- benchmark/bm_so_reverse_complement.rb | 60 +- benchmark/bm_so_spectralnorm.rb | 100 +-- benchmark/bm_vm1_ivar_set.rb | 12 +- benchmark/bm_vm2_eval.rb | 12 +- benchmark/driver.rb | 476 ++++++------ benchmark/make_fasta_output.rb | 38 +- benchmark/prepare_so_count_words.rb | 30 +- benchmark/prepare_so_k_nucleotide.rb | 4 +- benchmark/prepare_so_reverse_complement.rb | 4 +- 25 files changed, 1644 insertions(+), 1644 deletions(-) (limited to 'benchmark') diff --git a/benchmark/bm_app_erb.rb b/benchmark/bm_app_erb.rb index c4fcfac887..e58b7a34a1 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__ - - - <%= title %> - -

<%= title %>

- <%= content %> -

- - +# +# 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__ + + + <%= title %> + +

<%= title %>

+ <%= content %> +

+ + diff --git a/benchmark/bm_app_uri.rb b/benchmark/bm_app_uri.rb index 49fe5a81a8..586edfd5dc 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 db4e4dedd2..7adbe9ea5e 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 488a4e90ad..2b4212db76 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 05c7e7e45e..3cec58c6ae 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 138c5290f5..6a26465578 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 23298a8a31..a214f2e205 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 b95f5e9f10..3f759ba7ae 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 c0a5ba5046..dadab3e79c 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 2c05878863..76331c64b8 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 5dd720c340..30b99715af 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 709d58b7ff..d6c5bb9e61 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 59aead5893..a65cc78233 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 693b2f246d..019b8b6382 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 41f0a5fb87..630b45cb8d 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 acffe71ae7..c7d6fbfb4d 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 5cf1a86ada..82ea666994 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 3617da5236..6b97206689 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 023e397e92..c8076c6ab6 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 9ab781edd4..375dccc00e 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 dd6e1bf597..861d54f904 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 158d8fd161..b6d787ae27 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 54ea72b8ed..ee2138cdb2 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 62e0c76fb9..f28f4460a1 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 b1cd837626..7f089109de 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) -- cgit v1.2.1