Best way to implement LRU cache?
Best way to implement LRU cache?
- Subject: Best way to implement LRU cache?
- From: Daniel Gobera <email@hidden>
- Date: Fri, 27 Oct 2006 11:58:06 -0700
Hi.
I'm trying to find a good way to implement an object cache for my
Core Data-based application. I would like to use the LRU policy, so
the least recently used object is discarded when the cache is full.
Objects are uniquely identified and retrieved by a "name" attribute.
I'll need a way to quickly tell if an object is cached and retrieve
it, so a hash table by "name" would ideally fit here (NSDictionary).
The problem is that a Dictionary is unordered, so there's no way to
know which is the oldest object.
I'm guessing I'll need a second structure, a List. An NSArray would
normally be a good choice here, as it's internally implemented as a
list and allows to remove objects from any part an inexpensively
insert at the beginning or end. The problem here would be to keep
both structures in sync.
When an object is accessed by its "name", I'll need to remove it from
its current array position and insert it in the top again (make it
the most recently used one). But how to find it in the array? I don't
want to linearly traverse it every time. If in the dictionary I keep
a correspondence between "names" and index in the array, I'll need to
update all indexes when an object from the middle of the array is
removed and all subsequent indexes are decreased.
A Java HashList class would be ideal for this, but there's no
equivalent in Cocoa (there's not even a list or queue). I think I'll
have to implement my own. I'll still use an NSDictionary, but instead
of an array, I'll implement my own double-linked list. Does that
sound reasonable? I'm sure this is an old, solved problem, any
suggestions?
Thanks,
Daniel
_______________________________________________
Do not post admin requests to the list. They will be ignored.
Cocoa-dev mailing list (email@hidden)
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden