哈希表与Lambda函数

Question

我找到了两个看起来非常相似的示例，用于查找斐波那契数列：

• Lambda

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

• Hash

  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之间有什么区别？

- Tyler

Answer 1

是的，它使用递归。如果我们查看{}括号中的代码，我们就可以找出答案。让我们开始看哈希表。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的值时，它将重新计算20多次的3的值。在哈希表中，该值可以被存储并保存供以后使用。

- hirolau

Answer 2

在第一种情况下，您正在定义一个将被递归调用的递归。在哈希的情况下，值也将被递归计算，但存储并随后访问以提供结果。

• Lambda

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

• Hash

  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}
  

在某些情况下，使用lambda表达式不会在内存中留下任何足迹，而哈希将继续保留计算出的值。因此这取决于您需要什么。

如果您需要再次访问fibonacci[6]，lambda将重新计算结果，而哈希将立即给出结果，无需重新计算。

- Cyril Gandon

Answer 3

这样的哈希表和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 是一个不存在的键，因此块使用参数 h 和 3 被调用。 块中的 else 子句执行，给出：

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

或者：

h[2] +  h[1]

但是要评估该语句，Ruby必须首先评估h[2]。 但是当Ruby在哈希中查找h [2]时，键2是一个不存在的键，因此调用块并传递参数h和2，从而得到：

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

或者：

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

为了评估该语句，Ruby 首先必须评估第一个 h[1]，当 Ruby 尝试在哈希表中查找 h[1] 时，1 是一个不存在的键，因此将使用参数 h 和 1 调用块。这次 if 分支执行，导致发生以下情况：

 h[1] = 1

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

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

然后 Ruby 查找 h[0]，因为 0 是一个不存在的键，所以调用块并传入参数 h 和 0，if 子句执行并执行以下操作：

h[0] = 0

并且h[0]的值为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}

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

- 7stud