Re: indirect sort
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.
More telling would be a comparison of Arrays.sort( Whatever /* extends
Comparable */) to Arrays.sort( Whatever, Comparator ), where the
innate Whatever#compareTo() and the Comparator#compare() implement the
same ordering.
I wonder how it would affect the speed if the Comparator implemented
the double subtraction directly instead of doing
public static class DataComparator implements Comparator<DataRecord>
{
public int compare(DataRecord d1, DataRecord d2) {
return Double.compare(d1.d,d2.d);
}
}
Also, was this timing test done with the "-server" option to Java?
Benchmark runs without a complete disclosure of benchmark conditions
are pretty useless.
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?
Also also also, the timing test does not account for the time to
access the 'DataRecord' array in the resulting desired sort order, but
leaves off after sorting the copied array. This is not helpful for
the usual case where one needs the array of actual objects in a
desired order.
However, for the limited use case where an object is a thin wrapper
for primitives and one only needs the unwrapped result of the sort,
where the sort is shown by profiling to be an actual bottleneck in a
situation where every last nanometer per second of speed is needed,
and code complexity and maintainability are less important
considerations, this technique could be a useful micro-optimization if
used very judiciously.
--
Lew