"George Moschovitis" <george.moschovitis / gmail.com> schrieb im Newsbeitrag
news:1096276915.922554.253840 / h37g2000oda.googlegroups.com...
> The cached items are stored in a linked list to facilitate a
> constant(*) time lru algorithm. I could use a separate wrapper object
> to avoid 'polluting' the objects to be cached but I decided that the
> extra object creation (and related gc strain) is not justified.

I beg to differ.  Modifying objects that are put into any kind of
container to implement the container's functionality is a major design
sin.  All sorts of unforeseen problems can arise from this that are
difficult to track down since nobody expects this (if it's done
automatically).  You're likely to run into name clashes and such.  No
single container implementaion I know does this.

If you want to spare the object allocation (which is perfectly reasonable
for performance reasons) you better look out for other ways to do this.
Using an Array as list storage comes to mind.  It's not too difficult to
move elements in an Array around (look at Array#slice!) and it'll be
rather fast I guess.  Still I recommend to first implement the LRU cache
strightforward and then measure performance of alternatives against the
"default" implementation.

Btw another option is to recycle list elements in a local storage.
Usually it's sufficient to cache a single spare linked list element since
the size of the LRU cache is bounded and after you reach the limit you
only exchange elements in the cache.

Kind regards

    robert