Fibonacci is one of these theoretical problems which need large computation where implementation matters.

But in real life you can approximate the result with a certain accuracy.

So why should I need more than 10 digits of fib (100) if I ever need fib(100) ?

Thanks a lot for your reply.
Without going into too much detail about algorithms or optimizers, the reflection was precisely about the subtle world to do things, do things right and make things better.

In detail, in my case, from a list of files (I did not need to open them) what occupy time were obviously the queries to a database on another server.
Cheer

Hmm, my personal feeling is that if you use Memoize and see a dramatic performance boost when using recursive functions like this, then you really need to rethink your algorithm as there is very likely a much better solution

(To be fair, I suspect this is not always true, however it is absolutely worth investigating, especially if the trade off in memory utilisation is particularly expensive)

> then you really need to rethink your algorithm as there is very likely a much better solution

I doubt this, I've done some branch-and-bound implementations in the past which searched recursively through a graph and it was crucial for speed to see if a partial solution was already calculated.

Some graph search algorithms avoid memoizing by ordering the input nodes (thus avoiding duplications) In aforementioned cases this wasn't possible at all!

Cheers Rolf

PS: Je suis Charlie!

update

for instance see wikipedia Dynamic_programming

The dynamic programming approach seeks to solve each subproblem only once, thus reducing the number of computations: once the solution to a given subproblem has been computed, it is stored or "memo-ized": the next time the same solution is needed, it is simply looked up. This approach is especially useful when the number of repeating subproblems grows exponentially as a function of the size of the input.

How do you justify spending even five minutes thinking about how to improve the algorithm when you can solve the issue in 30 seconds and two lines of code? Of course after you've sent 30 seconds and found that the problem isn't solved, then it's time to think about smarter ways to approach the problem.

I know where you are coming from. Tricks like Memoize feel like cheating. But if it gets the job done and keeps getting it done then it's probably the right solution.

Perl is the programming world's equivalent of English

Its not so much that it feels like cheating, its more the impact of a module like Memoize might have on the underlying system that concerns me. It is entirely possible for an inexperienced developer to build a program that runs entirely fine on their test system, however on a production system is far too memory hungry and causes more problems than it solves.

Yes, I am aware that Memoize gives you options to limit the memory footprint, however that then trades off against the performance boost (and quite possibly entirely negates it)

So yes, in my job where I regularly deal with data sets that can easily fry servers with over 100GB of RAM, I can and do justify spending time finding the most efficient algorithm I possibly can and avoid using memory hungry workarounds such as Memoize. Then again, we spend a lot of time doing research for every aspect of our systems, as the more efficient and faster they are, the more productive (and therefore more valuable) they are.

At the end of the day though, everyones environment is different and likewise the development focus and priorities are different.

$ time perl -e '
print fibo(99);
{
  my @cache;
  sub fibo {
    my $num = shift;
    unless (defined $cache[$num]) {
      if ($num < 3) {
         $cache[$num] = 1; 
      } else { 
         $cache[$num] = fibo($num-1) + fibo($num-2);
      }
    }
    return $cache[$num];
  }
}
'
2.18922995834555e+20
real    0m0.036s
user    0m0.000s
sys     0m0.031s
[download]

Laurent_R:

Yeah, I know. I used the recursive method on purpose just 'cause it was easy and I was demonstrating recursion to a beginner. (If I recall correctly, I used the fibonacci series because it was even uglier than the traditional factorial example of recursion.) If I was actually interested in the fibonacci numbers (I don't recall actually ever needing them for anything), I'd've just created them in a loop, something like:

my @vals = (1, 1);

 . . .

sub fibo {
    my $num = (shift)-1;
    while ($#vals < $num) {
        push @vals, $vals[-1] + $vals[-2];
    }
    return $vals[$num];
}
[download]

...roboticus

When your only tool is a hammer, all problems look like your thumb.

Yeah, when I went to college/university to start to take IT courses, I was already a self-trained autodidact developer, programming in Basic, Fortran, Pascal, C and a couple of blends of assembly, though really not very advanced in any of these languages. I had written mostly spaghetti code, and I had only started to learn what was called then structured programming at least in Pascal and C (although the ideas of structures programming had been around already for many years).

I knew how to write a factorial or a fibonacci function in an imperative loop form, but, because of that, I had probably more problems than my mates to grasp recursion, because it seemed so much more complicated than doing a simple loop. I worked through the recursion assignments, but was not convinced that it could be useful for anything.

It is only later, when working on various types of linked-lists, trees and other similar data structures, that I started to really understand how recursion could make code much simpler and that I really adopted this way of thinking.

In brief, I found that the fact and fibo classical examples of recursion did not work very well in pedagogical terms, at least not for me (and at least with traditional procedural languages). Still today, I would most probably write a fact function as a loop, and I do not see any reason to write a fibo function for anything else than an academic example, but if I needed that, I would also probably do it as a simple loop.

Calculating the greatest common divisor of two numbers is the only classical academic example that I know where recursion starts to make really sense (simpler solution) and which could be moderately useful in real life problems. But when it comes to following a linked_list, traversing a directory tree on a hard disk or parsing a tree of possible actions in an operational research problem or in a game analysis, then recursion often shines, because it can really lead to much simpler code.

Back to the original subject, the Memoize module is beautiful and incredibly efficient (and also mind enlightening), thank you MJD for it, and there many cases where it can be useful. But there are a number of other cases where I am using the idea of caching data in problems where that module could not help. The Schwartzian transform technique is just an example of such data caching in a different context.

Je suis Charlie.