Can one determine the progress of a Java Comparator?

Question

I'm using a Comparator implementation to sort a large collection of objects. Depending on the type of objects in this collection the sort takes a few milliseconds to half a minute. Is there any way to determine the progress of the Comparator while sorting? I'd like to visualize this for the user.

Collections.sort(sorted, new Comparator<Object[]>() {
    public int compare(Object[] o1, Object[] o2) {
        /* do it... */
        return order;
    }
}

The collection may hold simple short String objects, Date objects or (worst case) CLOB objects which need to fetch data while sorting.

The comparator itself has no "progress" (as it only takes a few milliseconds). You would need to track the progress of the *sort* call - and I think this could only be done by using your own implementation. — , Nov 29 '12 at 10:03
Good point... I should have a look at the Collections class or similar ones. — Daniel Bleisteiner, Nov 29 '12 at 10:04
Just found http://stackoverflow.com/questions/3956142/sort-a-large-collection-while-showing-progress with this hint... — Daniel Bleisteiner, Nov 29 '12 at 10:06
"half a minute" I suspect you are doing something wrong if its taking that long. You should look at optimizing your code. — Peter Lawrey, Nov 29 '12 at 11:05
If I sort 25 million `Long`s it takes about 30 seconds. I would consider trying to do any parsing or processing you do in the compare once rather than each time, and I would look at using multiple threads to divide the load (As sort will only use one thread) — Peter Lawrey, Nov 29 '12 at 11:24
`Long` is a rather simple datatype. Think of more complex objects like entities which need to lazy load data while sorting to determine their order. — Daniel Bleisteiner, Nov 30 '12 at 05:55

AlexWien · Accepted Answer · 2012-11-29T10:16:08.293

2

You could do that by writing an comparator that counts up an "global" variable.

But to visualize the progress for analytical purpose, you have to copy your list, and sort it twice. The first time you determine the number of comparator calls. The next time you know how far you already are, by comparing the current counter with the value from the first sort.

You would need a second thread to read out the counter while the other thread is sorting.

Another possibility is to estimate the number of comparator calls: on average this could be related to n * ld (n).

Then again count up, and read from another thread. This way you have to sort only once.

edited Nov 29 '12 at 10:16

answered Nov 29 '12 at 10:09

AlexWien

28,470
6
53
83

That's a price I wont pay... but it relates to the similar question I've posted in a comment above. – Daniel Bleisteiner Nov 29 '12 at 10:11
That might work... I'd take the typical count as 100% and guess the progress on that base. Why not. – Daniel Bleisteiner Nov 29 '12 at 10:22
A cool feature, if the clients know that it will take furher 20 minutes. Time for a break ;-) – AlexWien Nov 29 '12 at 10:25

score 0 · Answer 2 · answered Nov 29 '12 at 10:53

I've made it this way (stripped example)... thanks for your input.

{
    final long mc = (long) (data.size() * Math.log(data.size()));
    Collections.sort(sorted, new Comparator<Object[]>() {
        long c = 0; 
        public int compare(Object[] o1, Object[] o2) {
            // Using Events to update the GUI...
            Events.instance().raiseEvent(StatusBean.EVENT_STATUS, "Sorting...", (int) ((100.0 / mc) * this.c++));
            /* do it... */
            return order;
        }
    }
}

Can one determine the progress of a Java Comparator?

2 Answers2