Interesting sort behavior in .NET
It all started with the fact that at work with colleagues began to fall tests. And only her one. I won't go into details, but the point is that there were two List objects in the test. The first was the reference, and the second was returned by the test method. Then the sheets were compared element by element.
Very quickly, the reason for the drop in the test was clarified: with a colleague, the order of the elements in the resulting array was the reverse of the order in the reference array. In the code of the tested method, the standard List.Sort with our comparator was used, which is exactly on this test that always returns 0. But for the whole team the elements were returned in the same order, and for one employee - strictly in reverse. It was quickly found out that her colleague had not had updates for a long time and her version of mscorlib.dll was very different from the one that others had. It would be possible to calm down on this, but it became interesting to me, I decided to dig further and this is what I found out.
The contents of the sheet after sorting and up to with the same elements may differ, because according to msdn in list.sort, QuickSort is used, which, as we all know, is unstable. However, there is one interesting feature. About her further.
Take this code:
In principle, nothing special. There is a Smth structure in which there are two fields. There is a comparer to this structure. We saturate the sheet with three structures identical for the comparator, display the contents of the sheet before sorting, then sort, then display the number of comparisons that were made, then display the contents of the sheet after sorting.
Now let's see what they give out three different versions of the .NET Framework.
As you can see, in the older version of .NET, the sorting is stable and only three comparisons are performed. In the latest version of .NET 4.0, the sorting is unstable and seven (!) Comparisons are performed. In .NET 4.5, sorting is again stable and 3 comparisons are performed again.
Those. The new version of .NET 4.0 processes the same elements more slowly. To confirm this, I increased the number of identical elements to 100 and received 813 comparisons in the latest version of .NET 4.0, and in .NET 4.0 of the old version and in .NET 4.5, 390.
Thus, it turns out that Microsoft did everything right, then wrong, then right again. Besides, this problem can haunt me like an olympiadnik somewhere.
')
ZY: I wrote my own most simple quick sorting with counting the number of comparisons:
And even she gave out that comparisons were only 744. That is, fewer calls than comparers in the latest version of .NET 4.0
Very quickly, the reason for the drop in the test was clarified: with a colleague, the order of the elements in the resulting array was the reverse of the order in the reference array. In the code of the tested method, the standard List.Sort with our comparator was used, which is exactly on this test that always returns 0. But for the whole team the elements were returned in the same order, and for one employee - strictly in reverse. It was quickly found out that her colleague had not had updates for a long time and her version of mscorlib.dll was very different from the one that others had. It would be possible to calm down on this, but it became interesting to me, I decided to dig further and this is what I found out.
The contents of the sheet after sorting and up to with the same elements may differ, because according to msdn in list.sort, QuickSort is used, which, as we all know, is unstable. However, there is one interesting feature. About her further.
Take this code:
Code
using System; using System.Collections.Generic; namespace fkComparer { internal struct Smth { public int X; public int Y; } internal class SmthComparer : IComparer<Smth> { #region Implementation of IComparer<in smth> public int Compare(Smth x, Smth y) { Result.Count++; if(xY < yY) return -1; if(xY > yY) return 1; return 0; } #endregion } internal static class Result { public static int Count; } internal class Program { static void Main() { List<Smth> list = new List<Smth> {new Smth {X = 4, Y = 4}, new Smth {X = 5, Y = 4}, new Smth {X = 6, Y = 4}}; SmthComparer comparrer = new SmthComparer(); for (int i = 0; i < aaa.Count; i++) { Console.WriteLine(list[i].X); } Console.WriteLine("***************"); aaa.Sort(comparrer); Console.WriteLine(Result.Count); Console.WriteLine("***************"); for(int i = 0; i < aaa.Count; i++) { Console.WriteLine(list[i].X); } Console.ReadLine(); } } } In principle, nothing special. There is a Smth structure in which there are two fields. There is a comparer to this structure. We saturate the sheet with three structures identical for the comparator, display the contents of the sheet before sorting, then sort, then display the number of comparisons that were made, then display the contents of the sheet after sorting.
Now let's see what they give out three different versions of the .NET Framework.
.NET Framework 4.0 Version mscorlib.dll 4.0.30319.17929
four
five
6
***************
3
***************
four
five
6
five
6
***************
3
***************
four
five
6
.NET Framework 4.0 Version mscorlib.dll 4.0.30319.18047
four
five
6
***************
7
***************
6
five
four
five
6
***************
7
***************
6
five
four
.NET Framework 4.5
four
five
6
***************
3
***************
four
five
6
five
6
***************
3
***************
four
five
6
As you can see, in the older version of .NET, the sorting is stable and only three comparisons are performed. In the latest version of .NET 4.0, the sorting is unstable and seven (!) Comparisons are performed. In .NET 4.5, sorting is again stable and 3 comparisons are performed again.
Those. The new version of .NET 4.0 processes the same elements more slowly. To confirm this, I increased the number of identical elements to 100 and received 813 comparisons in the latest version of .NET 4.0, and in .NET 4.0 of the old version and in .NET 4.5, 390.
Thus, it turns out that Microsoft did everything right, then wrong, then right again. Besides, this problem can haunt me like an olympiadnik somewhere.
')
ZY: I wrote my own most simple quick sorting with counting the number of comparisons:
code
static void Sort(int left, int right) { int l = left; int r = right; Smth m = list[left + (right - left) / 2]; while(true) { Result.Count++; while(list[l].Y < mY) { l++; Result.Count++; } Result.Count++; while(list[r].Y > mY) { r--; Result.Count++; } if(l < r) { Smth t = list[l]; list[l] = list[r]; list[r] = t; l++; r--; } if(l >= r) break; } if(left < r) Sort(left, r); if(right > l) Sort(l, right); } And even she gave out that comparisons were only 744. That is, fewer calls than comparers in the latest version of .NET 4.0
Source: https://habr.com/ru/post/185996/
All Articles