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 17:05:44 -0700
Hi.
I'm trying to find a good way to implement an object cache for a 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 this is what
indexOfObject: does). 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 a own double-linked list to eliminate the
indexes problem. 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