3

我发现了两个看起来很接近的例子来寻找斐波那契数：

  • 拉姆达

    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

我以前在 ruby​​ 中使用过哈希和 lambda，但不是这样。这更像是一种存储函数的方式：

if x < 2
  x
else
 fibonacci[x-1] + fibonacci[x-2]
  1. 你能详细解释一下这是如何工作的吗？这是使用递归吗？
  2. 像这样的哈希和 lambda 有什么区别？
4

3 回答 3

9

是的，它使用递归。如果我们查看 {} 括号中的代码，我们可以找出答案。让我们开始看看哈希。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 次。在散列中，这个值可以被存储并保存以备后用。

于 2013-09-11T07:50:27.463 回答
4

在第一种情况下，您正在定义一个将被递归调用的递归。

在散列的情况下，这些值也将被递归计算，但被存储然后访问以给出结果。

  • 拉姆达

    fibonacci = ->(x){ x < 2 ? x : fibonacci[x-1] + fibonacci[x-2] }
fibonacci[6]
fibonacci # => <Proc:0x2d026a0@(irb):5 (lambda)>

  • 哈希

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

在一种情况下，您不会在内存中留下任何足迹，而哈希将继续保留计算值。所以这取决于你需要什么。

如果您需要再访问fibonacci[6]一次，则 lambda 将重新计算结果，而哈希将立即为您提供结果，而无需重做计算。

于 2013-09-11T07:22:27.397 回答
-1

像这样的哈希和 lambda 有什么区别？

lambda 和哈希没有任何共同之处。你的问题就像问：

方法和数组有什么区别？

只是哈希可以为不存在的键指定默认值：

h = Hash.new(10)

h["a"] = 2
puts h["a"]
puts h["b"]

--output:--
2
10

哈希还提供了一种动态指定默认值的方法：您可以提供一个块。这是一个例子：

h = Hash.new do |h, key|
  h[key] = key.length
end

puts h['hello']
puts h['hi']
p h

--output:--
5
2
{"hello"=>5, "hi"=>2}

当您访问不存在的密钥时，将调用该块，并且该块可以做任何您想做的事情。所以有人聪明地发现你可以创建一个哈希并指定一个计算斐波那契数的默认值。下面是它的工作原理：

h = Hash.new do |h, key| 
  if key < 2  
    h[key] = key
  else 
    h[key] = h[key-1] + h[key-2] 
  end
end

这将创建哈希 h，它是一个没有键或值的哈希。如果你然后写：

puts h[3]

...3 是一个不存在的键，因此使用 args h 和 3 调用该块。该块中的 else 子句执行，它为您提供：

h[3-1] + h[3-2]

或者： 

h[2] +  h[1]

但要评估该语句，ruby 必须首先评估 h[2]。但是当 ruby​​ 在哈希中查找 h[2] 时，键 2 是一个不存在的键，因此使用 args h 和 2 调用该块，从而为您提供：

(h[2-1] + h[2-2]) + h[1]

或者： 

(h[1] + h[0])    + h[1]

要评估该语句，ruby 首先必须评估第一个 h[1]，当 ruby​​ 尝试在哈希中查找 h[1] 时，1 是不存在的键，因此使用 args h 和 1 调用块. 这次 if 分支执行，导致这种情况发生：

 h[1] = 1

并且 1 作为 h[1] 的值返回，给你这个：

 (1 + h[0])      + h[1]

然后 ruby​​ 查找 h[0]，因为 0 是一个不存在的键，所以使用 args h 和 0 调用该块，然后执行 if 子句并执行以下操作：

h[0] = 0

并且 0 作为 h[0] 的值返回，给你这个：

(1 + 0)        + h[1]

然后 ruby​​ 在哈希中查找 h[1]，这一次键 1 存在，它的值为 1，给你：

(1 + 0)        + 1

这等于 2，所以 h[3] 设置为等于 2。调用 h[3] 后，您会得到以下输出：

puts h[3]
p h

--output:--
2
{1=>1, 0=>0, 2=>1, 3=>2}

如您所见，之前的计算都缓存在哈希中，这意味着不必为其他斐波那契数再次执行这些计算。

于 2013-09-11T09:14:46.300 回答