aspose file tools*
The moose likes Beginning Java and the fly likes Multiple comparators ? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Multiple comparators ?" Watch "Multiple comparators ?" New topic
Author

Multiple comparators ?

ben oliver
Ranch Hand

Joined: Mar 28, 2006
Posts: 375
If I have a class like


Given a list of Students I need to sort using different attributes like "name", "address", "enrollDate", etc. Each has a different comparison rule. One approach is to create several different Comparator classes, each implement its unique compare method. Is there any better way that I don't need to create several comparator classes but still can sort the Stuent List using whatever attribute ? i.e. is it possible to consolidate the multiple comparator classes into one ?
Stevens Miller
Ranch Hand

Joined: Jul 26, 2012
Posts: 523
    
    3

"Better," of course, depends on what you are trying to do. If, for example, you want to be able to sort by more than one field, with a particular precedence (akin to a "select * from Students order by acctBalance, enrollDate, name" SQL statement), an interesting hybrid approach (one that uses a unique Comparator for each field in the sorted object type, but which can sort on any set of those fields with any precedence, in a single call) can be found at this blog.

Now, as those of us trying to convert from being procedural programmers to object programmers can tell you, a dedicated programmer can write "C" programs in any modern language, even Java. Thus, one could create a single Comparator that, say, retained some internal state you set before sorting, which it could rely upon when called to decide which fields to use and with what precedence. However, I believe someone like Campbell Ritchie would quite rightfully call upon me to quietly resign from the human race if I did that, so I won't.
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3611
    
  14

I'm not sure how useful it is though. Sorting by multiple criteria can easily be done with a stable sorting algorithm, such as Java's standard merge-sort algorithm.
Please note that I didn't compile or test this code, it may be riddled with errors.
Ivan Jozsef Balazs
Rancher

Joined: May 22, 2012
Posts: 867
    
    5
Stevens Miller wrote:Thus, one could create a single Comparator that, say, retained some internal state you set before sorting, which it could rely upon when called to decide which fields to use and with what precedence.



If this Comparator established the internal state during construction time, it would not be frowned upon from an OO point of view and the one making the suggestion would not be expelled from mankind.
Stevens Miller
Ranch Hand

Joined: Jul 26, 2012
Posts: 523
    
    3

Ivan Jozsef Balazs wrote:
Stevens Miller wrote:Thus, one could create a single Comparator that, say, retained some internal state you set before sorting, which it could rely upon when called to decide which fields to use and with what precedence.

If this Comparator established the internal state during construction time, it would not be frowned upon from an OO point of view and the one making the suggestion would not be expelled from mankind.

Hah! Good point, Ivan. Shows what I mean by how challenging it is, sometimes, to switch from being a procedural programmer to an OO programmer. I was contemplating an object that, once constructed, would support a method to set that state. Your point raises an interesting alternative option. The approach you're suggesting could even make the object immutable, couldn't it?

Thanks for making that comment.
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4363
    
    8

Ivan Jozsef Balazs wrote:If this Comparator established the internal state during construction time, it would not be frowned upon from an OO point of view and the one making the suggestion would not be expelled from mankind.

It wouldn't be disastrous. But I'd still prefer multiple very simple Comparator classes to a more complicated general purpose one, as it will be far more obvious what's going on. You're not going to get much more readable than code like this:
Stevens Miller
Ranch Hand

Joined: Jul 26, 2012
Posts: 523
    
    3

Matthew Brown wrote:
Ivan Jozsef Balazs wrote:If this Comparator established the internal state during construction time, it would not be frowned upon from an OO point of view and the one making the suggestion would not be expelled from mankind.

It wouldn't be disastrous. But I'd still prefer multiple very simple Comparator classes to a more complicated general purpose one, as it will be far more obvious what's going on. You're not going to get much more readable than code like this:

Matthew, how would you feel about something that looked like this?

The StudentSorter object gets an array of Comparators, so you still sort in one line, but by multiple fields. If you saved the StudentSorter object, you could use it more than once, getting the same sorting order each time. You could also pass it to other methods that wouldn't necessarily need to know or care what that order was, but they would still be able to sort in one call.

The StudentSorter could take a variable argument list (something like this untested fragment):

