T-D-K Jul 8 2013 at 23:10

Интересное поведение сортировки в .NET

3 min

5.1K

Всё началось с того, что на работе у коллеги стали падать тесты. Причём только у неё одной. Вдаваться в подробности не буду, но суть в том, что в тесте было два объекта List. Первый был эталонным, а второй — возвращался тестируемым методом. Затем листы сравнивались поэлементно.
Очень быстро было выяснена причина падения теста: у коллеги порядок элементов в результирующем массиве был обратным порядку в эталонном массиве. В коде тестируемого метода использовался стандартный List.Sort с нашим компаратором, который именно на этом тесте всегда возвращает 0. Но у всей команды элементы возвращались в одном порядке, а у одной сотрудницы — строго в обратном. Было быстро выяснено, что у коллеги давно не было обновлений и версия mscorlib.dll у неё сильно отличалась от той, что была у остальных. На этом можно было бы и успокоиться, но мне стало интересно я решил копать дальше и вот что выяснил.
Содержимое листа после сортировки и до при одинаковых элементах может отличаться, т.к. согласно msdn в list.sort используется QuickSort, которая, как мы все прекрасно знаем, неустойчива. Однако есть одна интересная особенность. О ней дальше.

Возьмём такой код:

Код

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(x.Y < y.Y)
                return -1;
            if(x.Y > y.Y)
                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();
        }
    }
}

В принципе, ничего особенного. Есть структура Smth, в которой два поля. Есть компарер на эту структуру. Насыщаем лист тремя одинаковыми для компарера структурами, выводим на экран содержимое листа до сортировки, потом сортируем, потом выводим количество сравнений, которое было произведено, затем выводим содержимое листа после сортировки.
А теперь посмотрим что выдают три разных версии .NET Framework.

.NET Framework 4.0 Версия mscorlib.dll 4.0.30319.17929

4
5
6
***************
3
***************
4
5
6

.NET Framework 4.0 Версия mscorlib.dll 4.0.30319.18047

4
5
6
***************
7
***************
6
5
4

.NET Framework 4.5

4
5
6
***************
3
***************
4
5
6

Как видим, в более старой версии .NET сортировка устойчивая и выполняется только три сравнения. В последней версии .NET 4.0 сортировка неустойчива и выполняется семь(!) сравнений. В .NET 4.5 сортировка вновь устойчива и выполняется опять 3 сравнения.
Т.е. новая версия .NET 4.0 медленнее обрабатывает одинаковые элементы. Для подтверждения этого я увеличил количество одинаковых элементов до 100 и получил в свежей версии .NET 4.0 — 813 сравнений, а в .NET 4.0 старой версии и в .NET 4.5 — 390.
Таким образом, получается что в Microsoft сделали всё правильно, потом неправильно, потом опять правильно. К тому же эта проблема может аукнуться мне как олимпиаднику где-нибудь.

З.Ы.: Я написал собственную самую простую быструю сортировку с подсчётом количества сравнений:

код

        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 < m.Y) {
                    l++;
                    Result.Count++;
                }
                Result.Count++;
                while(list[r].Y > m.Y) {
                    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);
        }

И даже она выдала что сравнений было всего лишь 744. Т.е. меньше чем вызовов компареров у последней версии .NET 4.0

Tags:

Hubs:

.NET