Skip to main content

Best performing Least Used List

5 replies [Last post]
byhisdeeds
Offline
Joined: 2006-01-06

I have a java application that requires me to sample hundereds of image files. To speed things up, I coded a Least Used List of a fixed size, of BufferedImages, that removed the least used entry when it required space for a new entry. I did this by using a priority queue to order a list of usage, as well as a hashmap to access the entries quickly.

it works ok, but I'm looking to optimise it and was wondering if anybody could tell me whether a Least Recently Used alogoritim would serve my purpose just as well. This would probably be faster, as I just keep the most recently accessed entry at the head of the list, and remove the tail when I need space.

Reply viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
fred34
Offline
Joined: 2004-06-19

There's already a class for this exact purpose. Look at LinkedHashMap as of JDK1.4

byhisdeeds
Offline
Joined: 2006-01-06

Thanks. However, do you think that a Least Recently Used cache would provide the same level of caching performance as my current Least Used cache, dropping the least used entry to make space.

spdenne
Offline
Joined: 2006-02-15

The relative performance will be based on the pattern of repeated use of the images, and how many images are in your cache.
A Least Used cache can get some images stuck in it that were used a huge amount in a batch a long time ago.

byhisdeeds
Offline
Joined: 2006-01-06

That's VERY true. Thanks. I iterate through X and Y from 1 to 127 to find images with X_Y.jpg, so the pattern of access is somewhat regular. I'm gonna time both implementations to see what happens.

byhisdeeds
Offline
Joined: 2006-01-06

OK. For my exisitng implementation I get 99.06% hit rate after 10 million requests. When I implement the LRU using the LinkedHashMap I get 100% for the same and more requests. As my access pattern is regular I guess its gonna be better.

Thanks everyone.