• Open Menu Close Menu
  • Apple
  • Shopping Bag
  • Apple
  • Mac
  • iPad
  • iPhone
  • Watch
  • TV
  • Music
  • Support
  • Search apple.com
  • Shopping Bag

Lists

Open Menu Close Menu
  • Terms and Conditions
  • Lists hosted on this site
  • Email the Postmaster
  • Tips for posting to public mailing lists
Best way to implement LRU cache?
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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


  • Prev by Date: Spotlight or some other way!
  • Next by Date: Re: Re: Keys down while dragging
  • Previous by thread: Re: Spotlight or some other way!
  • Next by thread: Best way to implement LRU cache?
  • Index(es):
    • Date
    • Thread