[jdjlist] Re: LFUCache problem

[James Stauffer]

Title: RE: [jdjlist] Re: LFUCache problem

Since the order that you want things sorted in can change based on usage then it could never keep it sorted with a standard collection. Correct? What happens more? The action that changes the order (accessing the items) or getting the items in the sorted order?   James Stauffer -----Original Message----- From: Greg Nudelman [mailto:[EMAIL PROTECTED] Sent: Friday, November 14, 2003 1:52 PM To: jdjlist Subject: [jdjlist] Re: LFUCache problem Dear Keats,   Thank you so much for the input.  I thought about this problem for a few days more and I figured out that I can get everything done with a single data-structure, a Hashtable with a real-time selection algorithm.  I'm writing the code now and will test the performance, and try to post a link here as soon as it is done (it's labor of love, as you can tell, so it may take a while :-)    One question though:   > The trickiest part of caching in Java is dealing with thread-safety issues with the Java Memory Model.    If I have a real-time synchronized public access methods and nothing running as a background thread, do I need to worry about any kind of locking issues for my cache, or should Java mostly take care of it?  I'm going to have a hell of a time testing this with multiple threads... does anyone have a simple, good thread testing class I can use that I can test cache concurrency on?   Look for my code coming soon, I hope some else can use it also.  Thank you again everyone for the input. I really appreciate being a part of a knowledgeable support group like this, it makes the projects a lot more fun!   Happy Friday and a Good Weekend to all,   Greg   -----Original Message----- From: Keats [mailto:[EMAIL PROTECTED] Sent: Friday, November 14, 2003 8:42 AM To: jdjlist Subject: [jdjlist] Re: LFUCache problem Using a Map is useful if you need to access elements by a key, which I would guess you want, though I don't know your requirements.  However, I don't know what a TreeMap does when you try to insert new elements when the tree is out order -- it will probably insert into the wrong place.  You probably need to store your elements in both a List and a Map and just sort the List.   The best implementation of the sorting thread is dependent on the performance requirements and expected usage patterns.  For example, if you can reasonably expect there there will be quiet periods, then an interruptable, low priortity thread as you propose sounds good.  However if the system will experience continual load for extended periods the sort might never complete.  You could add a timer to force a sort after a specified period of time, but this would force readers to block.  If this is unacceptable then you may want to go back to the idea of reinserting into a sorted list after each access.  The average performance would be slower but the worst case would be much faster.  (This is the classic problem with using garbage collection in real-time systems.)   The trickiest part of caching in Java is dealing with thread-safety issues with the Java Memory Model.  I strongly suggest using Doug Lea's excellent collections package to help deal with this.  See: http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html   Have fun! ----- Original Message ----- From: Greg Nudelman To: jdjlist Sent: Thursday, November 13, 2003 11:50 AM 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] **************************************************************************** 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]