473,320 Members | 2,145 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

dictionary that discards old items

Hi folks,

I need a collection class that behaves like a dictionary but when it
reaches 'n' items it discards the oldest item so that the length never
goes above 'n'. (Its for caching search results)

I have a vague memory of a module that does this, but I cant remember
where I read about it. Can anyone enlighten me?
Regards,

Will McGugan

--
http://www.willmcgugan.com
"".join({'*':'@','^':'.'}.get(c,0) or chr(97+(ord(c)-84)%26) for c in
"jvyy*jvyyzpthtna^pbz")
Jul 21 '05 #1
10 1395
Will McGugan wrote:
I need a collection class that behaves like a dictionary but when it
reaches 'n' items it discards the oldest item so that the length never
goes above 'n'. (Its for caching search results)

I have a vague memory of a module that does this, but I cant remember
where I read about it. Can anyone enlighten me?


You want a Least Recently Used, or LRU, cache. Here's one:

http://aspn.activestate.com/ASPN/Coo.../Recipe/252524

Google for <LRU python> to find others.
--
Michael Hoffman
Jul 21 '05 #2
[Will McGugan]
I need a collection class that behaves like a dictionary but when it
reaches 'n' items it discards the oldest item so that the length never
goes above 'n'. (Its for caching search results)

import collections

class Cache(dict):
def __init__(self, n, *args, **kwds):
self.n = n
self.queue = collections.deque()
dict.__init__(self, *args, **kwds)
def __setitem__(self, k, v):
self.queue.append(k)
dict.__setitem__(self, k, v)
if len(self) > self.n:
oldk = self.queue.popleft()
del self[oldk]

# . . .
# make similar modifications to setdefault, __delitem__, fromkeys
# and other mutating methods as needed

# Example
c = Cache(3)
for w in 'the quick brown fox jumped over the lazy dog'.split():
c[w] = w[:1].upper()
print repr(c)

Jul 22 '05 #3
not clear if you want a FIFO, or a LRU on read or write, so for the
non-dictionary component of this, you could also ( (search Cookbook)
|| google) for terms like "ring buffer", "fixed-size cache", um,
"bounded queue", "circular buffer", "deque", there's probably a bunch
of others.

Jul 22 '05 #4
Michael Hoffman wrote:
Will McGugan wrote:
I need a collection class that behaves like a dictionary but when it
reaches 'n' items it discards the oldest item so that the length never
goes above 'n'. (Its for caching search results)

I have a vague memory of a module that does this, but I cant remember
where I read about it. Can anyone enlighten me?

You want a Least Recently Used, or LRU, cache. Here's one:

http://aspn.activestate.com/ASPN/Coo.../Recipe/252524

Google for <LRU python> to find others.


Thanks. I found the one I saw originally in the Python Cookbook. Only
they call it a FIFO cache.

--
http://www.willmcgugan.com
"".join({'*':'@','^':'.'}.get(c,0) or chr(97+(ord(c)-84)%26) for c in
"jvyy*jvyyzpthtna^pbz")
Jul 22 '05 #5
On 7/21/05, Michael Hoffman <ca*******@mh391.invalid> wrote:
Will McGugan wrote:
I need a collection class that behaves like a dictionary but when it
reaches 'n' items it discards the oldest item so that the length never
goes above 'n'. (Its for caching search results)

I have a vague memory of a module that does this, but I cant remember
where I read about it. Can anyone enlighten me?


You want a Least Recently Used, or LRU, cache. Here's one:

http://aspn.activestate.com/ASPN/Coo.../Recipe/252524


http://py.vaults.ca/apyllo.py/514463...44789.92554878
Jul 22 '05 #6
Will McGugan wrote:
You want a Least Recently Used, or LRU, cache. Here's one:

Thanks. I found the one I saw originally in the Python Cookbook. Only
they call it a FIFO cache.


A FIFO cache is different, as gene tani points out. You need to consider
which one it is you want.
--
Michael Hoffman
Jul 22 '05 #7
On 21 Jul 2005 19:29:32 -0700, "Raymond Hettinger" <py****@rcn.com> wrote:
[Will McGugan]
I need a collection class that behaves like a dictionary but when it
reaches 'n' items it discards the oldest item so that the length never
goes above 'n'. (Its for caching search results)

import collections

class Cache(dict):
def __init__(self, n, *args, **kwds):
self.n = n
self.queue = collections.deque()
dict.__init__(self, *args, **kwds)
def __setitem__(self, k, v):
self.queue.append(k)
dict.__setitem__(self, k, v)
if len(self) > self.n:
oldk = self.queue.popleft()
del self[oldk]

# . . .
# make similar modifications to setdefault, __delitem__, fromkeys
# and other mutating methods as needed

