Java VM 1.6.0 Sorting Collections
in [Java Programming]
|
From: Roedy Green on 10 Jun 2010 17:10 On Thu, 10 Jun 2010 10:09:17 -0600, Jim Janney <jjanney(a)shell.xmission.com> wrote, quoted or indirectly quoted someone who said : >You're copying the list to an array, sorting the array, and then >copying the array back to the list. You might try coding up a simple >quicksort that operates directly on the ArrayList to see what kind of >times that gives you. see http://mindprod.com/products.html#QUICKSORT for Java source. For a really fast sort, see http://mindprod.com/products.html#RADIXSORT which should do very with your short keys. -- Roedy Green Canadian Mind Products http://mindprod.com Have you ever noticed that any computer search in the movies, is always linear, with, for example, candidate fingerprints flashing up on the screen one after another? The public is still under the delusion that electronic files are microscopic filing cabinets made out of tiny wires or magnetic patches inside the computer. Most lay people are surprised that it is easy for a computer to file things simultaneously by a dozen different schemes, and that they can have any report printed in any number of different sorted orders. With physical files, they are limited to one ordering/access.
From: Roedy Green on 10 Jun 2010 17:11 On Thu, 10 Jun 2010 10:14:50 -0600, Jim Janney <jjanney(a)shell.xmission.com> wrote, quoted or indirectly quoted someone who said : >The evil approach would be to use reflection to get the elementData >field in ArrayList, and call Arrays.sort directly on that. You are still using Doubles rather than doubles, so you won't get the full benefit of a true array. -- Roedy Green Canadian Mind Products http://mindprod.com Have you ever noticed that any computer search in the movies, is always linear, with, for example, candidate fingerprints flashing up on the screen one after another? The public is still under the delusion that electronic files are microscopic filing cabinets made out of tiny wires or magnetic patches inside the computer. Most lay people are surprised that it is easy for a computer to file things simultaneously by a dozen different schemes, and that they can have any report printed in any number of different sorted orders. With physical files, they are limited to one ordering/access.
From: Roedy Green on 10 Jun 2010 17:13 On Wed, 9 Jun 2010 21:00:08 -0700 (PDT), petek1976 <pete.karousos(a)earthlink.net> wrote, quoted or indirectly quoted someone who said : >I have been having some trouble with the performance of Java. In my >code I have narrowed it down to the sort: another optimisation is to use a native compiler. See http://mindprod.com/jgloss/jet.html http://mindprod.com/jgloss/nativecompiler.html -- Roedy Green Canadian Mind Products http://mindprod.com Have you ever noticed that any computer search in the movies, is always linear, with, for example, candidate fingerprints flashing up on the screen one after another? The public is still under the delusion that electronic files are microscopic filing cabinets made out of tiny wires or magnetic patches inside the computer. Most lay people are surprised that it is easy for a computer to file things simultaneously by a dozen different schemes, and that they can have any report printed in any number of different sorted orders. With physical files, they are limited to one ordering/access.
From: Joshua Cranmer on 10 Jun 2010 17:19 On 06/10/2010 07:57 AM, Tom Anderson wrote: > 1. Java's standard sort has to be stable, which means in practice it's a > mergesort, whereas STL's doesn't, so it can be a quicksort. Quicksort > will typically be faster than mergesort for random data. Arrays.sort() will use quicksort for integral types. -- Beware of bugs in the above code; I have only proved it correct, not tried it. -- Donald E. Knuth
From: Lew on 10 Jun 2010 17:51
Roedy Green wrote: > another optimisation is to use a native compiler. Theoretically HotSpot will be a native compiler for this test, as was pointed out to me upthread. -- Lew |