Shocking mistake with comparitor function by Microsoft programmers!
in [CSharp]
|
Prev: Which control is producing the ContextMenuStrip
Next: Save changes for a custom configuration section
From: Göran Andersson on 5 Mar 2010 02:54 RayLopez99 wrote: > On Mar 3, 11:40 am, G�ran Andersson <gu...(a)guffa.com> wrote: >> Arne Vajh�j wrote: >>> And it is good to know about JavaScript when commenting about >>> the correctness of JavaScript code. >> As this is the C# newsgroup, I can understand why Vanderghast made the >> quick assumption that it was about C# code... >> >> -- >> G�ran Andersson >> _____http://www.guffa.com > > You mean the compare function was improper in C# but proper in > JavaScript? Learned something new > > RL No, it's the other way around. In C# where the sorting algorithm is known, such a comparer can be used, but in Javascript where the sorting algorithm is not defined, the comparer has to be deterministic. -- G�ran Andersson _____ http://www.guffa.com
From: Arne Vajhøj on 7 Mar 2010 19:31 On 05-03-2010 02:54, G�ran Andersson wrote: > RayLopez99 wrote: >> On Mar 3, 11:40 am, G�ran Andersson <gu...(a)guffa.com> wrote: >>> Arne Vajh�j wrote: >>>> And it is good to know about JavaScript when commenting about >>>> the correctness of JavaScript code. >>> As this is the C# newsgroup, I can understand why Vanderghast made the >>> quick assumption that it was about C# code... >> >> You mean the compare function was improper in C# but proper in >> JavaScript? Learned something new > > No, it's the other way around. In C# where the sorting algorithm is > known, such a comparer can be used, but in Javascript where the sorting > algorithm is not defined, the comparer has to be deterministic. Actually the sorting algorithm in .NET is not that well-defined. The docs only state that it is using quick-sort - it does not specify exactly how the pivot element is picked. What is even worse is that docs for IComparer does not specify any contracts that needs to be fulfilled. But my claim is that this is a bug and IComparer indeed have similar requirements to JavaScript (and Java - check http://java.sun.com/javase/6/docs/api/java/util/Comparator.html#compare%28T,%20T%29). Othwerwise I can not see how Array.BinarySearch will ever work with IComparer. Obviously you can argue that with no restrictions in the docs, then anything goes. Arne
From: Arne Vajhøj on 7 Mar 2010 19:52
On 07-03-2010 19:31, Arne Vajh�j wrote: > On 05-03-2010 02:54, G�ran Andersson wrote: >> RayLopez99 wrote: >>> On Mar 3, 11:40 am, G�ran Andersson <gu...(a)guffa.com> wrote: >>>> Arne Vajh�j wrote: >>>>> And it is good to know about JavaScript when commenting about >>>>> the correctness of JavaScript code. >>>> As this is the C# newsgroup, I can understand why Vanderghast made the >>>> quick assumption that it was about C# code... >>> >>> You mean the compare function was improper in C# but proper in >>> JavaScript? Learned something new >> >> No, it's the other way around. In C# where the sorting algorithm is >> known, such a comparer can be used, but in Javascript where the sorting >> algorithm is not defined, the comparer has to be deterministic. > > Actually the sorting algorithm in .NET is not that well-defined. > > The docs only state that it is using quick-sort - it does > not specify exactly how the pivot element is picked. > > What is even worse is that docs for IComparer does not specify > any contracts that needs to be fulfilled. > > But my claim is that this is a bug and IComparer indeed > have similar requirements to JavaScript (and Java - check > http://java.sun.com/javase/6/docs/api/java/util/Comparator.html#compare%28T,%20T%29). > > > Othwerwise I can not see how Array.BinarySearch will > ever work with IComparer. > > Obviously you can argue that with no restrictions in the > docs, then anything goes. It should also be noted that this is only about the deterministic behavior of the sort. Even if it is deterministic then there are no guarantee that the the results will be evenly distributed. In fact a standard implementation of QuickSort and a comparer as the one described will not result in an even distribution. Someone better than me at math will have to explain why. I suspect that it has something to do with the fact that the number of elements below and below the pivot element is not uniformly distributed but binominal distributed. Arne |