Java VM 1.6.0 Sorting Collections
in [Java Programming]
|
From: Tom Anderson on 10 Jun 2010 16:39 On Thu, 10 Jun 2010, Jim Janney wrote: > Tom Anderson <twic(a)urchin.earth.li> writes: > >> On Thu, 10 Jun 2010, Jim Janney wrote: >> >>> Jim Janney <jjanney(a)shell.xmission.com> writes: >>> >>>> 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. >>> >>> The evil approach would be to use reflection to get the elementData >>> field in ArrayList, and call Arrays.sort directly on that. >> >> Your ideas are intriguing to me, and i wish to subscribe to your >> newsletter. > > "Why you should buy what you hate" > > http://online.wsj.com/article/SB10001424052748704025304575285000265955016.html Waaay ahead of you. Most of my money's in (a) tobacco companies and (b) Russia. tom -- All historians agree that George Washington's greatest regret was not being PERMANENTLY INVISIBLE.
From: Roedy Green on 10 Jun 2010 16:50 On Wed, 9 Jun 2010 21:00:08 -0700 (PDT), petek1976 <pete.karousos(a)earthlink.net> wrote, quoted or indirectly quoted someone who said : >Using an array >instead of ArrayList is not an option Why? You can always convert an ArrayList to an array and back again. It might not buy you anything, but code outside that would not even know about it. -- 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 16:51 On Wed, 9 Jun 2010 21:00:08 -0700 (PDT), petek1976 <pete.karousos(a)earthlink.net> wrote, quoted or indirectly quoted someone who said : > final int vecSize = 1000000; > ArrayList<Double> vec = new ArrayList<Double>(vecSize); This is a fair hunk of RAM to carve out of the heap. You might want to do some experiments with the command line options that tune the heap. See http://mindprod.com/jgloss/javaexe.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: Roedy Green on 10 Jun 2010 16:55 On Wed, 9 Jun 2010 21:00:08 -0700 (PDT), petek1976 <pete.karousos(a)earthlink.net> wrote, quoted or indirectly quoted someone who said : > ArrayList<Double> vec = new ArrayList<Double>(vecSize); Arraylist of Double is HUGELY fatter than array of double because there is the object header overhead for every item in the ArrayList. The sort comparison routine with the ArrayList has to find the values to compare with extra indirection. That is mostly what consumes the cycles in a sort. -- 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: Tom Anderson on 10 Jun 2010 17:08
On Thu, 10 Jun 2010, Lew wrote: > Jim Janney wrote: >> Assuming n log(n) performance for the sorting algorithm, sorting a >> million-element list once gives you well over a million visits to the >> comparison code, and presumably to the inner loops of the sort. > > Good point, but if he doesn't have "-server" then it might not even do > that optimization. This document: http://java.sun.com/performance/reference/whitepapers/tuning.html is so old it's virtually scripture (last revised in 2005, for 1.5.0_06, i think), so i don't know how applicable it is to the OP's JVM, but it alleges that: Most computers that have at least 2 CPU's and at least 2 GB of physical memory are considered server-class machines which means that by default the settings are: * The -server compiler If 'CPUs' means 'cores', and the OP's machine is reasonably recent, there's a strong chance that -server is on already. Doesn't hurt to turn it on explicitly, of course. I know i do! tom -- All historians agree that George Washington's greatest regret was not being PERMANENTLY INVISIBLE. |