0

修订 #3

我正在尝试使用原始的 3-arg 模型函数在 Ruby 中开发 Ackermann。我这样做的尝试似乎显示了 memoize'd 版本 - ack比原始版本花费更长的时间 -原始- 所以显然“某事”是错误的：

1% ruby -v
ruby 2.0.0p648 (2015-12-16 revision 53162) [universal.x86_64-darwin16]
1% time ruby ackermann3.rb raw silent
raw 0.107u 0.023s 0:00.13 92.3% 0+0k 0+0io 0pf+0w
1% time ruby ackermann3.rb ack silent
ack 0.563u 0.049s 0:00.62 96.7% 0+0k 0+0io 0pf+0w

对于这个模块 Ackermann3.rb

##
# https://www.saylor.org/site/wp-content/uploads/2013/04/Ackermann-Function.pdf
#
# Ackermann's original three-argument function: ƒ(m,n,p) is
# defined recursively as follows for nonnegative integers m, n, and p:
#
#  ƒ(m,n,0) = m + n
#  ƒ(m,0,1) = 0
#  ƒ(m,0,2) = 1
#  ƒ(m,0,p) = m for p > 2
#  ƒ(m,n,p) = ƒ(m, ƒ(m,n - 1,p), p - 1) for n > 0 and p > 0
#
#  Usage: ruby ./ackerman3.rb raw | ack
#
# RUBY_THREAD_VM_STACK_SIZE 10M
##

fun = ARGV[0]
if fun.nil?
  puts "Usage: ruby ./ackermann3.rb {ack | raw} [silent]"
  exit 1
end

log = ARGV[1]
if log.nil?
  silent = false
elsif 'silent'.match(log.downcase)
  silent = true
else
  silent = false
end

def is_number? string
  true if Float(string) rescue false
end

def filesize(string_size)
  units = ['B', 'K', 'M', 'G', 'T', 'P', 'E']
  size = Float(string_size)

  return '0b' if size == 0
  exp = (Math.log(size) / Math.log(1024)).to_i
  exp = 6 if exp > 6 

  bits = '%.1f' % [size.to_f / 1024 ** exp]
  if "#{bits}".end_with? ".0"
    bits['.0'] = ''
  end
  '%s%s' % [bits, units[exp]]
end

stk = ENV['RUBY_THREAD_VM_STACK_SIZE']
if stk.nil?
  stk = "undef stk"
elsif is_number?(stk)
  stk = "EOF " + filesize(stk)
end

def ack(m, n, p)
  @results ||= {}
  @results[[m,n,p]] ||= begin
    if p == 0
      m + n
    elsif n == 0 && p > 2
      m
    elsif n == 0 && p > 0
      p - 1
    else
      ack(m, ack(m,n - 1,p), p - 1)
    end
  end
end

def raw(m, n, p)
  if p == 0
    m + n
  elsif n == 0 && p > 2
    m
  elsif n == 0 && p > 0
    p - 1
  else
    raw(m, raw(m,n - 1,p), p - 1)
  end
end

9.times do |m|
  9.times do |n|
    9.times do |p|

      if (m+n+p) < 9
        print "#{fun} (#{m}, #{n}, #{p}) => " unless silent
        begin
          result = Object.send(fun, m, n, p)
        rescue SystemStackError
          #yoink
          result = stk
        end
        puts "#{result}" unless silent
      end

    end
  end
end
print "#{fun} " if silent

修改了脚本以解决先前的评论 - 我遇到的错误，但我不明白为什么记忆的变体无效。

4

0 回答 0