Re: Soliciting criticism of memoize function
[
Date Prev][
Date Next][
Thread Prev][
Thread Next]
[
Date Index]
[
Thread Index]
- Subject: Re: Soliciting criticism of memoize function
- From: "Patrick Donnelly" <batrick.donnelly@...>
- Date: 2008年5月17日 01:29:31 -0600
On Sat, May 17, 2008 at 12:12 AM, Mark Hamburg <mark_hamburg@baymoon.com> wrote:
> Some issues to deal with in getting a generic memoize to work correctly:
>
> 1. Do you need to support memoization for f( nil )? If so, you potentially
> need to handle this separately (but see below).
>
> 2. Do you handle nil results from f correctly? Efficiently?
> ...
That's a little overly complicated, you can deal with it like this
(using my previous example):
do
local FUNC = {}; -- key holder
local NIL = {}; -- nil key
local NaN = {} -- NaN
local mt = {
__mode = "k",
__index = function(t, k)
if k == nil then
if t[NIL] then return t[NIL] end
t[NIL] = t[FUNC](k);
return t[NIL];
elseif k ~= k and type(k) == "number" then
if t[NaN] then return t[NaN] end
t[NaN] = t[FUNC](k);
return t[NaN];
else
t[k] = t[FUNC](k);
return t[k];
end
end
};
function memoize (f)
-- f must take at most one argument and return at most one result
local cache = setmetatable({[FUNC] = f}, mt)
return function (x, ...)
assert(select('#', ...) == 0) -- cache works with at most one arg
return cache[x];
end
end
end
On Thu, May 15, 2008 at 6:38 PM, Norman Ramsey <nr@eecs.harvard.edu> wrote:
> > You could also [use the __index metamethod instead of testing for nil]
>
> I like this idea; I hope my colleague will like it as well. It makes
> the code a little cleaner and the 'fast path' (a hit in the cache)
> will be a little faster. But notice it's even nicer if you just
> capture the function lexically:
I noticed this, but I wanted to keep the metatable outside of the
memoize function. This is of course up to you (make a new metatable
for each memoized function or not).
Cheers,
--
-Patrick Donnelly
"One of the lessons of history is that nothing is often a good thing
to do and always a clever thing to say."
-Will Durant