哈希与兰达斯

Question

我找到两个看起来彼此接近的例子来寻找斐波纳契数:

• LAMBDA

  fibonacci = ->(x){ x < 2 ? x : fibonacci[x-1] + fibonacci[x-2] }
  fibonacci[6]  # => 8
  

• 哈希

  fibonacci = Hash.new{ |h,x| h[x] = x < 2 ? x : h[x-1] + h[x-2] }
  fibonacci[6]  # => 8 
  

我之前在红宝石中使用了哈希和lambdas,但不是这样的.这是一种存储函数的方法:

if x < 2
  x
else
 fibonacci[x-1] + fibonacci[x-2]

1. 你能详细解释一下这是如何工作的吗？这是使用递归吗？
2. 这样的哈希和lambdas之间有什么区别？

Answer 1

是的,它正在使用递归.如果我们查看{} -brackets中的代码,我们就可以找到答案.让我们开始看哈希.new关键字后面的值是默认值.如果散列中尚不存在该值,则将分配的值.

hash = Hash.new
p hash['new_value'] #=> nil

default_value_hash = Hash.new(0)
puts default_value_hash['new_value'] #=> 0

hash_with_block = Hash.new{|h,x| x}
puts hash_with_block['new_value'] #=> 'new_value'

所以当我们宣布时

 fibonacci = Hash.new{ |h,x| h[x] = x < 2 ? x : h[x-1] + h[x-2] }

我们基本上是说 - 使用默认值创建一个新哈希.如果我们要求一个小于或等于2的数字(x),只需返回输入(x).否则,请给出键值为x-1和x-2的字典值的总和.基本上是斐波那契算法.如果x-1和x-2不存在,它将再次运行相同的代码,直到两个基本输入值为1和2.

两种方法之间的区别在于散列保存了值(在散列中......).在某些情况下,这可能是一个巨大的优势.每次调用lambda时,都需要重新计算被调用值以下所有数字的值.

# Let's create a counter to keep track of the number of time the lambda is called.
# Please do not use global variables in real code. I am just lazy here.
@lambda_counter = 0

fibonacci_lambda = ->(x){ 
  @lambda_counter += 1
  x < 2 ? x : fibonacci_lambda[x-1] + fibonacci_lambda[x-2]
}

p (1..20).map{|x| fibonacci_lambda[x]}
# => [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]

p @lambda_counter # => 57290
# lambda called 57290 times!

@hash_counter = 0

fibonacci_hash = Hash.new{ |h,x|
  @hash_counter += 1
  h[x] = x < 2 ? x : h[x-1] + h[x-2]
}

p (1..20).map{|x| fibonacci_hash[x]}
# => [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]

p @hash_counter # => 21
# Only called 21 times!

调用差别很大的原因是递归的本质.lambda不存储其值,当计算10的值时,它会重新计算3次超过20次的值.在散列中,可以存储并保存该值以供稍后使用.