From: Daniel Hoppe [mailto:[EMAIL PROTECTED]]
> My problem is that my
> implementation for the longest interim is quite inefficient
> (I keep the keys
> in a LinkedList where they are (re)inserted at the first position on
> access, the times I profiled for this (esp.
> linkedList.remove()) makes me
> doubt that my approach is smashing so far...). Dropping the
> oldest value
> object is straightforward and fast as I do never need to
> reorder the keys.
> Better approaches on this are more than welcome!
It may well be faster to timestamp the entries, and then scan for
the oldest when you need to free up space in the cache.
If you free 1 entry at a time, and the cache is full, then:
Insert is : O(n) [find oldest entry]
+ O(replace) [which is probably O(1)]
Get is : O(get) [depending on your keying mechanism,
it's probably also O(1)]
+ O(1) [update timestamp]
So, probably you're looking at O(n) inserts and O(1) gets
If you reorder on use, you have:
Insert is : O(1) [oldest is at end of list]
+ O(1) [append to end]
Get is : O(1) [get by key]
+ O(?) [this could be O(1) in a fast list,
but then your "get by key" is probably
not going to be O(1) any more, in your
ase it seems to be O(n) ]
So, probably it's O(1) inserts and O(n) gets.
If those are the right numbers (and it depends on the
implemenation of the "list"), then the former should be faster
since inserts are going to be less frequent than gets.
