 |
 | Home | Contact Us | FAQ | Search & Site Map | Link to Us |
 | Sign In | Join | Other 45 Sites in Network |
Java Forum / General / August 2007Ranking
What's the best way to have in-memory ranking? For example each element is counted for the number of times it appears and ranks are updated with every count. Eg element 1, 4 times element 4, 3 times element 3, 2 times element 2, 1 times Can I use a hashtable type for this? On Aug 24, 2:40 pm, "Crouchez" <b...@bllllllahblllbllahblahblahhh.com> wrote: > What's the best way to have in-memory ranking? For example each element is > counted for the number of times it appears and ranks are updated with every [quoted text clipped - 6 lines] > > Can I use a hashtable type for this? You can use Collections.sort(list) to sort you record. Of course,the element in list should implements Comparable interface. > On Aug 24, 2:40 pm, "Crouchez" <b...@bllllllahblllbllahblahblahhh.com> > wrote: [quoted text clipped - 13 lines] > You can use Collections.sort(list) to sort you record. > Of course,the element in list should implements Comparable interface. A list is a array of single items but I have two items of data for one object? >> On Aug 24, 2:40 pm, "Crouchez" <b...@bllllllahblllbllahblahblahhh.com> >> wrote: [quoted text clipped - 16 lines] > A list is a array of single items but I have two items of data for one > object? A single item can be an Object provided (see above) that it implements the Comparable interface. The Object can contain an arbitrary number of data items.  Signaturemartin@ | Martin Gregorie gregorie. | Essex, UK org | >> On Aug 24, 2:40 pm, "Crouchez" <b...@bllllllahblllbllahblahblahhh.com> >> wrote: [quoted text clipped - 16 lines] > A list is a array of single items but I have two items of data for one > object? use a Map if one of the elements is a key to the other, which in this case it seems to be: { item, count(item) } Use HashMap first, another implementation if you need the characteristics of it. SignatureLew > What's the best way to have in-memory ranking? For example each element is > counted for the number of times it appears and ranks are updated with [quoted text clipped - 4 lines] > element 3, 2 times > element 2, 1 times Is this your homework or something ? e.g., informal pseudocode below - a[],b[]=a; found[] = {0}; //make found the same size as a in general; i =0, foreach i in a.length, i++: j=0,foreach j in b.lengh, j++: if b[j] = a[i]: found[i]++; > Can I use a hashtable type for this? Yes, sure. Hashtables are nothing but a mapping system where a=>b (map keys to values) so if you take a bit of time and play around with the the collections API, it'll work. you'd probably need it when in above code after "found[i]++;". :) hth SignatureCheers, Ishwor Gurung /* humpty dumpty */ Ishwor Gurung kirjoitti: >> What's the best way to have in-memory ranking? For example each element is >> counted for the number of times it appears and ranks are updated with [quoted text clipped - 13 lines] > collections API, it'll work. you'd probably need it when in above code > after "found[i]++;". :) I think "priority queue" is what Crouchez is after. And that is part of java collections framework since 1.5 SignatureJani Tiainen > Ishwor Gurung kirjoitti: >> [quoted text clipped - 20 lines] > I think "priority queue" is what Crouchez is after. And that is part of > java collections framework since 1.5 Also, watch out for the term "hash table" in Java; it might lead you to use java.util.Hashtable, which would be suboptimal in most cases. Declare the variable as Map when such things are needed, and pick the appropriate implementation thereof, such as HashMap, or very rarely, Hashtable. Similarly with Vector vs. ArrayList. SignatureLew >> Ishwor Gurung kirjoitti: >>> [quoted text clipped - 27 lines] > > Similarly with Vector vs. ArrayList. why rarely hashtable? - it's auto synchronized which is a big help >>>>> Can I use a hashtable type for this? "Lew" <lew@lewscanon.com> wrote in message >> Also, watch out for the term "hash table" in Java; it might lead you to >> use java.util.Hashtable, which would be suboptimal in most cases. Declare >> the variable as Map when such things are needed, and pick the appropriate >> implementation thereof, such as HashMap, or very rarely, Hashtable. >> >> Similarly with Vector vs. ArrayList. > why rarely hashtable? - it's auto synchronized which is a big help That's "Hashtable", not "hashtable". You hadn't previously stated a need for synchronization, so of course I spoke to the general case. Hashtable isn't even necessarily the best synchronized Map because of non-Collection methods it still supports. You can use Collections.synchronizedMap( someMap ) for better safety. Or use Hashtable. Notice that I said it's "suboptimal in most cases", not "in all cases". Are you writing multi-threaded code that shares the Map, then? SignatureLew >>>>>> Can I use a hashtable type for this? > [quoted text clipped - 21 lines] > > Are you writing multi-threaded code that shares the Map, then? Yeah. I've tried Collection.synchronizedMap(map) but it throughs a concurrentmodification when used with an Iterator even when wrapped in a synchnronized(map) block. Hashtable with enumeration doesn't do this? >>>>>>> Can I use a hashtable type for this? >> [quoted text clipped - 25 lines] > concurrentmodification when used with an Iterator even when wrapped in a > synchnronized(map) block. Hashtable with enumeration doesn't do this? *throughs?? throws that should be >> Yeah. I've tried Collection.synchronizedMap(map) but it throughs a >> concurrentmodification when used with an Iterator even when wrapped in a >> synchnronized(map) block. Hashtable with enumeration doesn't do this? >> > *throughs?? throws that should be Have you tried it? ConcurrentModificationException is not inherently a threading issue. It means something changed the underlying Collection but not through the Iterator. Synchronization will not fix that. SignatureLew >>> Yeah. I've tried Collection.synchronizedMap(map) but it throughs a >>> concurrentmodification when used with an Iterator even when wrapped in a [quoted text clipped - 7 lines] > means something changed the underlying Collection but not through the > Iterator. Synchronization will not fix that. Yep. I can confirm that Collection.synchronizedMap(map) with iterator throws an concurrentmodificationexception with multithreading read/write. Hashtable with enumeration works ok. "Lew" wrote >> ConcurrentModificationException is not inherently a threading issue. It >> means something changed the underlying Collection but not through the >> Iterator. Synchronization will not fix that. > Yep. I can confirm that Collection.synchronizedMap(map) with iterator throws > an concurrentmodificationexception with multithreading read/write. Hashtable > with enumeration [sic] works ok. It'll throw that exception even without more than one thread. So will Hashtable, if you use an Iterator. When you said "enumeration", did you mean "Enumeration", as in "java.util.Enumeration<E>"? If so then you are mistaken, it does not "work ok" because there is no ability for the Enumeration to detect concurrent modification. Therefore the code is silently breaking. Again - ConcurrentModificationException is not inherently a threading issue. It does not require more than one thread to happen. If you are getting that exception, it's because you're not protecting the Map against "side" access, ergo you're getting inconsistent or wrong results. The exception alerts you to that issue. Using an Enumeration to hide the error doesn't mean the error isn't happening. SignatureLew > "Lew" wrote >>> ConcurrentModificationException is not inherently a threading issue. It [quoted text clipped - 20 lines] > exception alerts you to that issue. Using an Enumeration to hide the > error doesn't mean the error isn't happening. >>Again - ConcurrentModificationException is not inherently a threading >>issue. It does not require more than one thread to happen. Concurrent means multiple threads though doesn't it? ... >>> Again - ConcurrentModificationException is not inherently a threading >>> issue. It does not require more than one thread to happen. > > Concurrent means multiple threads though doesn't it? Not necessarily. It just means two things are going on at the same time. The effective lifetime of an Iterator is from when it is created until the last call to its methods. A change to the underlying collection during that period is "concurrent" with the iterator. Patricia "Lew" wrote in message >>> Again - ConcurrentModificationException is not inherently a threading >>> issue. It does not require more than one thread to happen. > Concurrent means multiple threads though doesn't it? According to <http://java.sun.com/javase/6/docs/api/java/util/ConcurrentModificationException.html> > Note that this exception does not always indicate that an object has been > concurrently modified by a /different/ thread. If a single thread issues a > sequence of method invocations that violates the contract of an object, > the object may throw this exception. For example, if a thread modifies a > collection directly while it is iterating over the collection with a > fail-fast iterator, the iterator will throw this exception. (emphasis in the original) Whatever "concurrent" may mean, and whether that meaning actually inherently implies multithreading or not, the Javadocs explain what the API class ConcurrentModificationException does. I tried to construct an SSCCE that demonstrates this and so far have not succeeded. Regardless, Collections.synchronizedMap() produces no less synchronized an object than does new Hashtable(). The major differences are that Hashtable contains non-Collection methods (like elements()) and seemingly does not alert you to concurrent modifications when you use the associated Enumeration instead of the more robust Iterator. I never use Hashtable so I cannot advise you better on its peculiarities. SignatureLew Crouchez wrote: >> Concurrent means multiple threads though doesn't it? > <http://java.sun.com/javase/6/docs/api/java/util/ConcurrentModificationException.html> > >> Note that this exception does not always indicate that an object has been >> concurrently modified by a /different/ thread. > (emphasis in the original) <sscce> /* ConcurrentModifier * $Id$ */ package testit; import java.util.ArrayList; import java.util.Iterator; import java.util.List; /** Cause a <code>ConcurrentModificationException</code>. */ public class ConcurrentModifier { /** Cause a <code>ConcurrentModificationException</code>. * @param args <code>String []</code> program arguments. */ public static void main( String [] args) { List <String> strangs = new ArrayList <String> (); strangs.add( "first" ); strangs.add( "second" ); strangs.add( "remove" ); strangs.add( "last" ); String val; Iterator <String> iter = strangs.iterator(); if ( iter.hasNext() ) { val = iter.next(); System.out.println( val ); System.out.println( "" ); } if ( iter.hasNext() ) { if ( strangs.remove( "remove" ) ) { System.out.println( "Removed" ); } else { System.out.println( "Not removed" ); } System.out.println( "" ); } while ( iter.hasNext() ) { val = iter.next(); // line 50 System.out.println( val ); System.out.println( "" ); } System.out.println( "out of elements" ); } } </sscce> Output: first Removed Exception in thread "main" java.util.ConcurrentModificationException at java.util.AbstractList$Itr.checkForComodification(AbstractList.java:372) at java.util.AbstractList$Itr.next(AbstractList.java:343) at testit.ConcurrentModifier.main(ConcurrentModifier.java:50) SignatureLew > Crouchez wrote: >>> Concurrent means multiple threads though doesn't it? [quoted text clipped - 75 lines] > at java.util.AbstractList$Itr.next(AbstractList.java:343) > at testit.ConcurrentModifier.main(ConcurrentModifier.java:50) That's it - it wasn't a different thread - items were being removed inside the iterator.. doh What's the best way to do remove while in the loop? Is it to store the objects temporarily in an array and remove after or is there a built-in api way? > That's it - it wasn't a different thread - items were being removed inside > the iterator.. doh > > What's the best way to do remove while in the loop? Is it to store the > objects temporarily in an array and remove after or is there a built-in api > way? Iterator.remove(). SignatureLew >> That's it - it wasn't a different thread - items were being removed >> inside the iterator.. doh [quoted text clipped - 4 lines] > > Iterator.remove(). ah of course - cheers cheers for the all feedback by the way >> What's the best way to have in-memory ranking? For example each element >> is [quoted text clipped - 7 lines] > > Is this your homework or something ? no just throwing it out to see what's the best solution Basically what I want to do is maintain a constant top 10 list that is accessed and modified by multiple threads. The list contains objects that have two values - a name and an access count. Think I might use this? Collections.sort(List list, Comparator c) like Jacky said but with a different comparator > Basically what I want to do is maintain a constant top 10 list that is > accessed and modified by multiple threads. The list contains objects that > have two values - a name and an access count. Think I might use this? > Collections.sort(List list, Comparator c) like Jacky said but with a > different comparator Your choice depends on a few things: If your list has a total of N items, finding the top k in this list is O(k*N) using a hash table, O(k) for a sorted list, O(k*N) for an unsorted list, and O(k*lg N) for a priority queue. Updating the list requires O(1) for a hash table, O(N) for a sorted list, O(1) for an unsorted list, and O(lg N) for priority queues. If the ratio of modifications to generations is m (i.e., for every m modifications, the list is regenerated), then the total time is O(m+k*N) for hash table, O(N+m*k) for sorted lists, O(k*N+m) for unsorted lists, and O((k+m)*lg N) for priority queues. If m is 1, these formulas degenerate into O(k*N), O(N+k), O(k*N), and O(k*lg N) respectively. I should note that metrics for the last two imply O(1) access to a specific element, which means that an auxiliary hash table mapping objects to indices is needed. For unsorted lists, that means that it is essentially a hash table. Without that unit, the times go up to O(N) for access in both cases. Furthermore, the time for a sorted list implies using a slightly-modified insertion sort rather than a quick sort. Updating goes up to an O(N lg N) in that case. I am also assuming that a custom heap is used for the priority queue case to take advantage of the hash table. If you want to write as little code as possible, a hash table (implemented via HashMap and Collections.synchronizedMap()) is fastest. In high-throughput conditions, a custom-made priority queue works best; the sorted list is a good middle-of-the-road, assuming you use a modified insertion sort rather than the default quicksort. SignatureBeware of bugs in the above code; I have only proved it correct, not tried it. -- Donald E. Knuth On Fri, 24 Aug 2007 06:40:48 GMT, "Crouchez" <blah@bllllllahblllbllahblahblahhh.com> wrote, quoted or indirectly quoted someone who said : >What's the best way to have in-memory ranking? For example each element is >counted for the number of times it appears and ranks are updated with every [quoted text clipped - 6 lines] > >Can I use a hashtable type for this? If what you are trying to do is count item of various kinds there are three basic approaches: 1. HashMap. Look up object and increment its count. see http://mindprod.com/jgloss/hashmap.html 2. array of counts. Compute which bin and increment it. see http://mindprod.com/jgloss/array.html 3. sort and collapse. see http://mindprod.com/jgloss/sort.html SignatureRoedy Green Canadian Mind Products The Java Glossary http://mindprod.com Free MagazinesGet these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...
|
Reply to this Message
|
 Sign In
 Join
 My Latest Posts My Monitored Threads My Blog My Photo Gallery My Profile My Homepage Start New Thread Enable EMail Alerts Rate this Thread
|
©2008 Advenet LLC Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.