James Stauffer
From: Greg Nudelman [mailto:[EMAIL PROTECTED]
Sent: Thursday, November 13, 2003 10:51 AM
To: jdjlist
Subject: [jdjlist] Re: LFUCache problem
Wow! Thanks!
Lots of new things to try!! I think this is turning out to be a bigger prject then I thought... Oh, and BTW, does anyone have a good article on the correct way to implement the updater thread? :-)
I was thinking something like:
LFUCache {
boolean performUpdate;
Thread updater(priority LOWEST) {
run() {
sleep for 10 seconds;
if (performUpdate)
resort();
else
sleep for
10 seconds;
}
I'm not sure if I need to catch the interupted exception or make everyone wait for my re-sort... I guess if I do decide to go with a separate thread doing the updating, I might as well forgo the TreeMap altogether and just have an Container[] order; and then do the Collections.sort(order, new Comparator(blah)); I think it is much more efficient then log(n) of the TreeMap, right?
Greg
-----Original Message-----
From: Keats
[mailto:[EMAIL PROTECTED]]
Sent: Thursday, November 13, 2003 7:24 AM
To: jdjlist
Subject: [jdjlist] Re: LFUCache
problem
I think Paul's approach sounds good. Depending on your
requirements, you may
want to reduce the performance hit
by having a separate thread handling the
sort. For
example, you could periodically build a new tree and replace the
old one, or queue up nodes that need to be reinserted.
(Take care that you
do this in a thread-safe
manner.) Since you probably don't need to have the
tree perfectly sorted at all times you don't need to resort on each
access.
Keats
----- Original Message -----
From: "Paul
Franz" <[EMAIL PROTECTED]>
To: "jdjlist"
<[EMAIL PROTECTED]>
Sent: Thursday,
November 13, 2003 6:22 AM
Subject: [jdjlist] Re:
LFUCache problem
> Also, a couple things that should be mentioned:
>
> 1)
The TreeMap does not use the hashCode to sort, it uses the
Comparable
> interface (i.e. the public int
compareTo method) to do its sorting.
> 2) As Spencer has pointed out the sorting is
done at the time of
> insertation. Which means to
solve the problem all you need to do is remove
> the
entry from the TreeMap and then re-insert after the frequency has been
> updated.
>
> Paul Franz
>
>
----- Original Message -----
> From: "Spencer W.
Thomas" <[EMAIL PROTECTED]>
> To: "jdjlist"
<[EMAIL PROTECTED]>
> Sent:
Wednesday, November 12, 2003 9:44 PM
> Subject:
[jdjlist] Re: LFUCache problem
>
>
> > Well, I think your problem is
this: the TreeSet sorts items *as they are
> >
inserted*. Your "get" operation changes the key *after* the items
are
> > inserted, but does nothing to force the
Set to re-sort. You need to
> > remove the
item from the set and reinsert it in order to change the sort
> > order.
> >
> > Another possibility: use a plain Set to store your items, but
when you
> > need to find the LFU, make a TreeSet
from the Set contents. Of course,
> > at
that point, you might as well just scan the whole set looking for the
> > LFU element, because that's O(n) and building the
TreeSet is O(n
> > log(n)), so slower.
> >
> > =S
> >
> >
>
>
> > ---
> > You
are currently subscribed to jdjlist as: [EMAIL PROTECTED]
> > To unsubscribe send a blank email to
> [EMAIL PROTECTED]
> > http://www.sys-con.com/fusetalk
> > To unsubscribe from all mailing lists, click:
> >
>
http://sys-con.com/[EMAIL PROTECTED]
> on.com
>
>
> ---
> You
are currently subscribed to jdjlist as: [EMAIL PROTECTED]
> To unsubscribe send a blank email to
[EMAIL PROTECTED]
> http://www.sys-con.com/fusetalk
> To unsubscribe from all mailing lists, click:
>
http://sys-con.com/[EMAIL PROTECTED]
on.com
>
****************************************************************************
This e-mail, and any attachment, is intended only for the
person or entity to which it is addressed and may contain confidential
and/or privileged material. Any review, re-transmission, copying,
dissemination or other use of this information by persons or entities other than
the intended recipient is prohibited. If you received this in error,
please contact the sender and delete the material from any computer. The
contents of this message may contain personal views which are not the views of
Discovery Communications, Inc. (DCI).
****************************************************************************
---
You are currently subscribed to
jdjlist as: [EMAIL PROTECTED]
To unsubscribe send a
blank email to [EMAIL PROTECTED]
http://www.sys-con.com/fusetalk
To unsubscribe from all mailing lists, click:
http://sys-con.com/[EMAIL PROTECTED]
You are currently subscribed to jdjlist as: [EMAIL PROTECTED]
To unsubscribe send a blank email to [EMAIL PROTECTED]
http://www.sys-con.com/fusetalk To unsubscribe from all mailing lists, click:
http://sys-con.com/[EMAIL PROTECTED] ---
You are currently subscribed to jdjlist as: [EMAIL PROTECTED]
To unsubscribe send a blank email to [EMAIL PROTECTED]
http://www.sys-con.com/fusetalk To unsubscribe from all mailing lists, click:
http://sys-con.com/[EMAIL PROTECTED]
