in reply to Re: quickness is not so obvious
in thread quickness is not so obvious

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)

Replies are listed 'Best First'.
Re^3: quickness is not so obvious (Dynamic Programming)
by LanX (Saint) on Jan 23, 2015 at 23:03 UTC
    > 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.

[reply]
Re^3: quickness is not so obvious
by GrandFather (Saint) on Jan 24, 2015 at 22:15 UTC

    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
[reply]

      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.

[reply]
[d/l]
[select]

In Section Meditations