Hacker News Reader

Comment by nix-zarathustra | Hacker News Reader

One of the most beautiful things in Ruby that I have ever seen is this fibonacci code.

  fib = Hash.new do |k, v|
    next 1 if v == 0 || v == 1
    k[v-1] + k[v-2]
  end

View on HN

With caching...

   fib = Hash.new do |k, v|
     next 1 if v == 0 || v == 1

     unless k.key? v
       k[v] = k[v-1] + k[v-2]
     end

     k[v]
   end

Wouldn't you get the same result using memoization idiomatic syntaxes?

k[v] ||= k[v-1] + k[v-2]

No, because that is equivalent to

    k[v] || (k[v] = k[v-1] + k[v-2])

And that first k[v] (unlike k.key?(v)) will trigger the Hash.new block again, so it'll recurse until it runs out of stack. But neither check is necessary, because the Hash.new block will only ever get called if k.key?(v) is false.

If you want a more compact version, you could do:

    fib = Hash.new do |k,v|
      next 1 if v == 0 || v == 1
      k[v] = k[v-1] + k[v-2]
    end

That was the first thing I tried, but it blew the stack :) You can still blow the stack if you pick a number that's too high, like k[20000] or something. But if you pick a lower number & cache that, then you can (eventually) call a higher number without blowing the stack. This recursive approach is a horribly inefficient algorithm anyway, so I don't think it's worth optimizing :)

But caching doesn't required here. Hash.new calls block only if value isn't initialialized.

I just did it for fun. This particular recursive approach is super slow for numbers of nontrivial size, so I was just curious if I could even make the caching work in the block. It's not worth optimizing a suboptimal query when a more efficient option is available anyway.

You don't need the `unless k.key? v` guard. The `Hash.new` block only gets called when the key is not present in the hash.

The caching makes it faster the trade off being more using more memory. I just wanted to see if it’d work.

Let’s make it a one liner :D

fib = Hash.new {|hash, key| hash[key] = key < 2 ? key : hash[key-1] + hash[key-2] }

Example: fib[123] # => 22698374052006863956975682

Makes use of memoization.

Yes, I was going off of memory and thought that it was memoising it, but I made a mistake and fixed it.

  fib = Hash.new do |k, v|
    next 1 if v == 0 || v == 1
    k[v] = k[v-1] + k[v-2]
  end

I like yours better though, it seems a lot simpler with the less than 2 check.

You can also recursively define fib as a lazy sequence that is the pairwise sum of fib and fib shifted by one. (Clojure, from Rosetta Code).

    (def fib (lazy-cat [0 1] (map + fib (rest fib))))

    => (take 10 fib)
    (0 1 1 2 3 5 8 13 21 34)


    Explanation:

       0 1 1 2 3 5   ;  this is fib
    +  1 1 2 3 5 8   ;  this is (rest fib) 
    ---------------
       1 2 3 5 8 13  ;  this is (map + fib (rest fib))
                     ;  and the sequence needs to be initialized with (lazy-cat [0 1] ...

Or an Ackermann:

    A = Hash.new { |a,(m,n)| a[[m,n]] = m==0 ? n+1 : n==0 ? a[[m-1,1]] : a[[m-1, a[[m, n-1]]]] }

    A[[3,4]] #=> 125

    A.inspect #=> ... long

However, the application utility of a self-populating lazily-evaluated lookup structure goes further. A hash with a default function works great as a simple caching wrapper for all manner of results, for example when talking to slow or fine-grained APIs.

Reply on news.ycombinator.com