Re: indirect sort
Lew wrote:
On May 13, 11:33 am, Eric Sosman <Eric.Sos...@sun.com> wrote:
tno...@gmail.com wrote:
So I did the actual test. The code is pasted below. For me it looks
like the version that iterates through the array of objects, extracts
double data, puts it into an array and sorts this array is faster than
just sorting the objects. About 4-5 times faster. It looks like it is
worthy to have my own implementation of sort(), that swaps integers in
a second array while sorting the double[]
For what it's worth, I ran your test on my system and got
similar results: Arrays.sort(double[]) took about 1/4 the time
of Arrays.sort(Whatever[],Comparator). I guess that's the price
you pay for the flexibility of a Comparator versus a hard-wired
comparison buried inside the sorting code.
More likely it's the difference between primitive comparisons and
object comparisons based on attributes of the type. A 'double'
comparator can simple subtract one argument from the other and cast
the result to 'int'. Attribute comparisons generally involve multiple
'if' tests.
I hope you're not in the habit of comparing doubles this way,
as it is faulty in several respects. For example, it declares
that 5.9 and 6.2 are equal, that 3.5E9 is less than 1.0E9, and so on.
I don't know what it would do with infinities and NaNs, but there's
a pretty good chance it would botch them.
Academically interesting exercise: There are 2**128 possible
pairs of doubles, somewhat fewer if you consider all NaNs alike.
Subtract-and-cast will give the right answer for some of these
pairs, the wrong answer for others. Estimate the success rate.
In a quick-and-dirty[*] empirical test with ten million pairs of
random doubles, subtract-and-cast agreed with Double.compare()
74.95% of the time, doing better than I'd guessed it would. All
the disagreements in this particular test had subtract-and-cast
declaring equality when Double.compare() detected inequality.
[*] "Dirty" because Random.nextLong() can't generate all the
bit patterns Double.longBitsToDouble() could use, hence some
possibly-systematic groups of double values are omitted.
Also also, I note that there's no warmup run to let Hotspot do its
magic. Does that reflect the usage of the class in the field?
The original code runs the test ten times. For my "1/4"
result, I discarded the first iteration as potentially contaminated
(it *was* in fact slower than the others).
--
Eric.Sosman@sun.com