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]
