473,700 Members | 2,582 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

How to memoize functions?

I would like to memoize (I think I've got that right) a collection of
functions for a project I'm working.

<Aside for those not familiar with memoizing functions:>

Given:

def foo(a,b,c):
return <result of large ugly computation>

Memoization of foo would look like:

def foo(a,b,c):
if <this set of arguments has already been handled>
return <result of prior computation>
else
<do large ugly computation>
<save result>
return <result>

</Aside>

The obvious way to memoize a function would be to keep a dictionary with
keys being tuples (or maybe dictionaries) of previous argument lists
and values being the results of the previous computations.

Unfortunately, this will really mess up garbage collection, since
objects that are arguments could never be collected. Something like
weakref.WeakKey Dictionary seems to be the obvious solution. However, a
WeakKeyDictiona ry won't work since it can't use a tuple as a key, and
wouldn't do the right thing, even if it could.

The only solution I've got so far is to implement a new class, imitating
WeakKeyDictiona ry. I started down this road, but the implementation
started getting a little involved, since I needed two dictionaries, one
for the argument list -> result mapping and one to keep track of which
objects appear in which argument lists (since an argument tuple must be
deleted when _any_ of its arguments becomes garbage).

So ... does anyone have any suggestions and/or has anyone already done
something like this (I couldn't find anything in the cookbook at
ActiveState).

Thanks in advance, Chris

Jul 18 '05 #1
3 4211
Le Thu, 26 Jun 2003 16:29:07 -0400, Chris Reedy a écrit :
The obvious way to memoize a function would be to keep a dictionary with
keys being tuples (or maybe dictio naries) of previous argument lists
and values being the results of the previous computations.

Unfortunately, this will really mess up garbage collection, since
objects that are arguments could never be collected.


first I must say that my answer is probably completely stupid.

however why would you want to use the original arguments tuple as a key ?

depending on the computational intensity of your original function, why
not compute some sort of hash (like an hex md5sum) on all the arguments
(converted to strings and concatenated) ?

this way your original arguments would still be garbage collectable (well,
at least I suppose), since only the hash would be used for the key.

again, it may be stupid, I don't know python internal enough

hth

Jerome Alet
Jul 18 '05 #2
The argument tuple is only "materializ ed" for a moment (it disappears
after the called function returns, if it was taken by *args, or else
before the first line of the function if it was taken by named args).
It will disappear from a weakkeydict immediately as a result.

The common memoize, written here using nested scopes, never trims old
values from the dictionary:
def memoize(f):
d = {}
def g(*args):
if not d.has_key(args) :
d[args] = f(*args)
return d[args]
return g
You could make d be a cache of limited size with code like
if not d.has_key(args) :
if len(d) > 1000:
d.pop() # XXX
d[args] = f(*args)
the XXX line removes "some key" from the dictionary. The actual item is
not specified, but turns out to have some relationship to the hash value
of args. This may or may not be acceptable to you. Otherwise, you might
implement a true pseudorandom replacement algorithm, or the standard LRU,
or LFU. These may require that you maintain a heap or other auxiliary
list (corresponding to the keys) to achieve O(1) for the "remove an old
memoized value" code.

I just think weakrefs are not the solution to this problem...

Jeff

Jul 18 '05 #3
Jerome Alet wrote:
Le Thu, 26 Jun 2003 16:29:07 -0400, Chris Reedy a écrit :

The obvious way to memoize a function would be to keep a dictionary with
keys being tuples (or maybe dictio naries) of previous argument lists
and values being the results of the previous computations.

Unfortunately , this will really mess up garbage collection, since
objects that are arguments could never be collected.

first I must say that my answer is probably completely stupid.

however why would you want to use the original arguments tuple as a key ?


Actually, I chose that just because it was the most obvious. The next
choice was a tuple of the ids of the arguments ...
depending on the computational intensity of your original function, why
not compute some sort of hash (like an hex md5sum) on all the arguments
(converted to strings and concatenated) ?
This is certainly a possibility. However ...
this way your original arguments would still be garbage collectable (well,
at least I suppose), since only the hash would be used for the key.


That's true. Unfortunately, that misses the other half of the problem
(which, admittedly, I didn't mention) which is that I would also like to
be able to collect the results of the function, which could be complex
data structures, as well as the arguments (which could be other
instances of the same complex structures).

Chris

-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----== Over 80,000 Newsgroups - 16 Different Servers! =-----
Jul 18 '05 #4

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

5
3340
by: hokiegal99 | last post by:
A few questions about the following code. How would I "wrap" this in a function, and do I need to? Also, how can I make the code smart enough to realize that when a file has 2 or more bad charcters in it, that the code needs to run until all bad characters are gone? For example, if a file has the name "<bad*mac\file" the program has to run 3 times to get all three bad chars out of the file name. The passes look like this:
3
4012
by: Michael Hohn | last post by:
Hi, under python 2.2, the pickle/unpickle sequence incorrectly restores a larger data structure I have. Under Python 2.3, these structures now give an explicit exception from Pickle.memoize(): assert id(obj) not in self.memo I'm shrinking the offending data structure down to find the problem
13
2351
by: km | last post by:
Hi all, was going thru the new features introduced into python2.4 version. i was stuck with 'decorators' - can someone explain me the need of such a thing called decorators ? tia KM
2
3788
by: Bryan Olson | last post by:
The current Python standard library provides two cryptographic hash functions: MD5 and SHA-1 . The authors of MD5 originally stated: It is conjectured that it is computationally infeasible to produce two messages having the same message digest. That conjecture is false, as demonstrated by Wang, Feng, Lai and Yu in 2004 . Just recently, Wang, Yu, and Lin showed a short- cut solution for finding collisions in SHA-1 . Their result
7
5898
by: Tim ffitch | last post by:
Hi I have created a VB dll file that contains common functions I use across various projects in VB, Access and Excel. Rather than have to code the functions in each I decided to use the dll route. The problem being that I can't call these functions from the query designer in Access. I decided that I would try the route of declaring the functions from the dll file the same way you would for the Windows API. Access then complains that...
23
4006
by: Timothy Madden | last post by:
Hello all. I program C++ since a lot of time now and I still don't know this simple thing: what's the problem with local functions so they are not part of C++ ? There surely are many people who will find them very helpfull. gcc has them as a non-standard option, but only when compiling C language code, so I'm afraid there might be some obscure reason why local functions are not so easy to be dealt with in C++, which I do not yet know.
11
2510
by: thattommyhallll | last post by:
im plugging away at the problems at http://www.mathschallenge.net/index.php?section=project im trying to use them as a motivator to get into advanced topics in python. one thing that Structure And Interpretation Of Computer Programs teaches is that memoisation is good. all of the memoize decorators at the python cookbook seem to make my code slower. is using a decorator a lazy and inefficient way of doing memoization? can anyone point...
2
1335
by: ankitks.mital | last post by:
I saw example of memoize function...here is snippet def memoize(fn, slot): def memoized_fn(obj, *args): if hasattr(obj, slot): return getattr(obj, slot) else: val = fn(obj, *args) setattr(obj, slot, val) return val
7
3967
by: Immortal Nephi | last post by:
My project grows large when I put too many member functions into one class. The header file and source code file will have approximately 50,000 lines when one class contains thousand member functions. Is it normal how C++ Compiler can compile large class without any problem? Didn't C++ Compiler have rules to limit the number of member functions? One big object has complex operations how member variables and member functions can be...
0
8728
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
8926
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
7813
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
1
6563
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
5903
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
4404
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
0
4659
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
2
2392
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
2030
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.