# Example
c = Cache(3)
for w in 'the quick brown fox jumped over the lazy dog'.split():
c[w] = w[:1].upper()
print repr(c)


Minor comment: There is a potential name collision problem for keyword n=something,
so what is considered best practice to avoid that? __n or such as the n arg?
def foo(n, *args, **kw): print n, args, kw ... foo(1) 1 () {} foo(n=5) 5 () {} foo(3, n=5) Traceback (most recent call last):
File "<stdin>", line 1, in ?
TypeError: foo() got multiple values for keyword argument 'n'


Regards,
Bengt Richter
Jul 24 '05 #8
[Raymond Hettinger]
class Cache(dict):
def __init__(self, n, *args, **kwds):
self.n = n
self.queue = collections.deque()
dict.__init__(self, *args, **kwds)

[Bengt Richter] Minor comment: There is a potential name collision problem for keyword n=something,
so what is considered best practice to avoid that? __n or such as the n arg?


I don't know what best practice is, but if you want to guarantee to
avoid the name collision, you can write:

def __init__(*args, **kwargs):
self = args[0]
self.n = args[1]
self.queue = collections.deque()
dict.__init__(self, *args[2:], **kwargs)

It's not pretty though. ;)

STeVe
Jul 24 '05 #9
On Sat, 23 Jul 2005 20:07:25 -0600, Steven Bethard <st************@gmail.com> wrote:
[Raymond Hettinger]
class Cache(dict):
def __init__(self, n, *args, **kwds):
self.n = n
self.queue = collections.deque()
dict.__init__(self, *args, **kwds)


[Bengt Richter]
Minor comment: There is a potential name collision problem for keyword n=something,
so what is considered best practice to avoid that? __n or such as the n arg?


I don't know what best practice is, but if you want to guarantee to
avoid the name collision, you can write:

def __init__(*args, **kwargs):
self = args[0]
self.n = args[1]
self.queue = collections.deque()
dict.__init__(self, *args[2:], **kwargs)

It's not pretty though. ;)

Bullet proofing doesn't have to be ;-)
Best solution I've seen yet, thanks.

Regards,
Bengt Richter
Jul 24 '05 #10
[Raymond Hettinger]
class Cache(dict):
def __init__(self, n, *args, **kwds):
self.n = n
self.queue = collections.deque()
dict.__init__(self, *args, **kwds)


[Bengt Richter] Minor comment: There is a potential name collision problem for keyword n=something,
so what is considered best practice to avoid that? __n or such as the n arg?


One solution is to drop the *args and **kwds part of the __init__() API
for the subclass. For a cache class, it doesn't make sense that you
would know all of the values when the instance is first created. If
the need arises, the update() method will suffice:

class Cache(dict):
def __init__(self, n):
self.n = n
dict.__init__(self)
. . .
The __n form doesn't get name mangled so its only advantage is in being
a less likely key.
Raymond

Jul 24 '05 #11

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

Similar topics

1
by: none | last post by:
or is it just me? I am having a problem with using a dictionary as an attribute of a class. This happens in python 1.5.2 and 2.2.2 which I am accessing through pythonwin builds 150 and 148...
4
by: brianobush | last post by:
# # My problem is that I want to create a # class, but the variables aren't known # all at once. So, I use a dictionary to # store the values in temporarily. # Then when I have a complete set, I...
125
by: Raymond Hettinger | last post by:
I would like to get everyone's thoughts on two new dictionary methods: def count(self, value, qty=1): try: self += qty except KeyError: self = qty def appendlist(self, key, *values): try:
5
by: JerryB | last post by:
Hi, I have a dictionary for counting ocurrences of strings in a document. The dictionary looks like this: 'hello':135 'goodbye':30 'lucy':4 'sky':55 'diamonds':239843 'yesterday':4
2
by: jg | last post by:
I was trying to get custom dictionary class that can store generic or string; So I started with the example given by the visual studio 2005 c# online help for simpledictionay object That seem...
3
by: Mark Rae | last post by:
Hi, Is it possible to use a Dictionary<int, stringor even Dictionary<string, stringas the DataSource for a DropDownList directly, i.e. without having to iterate through the the Dictionary's...
1
by: Sam Loxton | last post by:
Hi, I am fairly new to the python language and am trying to sort a nested Dictionary of a Dictionary which I wish to sort by value. The dictionary does not have to be restructured as I only need...
7
by: mmm | last post by:
I found code to undo a dictionary association. def undict(dd, name_space=globals()): for key, value in dd.items(): exec "%s = %s" % (key, repr(value)) in name_space So if i run I get
2
by: uday1302 | last post by:
Hi, I have Listbox(lstgroups) and listview(lstItems). say items in lisbox as Groups and in listview as Items. Each Group should have list of items, when i add an new item to lstitems. it should...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
0
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you

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.