3 ms·

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

• psychoslave 3y ago
  Wouldn't you get the same result using memoization idiomatic syntaxes? k[v] ||= k[v-1] + k[v-2]
  • devoutsalsa 3y ago
    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 :)
  • vidarh 3y ago
    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
• oddx 3y ago
  But caching doesn't required here. Hash.new calls block only if value isn't initialialized.
  • devoutsalsa 3y ago
    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.
    • deleted 3y ago
      [deleted]
    • sinkwool 3y ago
      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.
      • devoutsalsa 3y ago
        The caching makes it faster the trade off being more using more memory. I just wanted to see if it’d work.