Function Memoization

re: Function Memoization

Heath Stewart — Fri, 26 Jan 2007 19:41:19 GMT

Wow, someone else that has heard of Robo Rally. That is a fun game. Have fun with your project.

re: Function Memoization

damien morton — Sun, 28 Jan 2007 06:38:55 GMT

Theres a great article on using memoisation to speed up Conways Game Of Life here: http://www.ddj.com/dept/ai/184406478

The basic idea is to treat the change in state of the board as a function from one moment in time to the next. By recursively subdividing the board, and memoising the state transitions, a lot of computation can be re-used. The same idea is then applied in time, by memoizing entire sequences of state transitions. The result is speedups of the order of a million-fold.

re: Function Memoization

Judah — Mon, 29 Jan 2007 01:38:29 GMT

Thanks for the article, Wes. I enjoyed the Channel 9 video too, very informative. Gets me excited about LINQ. :-)

FWIW, it's possible to do memoization today in C# 2. It's a bit more verbose without lambdas, of course, but it's do-able nonetheless. See this post for Sriram's how-to:

http://blogs.msdn.com/sriram/archive/2006/01/15/lisp_is_sin.aspx

re: Function Memoization

Alex James — Mon, 29 Jan 2007 03:53:26 GMT

Great learning resource = Wes Dyer...

Mr

James Jones — Mon, 29 Jan 2007 16:12:23 GMT

Thanks for the ongoing functional stuff ...

I was wondering if you had any opinions on how best to approach ensuring such functions are thread safe?

re: Function Memoization

wesdyer — Mon, 29 Jan 2007 22:41:30 GMT

Damien:

That is fascinating. I love the game of life and was not aware of that speed up. Thanks for the link.

Judah:

You are right. But I would add that not only is it more verbose, it is also uglier and doesn't include type inference.

James Jones:

Good question. I'll prep a post about that.

re: Mr

wesdyer — Wed, 31 Jan 2007 02:41:14 GMT

James:

As I was thinking about what to write concerning thread safe functions, it seemed that nothing would be particularly helpful without a little more context concerning what problems you are facing.

Could you describe the specific problems that you are having?

If you care just to learn general strategies then I could always discuss a few, but this is a topic about which we could write whole books.

Is C# becoming a functional language?

David's blog — Wed, 31 Jan 2007 13:31:21 GMT

Is C# becoming a functional language?

David's blog — Wed, 31 Jan 2007 13:47:13 GMT

Is C# becoming a functional language?

David's blog — Wed, 31 Jan 2007 14:29:35 GMT

re: Function Memoization

James Jones — Thu, 01 Feb 2007 17:09:35 GMT

Hi Wes

Thank you for the feedback .. it's appreciated.

I'm very much an OOP minded programmer who is trying very hard to appreciate and adopt a more functional style of programming that will inherently promote thread neutral development. The idea being that my applications scale naturally on multi-processor machines into the future.

I'm currently working on a system, part of which involves delegating well known interface type instantiation to a factory class. What I'd really like is a way of promoting Singleton type usage of types that do not necessarily implement that pattern themselves. It struck me that your memorize function could be just the ticket to this ... kindof a surrogate singleton.

Thank you for taking the time to respond and please keep up the excellent posts.

James

Community Convergence XX

Charlie Calvert's Community Blog — Fri, 02 Feb 2007 10:52:40 GMT

Welcome to the twentieth Community Convergence. I'm Charlie Calvert, the C# Community PM, and this is

Community Convergence XX

Charlie Calvert's Community Blog — Fri, 02 Feb 2007 11:10:36 GMT

Welcome to the twentieth Community Convergence. I'm Charlie Calvert, the C# Community PM, and this is

re: Function Memoization

wesdyer — Fri, 02 Feb 2007 20:41:39 GMT

James:

Probably the easiest way to make Memoize thread-safe is to put a lock on map. Like so:

public static Func<A, R> Memoize<A, R>(this Func<A, R> f)

{

var map = new Dictionary<A, R>();

return a =>

{

lock (map)

{

R value;

if (map.TryGetValue(a, out value))

return value;

value = f(a);

map.Add(a, value);

return value;

}

};

}

This will ensure that the function that is being memoized will only be run once for each set of distinct arguments.

In my example of the RoboRally game, I actually used function memoization to act as "surrogate singleton". It isn't really a singleton since there can be one instance per factory instance (unless the factory is static). But that is exactly what I wanted.

Baby Names, Nameless Keys, and Mumbling

Yet Another Language Geek — Sun, 11 Feb 2007 09:49:39 GMT

Baby Names I recently finished reading Freakonomics . It is a fascinating book about a number of strange

re: Function Memoization

Kiryl Batsiukov — Wed, 14 Feb 2007 01:13:36 GMT

Great!

I finaly understood why was Lambda Calculus included in my Informatics Lectures at the university:)

Thanx for your post

re: Function Memoization

Romain Verdier — Sat, 03 May 2008 02:04:56 GMT

Pingback from :

http://codingly.com/2008/05/02/optimisation-des-invocations-dynamiques-de-methodes-en-c/