The comparators array in StudentSorter retains the ordered list of Comparator objects (in effect, the "state" that Ivan suggests be established at construction time), while allowing for any number of sorting fields in any order.
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3611
    
  14

Again, why? A "compound" comparator like this is only useful if you're using unstable sorting algorithms, such as quick-sort.

If I changed the parameter of the sort method I proposed above to take varargs, and made a simple static import you could just do this:
Stevens Miller
Ranch Hand

Joined: Jul 26, 2012
Posts: 523
    
    3

Stephan van Hulst wrote:Again, why? A "compound" comparator like this is only useful if you're using unstable sorting algorithms, such as quick-sort.

If I changed the parameter of the sort method I proposed above to take varargs, and made a simple static import you could just do this:

I guess the only significant difference I can see is that your static method doesn't save the sorter, so it can't be passed to anything else that the caller might want to impose the same sorting order upon, without having to know what it is (the caller itself might have received the sorter from some other caller, higher up the stack). Other than that, I think your proposal and my take on Ivan's are largely the same, by using a series of individual sorters; yours doesn't save that list, and needs no object, while mine saves the list as "state" when the composite sorter is created. One of the more advanced commentators would have to chime in here to be precise about any basis in general for a preference, but my imprecise inclination is to favor doing things with object instances instead of static methods when I can. YMMV.
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4363
    
    8

Stevens Miller wrote:
Matthew, how would you feel about something that looked like this?

The StudentSorter object gets an array of Comparators, so you still sort in one line, but by multiple fields. If you saved the StudentSorter object, you could use it more than once, getting the same sorting order each time. You could also pass it to other methods that wouldn't necessarily need to know or care what that order was, but they would still be able to sort in one call.

Sounds OK to me. I'd probably make StudentSorter a generic CompoundComparator - seems like the sort of class you only ever need to write once.

Stephan van Hulst wrote:Again, why? A "compound" comparator like this is only useful if you're using unstable sorting algorithms, such as quick-sort.

Well, to be fair, Collections.sort might is stable. But can you guarantee you'll never want to use the Comparator will never be used in a context where it makes a difference? What if you want to put them in a TreeSet, or some other sorted collection? Or any other context where a comparison operation is used? Making a compound Comparator is more flexible than making a compound sort method.
Ivan Jozsef Balazs
Rancher

Joined: May 22, 2012
Posts: 867
    
    5
Stephan van Hulst wrote:A "compound" comparator like this is only useful if you're using unstable sorting algorithms



Actually why? If there is is only one sorting criterium, the order or the equivalent elements is not defined without respect to whether they come in the original order (stable case) or not (unstable case). The need to define further sorting criteria is quite natural if there are collisions per the first criterium.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38363
    
  23
Stevens Miller wrote: . . . However, I believe someone like Campbell Ritchie would quite rightfully call upon me to quietly resign from the human race if I did that, so I won't.
You are exaggerating (but only slightly).
And I agree there is some iffy code in that blog, the use of break for example. That isn’t really a multiple Comparator, but a compareTo method which stops when it reaches its first difference. You can achieve this with tests for if difference == 0 or difference == 0 as part of the continuation test in the loop. I agree with the blog that such sorting is best left to databases, if at all possible.

I would be interested to see the other multiple Comparator you mentioned, though I suspect it would be some sort of procedural code.
The way I would prefer to sort is to use several Comparators and a stable sort. Slightly slower, but easier to understand.Note you use the Comparators in a sort of backwards order.
Martin Vajsar
Sheriff

Joined: Aug 22, 2010
Posts: 3610
    
  60

Matthew Brown wrote:
Stephan van Hulst wrote:Again, why? A "compound" comparator like this is only useful if you're using unstable sorting algorithms, such as quick-sort.

Well, to be fair, Collections.sort might is stable. But can you guarantee you'll never want to use the Comparator will never be used in a context where it makes a difference? What if you want to put them in a TreeSet, or some other sorted collection? Or any other context where a comparison operation is used? Making a compound Comparator is more flexible than making a compound sort method.

Collections.sort is actually documented to be stable.

But I prefer the compound comparator anyways. Apart from its utility in cases already mentioned, I abhor the idea of executing several sorts where one would suffice. I understand that given todays computer speed it is not a deal, unless the list has millions of items, or the sort is called thousands of times, but still... it's like sorting an array to get the maximum element.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Multiple comparators ?