Re: indirect sort

On May 13, 11:33 am, Eric Sosman <Eric.Sos...@xxxxxxx> wrote:
tno...@xxxxxxxxx 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
.

Relevant Pages

  • Re: A Fast sorting algorithm for almost sorted data
    ... far my compressor has potential but is nowhere near ready. ... It does however make heavy use of sorting. ... which I am currently calling Run sort. ... entire selected run can be added to the sorted output array. ...
    (comp.compression)
  • A Fast sorting algorithm for almost sorted data
    ... which I am currently calling Run sort. ... entire selected run can be added to the sorted output array. ... public class RunSort implements Comparator ... public static void sort(Comparable a, int start,int end) ...
    (comp.compression)
  • Re: Sorting routine
    ... n RSHIFT shifts n bits. ... in the output array. ... This would be handy for sign sorting of 2's complement. ... So Radix/Distribution sort is about 1.4 times faster than Sedge's Sort. ...
    (comp.lang.forth)
  • Re: Sorting objects in ooRex? is this possible with data structures?
    ... The sorting features are modeled off of what Java does with its Comparable and Comparator classes. ... If you want to sort on different column positions, we have a Comparator class that allows you to specify the comparison colums. ... Here's one that compares strings as numbers: ...
    (comp.lang.rexx)
  • Re: Efficiently Extracting Identical Values From A List/Array
    ... struct SortHelper ... Now sort that array according to NodeIndex: ... running through the data structure and sorting things out. ...
    (comp.lang.cpp)