Hi Guys, Below I have given two links to my submissions source code for problem 159B. The two codes are exactly same. The only difference is that one of the submission is made in JAVA 6 and the other one in JAVA 7. And it is interesting to note that the submission in JAVA 6 got AC while in JAVA 7 got RE. I think this is probably due to different implementations of inbuilt sort in JAVA 6 and 7. Any of your suggestions are welcome on this topic here and yes, we should wait a bit before saying Good Bye to JAVA 6 because their can be even more bugs in JAVA 7 in addition to this one. Link to my submission under JAVA 6 1353158 and Link to my submission under JAVA 7 1353143
Thank You.
Your comparator is wrong. See the message:
If two objects are equal, comparator should return 0 but your comparator never returns 0.
But the submission in JAVA 6 ran successfully. The comparator definition is exactly same there.
It seems that Java 6's sort doesn't check if the comparator is correct.
Yeah, got AC on adding the return 0;.
Why Java can understand it? Without unnecessary comparasions it should be impossible. If a.compare(b) = -1, It should suppose a less than b, and never compare (b and a) or (a and b) or (something that greater than b and something less than a) etc.
Yes, I understand that it's MAY do it, but why it spend our CPU time?
What do you think about it?
Yeah sure, I fully agree with you. For suppose I have Obj1=(1,2) and Obj2=(1,2). On calling Obj1.compareTo(Obj1), compareTo function as defined will return -1. Why java should check if it returns 0 in this case. It is none of it's matter. In the above case it should simply return -1 and go on and should not have given RE. And if it does, it should show a message during compilation if the comparator does not return 0. Doing that thing in runtime and giving runtime exception after passing 9 test cases is kind of wierd.
Java 7 assumes that Comparator.compare method is consistent. But if it is not, certain assertions about values of variables are wrong.
Look at the source, line 868. You can see that if your comparator is "buggy", it may violate an assertion.
So, Java 7 does not check your comparator on every pair of elements or so. If it did, it would fail (with the exception) on the first test. But it checks a small number of invariants. If it did not, you would receive a cryptic error, probably something like ArrayOutOfBoundsException, from inside the sort procedure, and you will never guess that it is your fault.
Yeah, I got it. Thanks.
> It should suppose a less than b, and never compare (b and a) or (a and b)
I think it's too expensive to cache all comparison results for general case. Oracle's implementation uses tricky in-place merge sort and it needs some duplicate comparison in different places of code. If your comparator is too expensive you can implement some cache technique inside of the comparator.
But if there is no cache, how can you understand, that comparator is icorrect?:)
It's depend on used algorithm — it may not directly use cache (like int cache[][]), but it can analyze some statistics info (you can see java's source — they check length variable after merging of two parts of array).
Yes, i got now that it may depends on sorting algo. For example, some obvious errors may be catched without additional check. But I couldn't imagine it on easy algos that I know, though
Thanks.