Hashes gegen Lambdas

Question

Ich habe zwei Beispiele gefunden, die sich sehr ähnlich waren, um Fibonacci-Zahlen zu finden:

• 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 

Ich habe schon früher sowohl Hashes als auch Lambdas in Ruby verwendet, aber nicht auf diese Weise. Dies ist eher eine Möglichkeit, eine Funktion zu speichern:

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

1. Kannst du ausführlich erklären, wie das funktioniert? Verwendet dies Rekursion?
2. Was sind die Unterschiede zwischen Hashes wie diesem und Lambdas?

Answer 1

Ja, es verwendet Rekursion. Wenn wir uns den Code in den {}-Klammern ansehen, können wir die Antwort herausfinden. Fangen wir an, uns den Hash anzusehen. Die Werte nach dem neuen Schlüsselwort sind die Standardwerte. Ein Wert, der zugewiesen wird, wenn der Wert nicht bereits im Hash existiert.

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

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

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

Also wenn wir deklarieren

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

sagen wir im Grunde - Erstelle einen neuen Hash mit einem Standardwert. Wenn wir nach einer Zahl (x) kleiner oder gleich zwei fragen, gib einfach die Eingabe (x) zurück. Andernfalls gib uns die Summe der Wörterbuchwerte, wo der Schlüssel x-1 und x-2 ist. Im Grunde der Fibonacci-Algorithmus. Wenn x-1 und x-2 nicht existieren, führt er den gleichen Code erneut aus, bis die beiden Grundwerte 1 und 2 sind.

Der Unterschied zwischen den beiden Ansätzen besteht darin, dass der Hash die Werte speichert (in einem Hash...). Dies kann in einigen Fällen einen großen Vorteil darstellen. Jedes Mal, wenn das Lambda aufgerufen wird, muss es die Werte für alle Zahlen unter dem aufgerufenen Wert neu berechnen.

# Lassen Sie uns einen Zähler erstellen, um die Anzahl der Aufrufe des Lambdas zu verfolgen.
# Bitte verwenden Sie in echtem Code keine globalen Variablen. Ich bin hier nur faul.
@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 wurde 57290 Mal aufgerufen!

@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
# Nur 21 Mal aufgerufen!

Der Grund für den großen Unterschied in den Aufrufen liegt in der Natur der Rekursion. Das Lambda speichert seine Werte nicht und wenn der Wert für 10 berechnet wird, berechnet es den Wert für 3 mehr als 20 Mal neu. Im Hash kann dieser Wert gespeichert und für später abgerufen werden.

Answer 2

Im ersten Fall definieren Sie eine Rekursion, die rekursiv aufgerufen wird.

Im Fall des Hashes werden die Werte ebenfalls rekursiv berechnet, aber gespeichert und dann zum Abrufen des Ergebnisses verwendet.

• Lambda

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

• 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}

In einem Fall hinterlassen Sie keine Speicherbelastung, während der Hash weiterhin den berechneten Wert speichert. Es hängt also davon ab, was Sie brauchen.

Wenn Sie fibonacci[6] noch einmal abrufen müssen, wird das Lambda das Ergebnis neu berechnen, während der Hash Ihnen das Ergebnis sofort gibt, ohne die Berechnungen erneut durchzuführen.

Answer 3

Was sind die Unterschiede zwischen Hashes wie diese und Lambdas?

Lambdas und Hashes haben nichts gemeinsam. Deine Frage ist wie zu fragen:

Was sind die Unterschiede zwischen Methoden und Arrays?

Es ist einfach so, dass Hashes einen Standardwert für einen nicht existierenden Schlüssel angeben können:

h = Hash.new(10)

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

--output:--
2
10 

Hashes bieten auch eine Möglichkeit, den Standardwert dynamisch festzulegen: Du kannst einen Block angeben. Hier ist ein Beispiel:

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}

Wenn du auf einen nicht existierenden Schlüssel zugreifst, wird der Block aufgerufen und der Block kann tun, was auch immer du willst. Also hat jemand clever herausgefunden, dass du eine Hash erstellen und einen Standardwert angeben kannst, der Fibonacci-Zahlen berechnet. So funktioniert es:

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

Das erstellt die Hash h, die eine Hash ohne Schlüssel oder Werte ist. Wenn du dann schreibst:

puts h[3]

...ist 3 ein nicht existierender Schlüssel, also wird der Block mit den Argumenten h und 3 aufgerufen. Der else-Zweig im Block wird ausgeführt, was dir gibt:

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

oder:

h[2] +  h[1]

Aber um diese Aussage zu bewerten, muss Ruby zuerst h[2] bewerten. Aber wenn Ruby h[2] in der Hash nachschlägt, ist der Schlüssel 2 nicht existent, also wird der Block mit den Argumenten h und 2 aufgerufen, der dir gibt:

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

oder:

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

Um diese Aussage zu bewerten, muss Ruby zuerst das erste h[1] bewerten und wenn Ruby versucht, h[1] in der Hash nachzuschlagen, ist 1 ein nicht existierender Schlüssel, also wird der Block mit den Argumenten h und 1 aufgerufen. Diesmal wird der if-Zweig ausgeführt, wodurch dies passiert:

 h[1] = 1

und 1 wird als Wert von h[1] zurückgegeben, was dir dies gibt:

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

Dann sucht Ruby h[0] nach und weil 0 ein nicht existierender Schlüssel ist, wird der Block mit den Argumenten h und 0 aufgerufen und der if-Zweig wird ausgeführt und führt dies aus:

h[0] = 0

und 0 wird als Wert von h[0] zurückgegeben, was dir dies gibt:

(1 + 0)        + h[1]

Dann sucht Ruby h[1] in der Hash und dieses Mal existiert der Schlüssel 1 und hat den Wert 1, was dir gibt:

(1 + 0)        + 1

Und das ergibt 2, also wird h[3] gleich 2 gesetzt. Nachdem h[3] aufgerufen wurde, erhältst du diese Ausgabe:

puts h[3]
p h

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

Wie du sehen kannst, sind die vorherigen Berechnungen alle im Hash zwischengespeichert, was bedeutet, dass diese Berechnungen nicht erneut für andere Fibonacci-Zahlen durchgeführt werden müssen.