Внутренняя работа методов Sort() и CompareTo()

Я пытался понять, как метод CompareTo() работает внутри, но потерпел неудачу. Я искал этот сайт и прочитал несколько сообщений, и я думаю, что видел все, что можно увидеть в MSDN по этому вопросу, и я просто не понимаю. Пример MSDN:

public int CompareTo(object obj)
{
    if (obj == null)
    {
        return 1;
    }

    Temperature otherTemperature = obj as Temperature;
    if (otherTemperature != null)
    {
        return this.temperatureC.CompareTo(otherTemperature.temperatureC);
    }
    else
    {
        throw new ArgumentException("the object is not a temperature");
    }
}

Это пример MSDN реализации метода CompareTo(). Я понимаю это, я понимаю, как работает интерфейс IComparable, если я правильно понял, это вызывается, когда я использую метод ArrayList.Sort().

Чего я не понимаю, так это: когда программа передает аргумент для метода CompareTo(object obj)? Или, другими словами, как работает метод Sort()? Я имею в виду, что этот код сравнивает экземпляр температуры с другим экземпляром температуры, но когда и как программа получает второй экземпляр температуры для проведения сравнения? Надеюсь, мой вопрос имеет смысл.

Я попытался вывести на экран процесс CompareTo(), поэтому, возможно, я мог бы перепроектировать вывод, но я запутался еще больше.

EDIT: Может быть, если я буду идти шаг за шагом, я смогу лучше объяснить себя. Предположим, у меня есть 3 объекта температуры: 34, 45, 21 в ArrayList. Когда я вызываю ArrayList.Sort(), вызывается ли метод CompareTo() как 34.CompareTo(45)? А потом 45.CompareTo(21)? Возвращаемые целые числа будут равны 1 при первом сравнении и -1 при втором? И как эти целые числа возвращались, если я определил метод CompareTo() только для возврата 1, только если obj (параметр) был нулевым? Я ничего не определял для возврата -1 или 0. Это как если бы я реализовывал уже реализованный метод. Определение метода CompareTo(), когда он уже определен для возврата -1, 0 и 1.


person JaviML    schedule 05.03.2013    source источник
comment
Другой экземпляр исходит из массива, который вы сортируете.   -  person SLaks    schedule 06.03.2013


Ответы (5)


Начнем с основной идеи.

Какова цель CompareTo?

Чему равно 42 относительно 1337. 42... больше, меньше или равно 1337?

Этот вопрос и ответ на него моделируются методом CompareTo в интерфейсах IComparable<T> и IComparable. Для A.CompareTo(B) метод может возвращать:

  • A больше B: целочисленное значение больше 0.
  • A меньше B: целочисленное значение меньше 0.
  • A равно B: целочисленное значение, равное 0.

И, конечно же, IComparable не ограничивается целыми числами. Вы можете реализовать IComparable для сравнения любых двух объектов, которые, по вашему мнению, должны быть сопоставимы. Например, строки:

Что такое «Броненосец» для «Зодиака»: «Броненосец»… больше, меньше или равен «Зодиаку»?

Ответ зависит от вашего определения больше, меньше и равно. Для строк обычный порядок таков, что слово, которое должно появиться позже в словаре, больше слова, которое встречается раньше.

Как CompareTo помогает сортировать?

Хорошо, теперь вы знаете, как сравнивать любые два объекта. Это полезно для многих алгоритмов, но в основном для алгоритмов сортировки и упорядочивания. Возьмем, к примеру, очень простой алгоритм сортировки: глупая сортировка. Идея такова:

Посмотрите на два соседних элемента в вашем массиве, A и B.
Когда A ‹= B: перейдите к следующей паре.
Когда A > B: поменяйте местами A и B и вернитесь к предыдущей пара.
Когда мы дойдем до конца, мы закончим.

Видите ли, для сортировки должен быть способ определить, какой из двух элементов больше. Вот где IComparable<T> вступает в игру.

public static void StupidSort<T>(T[] array)
            where T : IComparable<T>
{
    int index = 0;
    while (index < array.Length)
    {
        if (index == 0 ||
            array[index - 1].CompareTo(array[index]) <= 0)
        {
            index++;
        }
        else
        {
            Swap(array, index - 1, index);
            index--;
        }
    }
}

Что произойдет, если CompareTo всегда будет возвращать 1?

Конечно, вы можете запрограммировать CompareTo так, чтобы он возвращал все, что захотите. Но если вы облажаетесь, то ваш метод больше не отвечает на вопрос чему равно this по отношению к obj? Если всегда будет возвращаться 1, это будет означать, что для любых A и B A всегда больше, чем B. Это все равно, что сказать : 20 больше 10 и 10 больше 20. Это не имеет смысла, и в результате любая сортировка, которую вы делаете, также не будет иметь никакого смысла. Мусор на... мусор на выходе.

Правила игры для трех заданных объектов A, B и C:

  • A.CompareTo(A) должен возвращать 0 (A равно A).
  • Если A.CompareTo(B) возвращает 0, то B.CompareTo(A) возвращает 0 (Если A равно B, то B равно A).
  • Если A.CompareTo(B) возвращает 0, а B.CompareTo(C) возвращает 0, то A.CompareTo(C) возвращает 0 (Если A равно B, а B равно C, то A равно C).
  • Если A.CompareTo(B) возвращает значение больше 0, то B.CompareTo(A) возвращает значение меньше 0 (Если A больше B, то B меньше A).
  • Если A.CompareTo(B) возвращает значение меньше 0, то B.CompareTo(A) возвращает значение больше 0 (Если A меньше B, то B больше A).
  • Если A.CompareTo(B) возвращает значение больше 0, а B.CompareTo(C) возвращает значение больше 0, то A.CompareTo(C) возвращает значение больше 0 (Если A больше B, а B больше C, то A больше C ).
  • Если A.CompareTo(B) возвращает значение меньше 0, а B.CompareTo(C) возвращает значение меньше 0, то A.CompareTo(C) возвращает значение меньше 0 (Если A меньше B, а B меньше C, то A меньше C ).
  • null всегда меньше любого ненулевого объекта.

Если ваша реализация не соответствует этим (простым и логичным) принципам, то алгоритмы сортировки могут буквально делать все что угодно и, вероятно, не дадут ожидаемых результатов.

person Daniel A.A. Pelsmaeker    schedule 05.03.2013

Когда вы хотите сравнить a с b, вы говорите:

int result=a.CompareTo(b);

т. е. первый операнд сравнения — this, а второй — параметр, передаваемый функции.

Затем, когда вы сортируете массив, независимо от используемого алгоритма, вы должны сравнивать элементы вместе, отправляя их как this и obj в object.CompareTo (или жизнеспособные перегрузки этой функции).

person Blindy    schedule 05.03.2013
comment
Спасибо всем за быстрые ответы. Чего я до сих пор не понимаю: хорошо, независимо от используемого алгоритма... но разве я не определяю алгоритм, когда пишу реализацию метода CompareTo()? Так почему же вызов метода CompareTo() внутри того же метода CompareTo(), который я реализую, работает? - person JaviML; 06.03.2013

Метод сортировки не зависит от метода CompareTo. Я не уверен, какой алгоритм сортировки используется, но я предполагаю, что это что-то вроде быстрой сортировки (очевидно, не пузырьковой сортировки). Если вас интересуют эти алгоритмы, Википедия подробно их документирует.

Метод CompareTo — это просто средство для сравнения объектов одного типа. Он изначально определен для многих распространенных типов .NET и может быть переопределен для сравнения между пользовательскими объектами (вещами, которые вы создаете). По сути, вы вызываете его из объекта типа A, передавая ему второй объект типа A, а возвращаемое значение указывает, равны ли два объекта или один больше другого.

Лучше всего рассматривать CompareTo как функцию полезности. Он существует, чтобы вы могли выполнять пользовательские сравнения, используя методы сортировки, предоставляемые общими структурами данных .NET. Без чего-то подобного вам пришлось бы самому писать алгоритм сортировки, чтобы сравнивать созданные вами типы. Его цель - просто сделать методы сортировки многоразовыми/расширяемыми.

person evanmcdonnal    schedule 05.03.2013

Короче говоря, Sort берет два элемента вашего ArrayList и вызывает CompareTo для первых элементов и передает второй элемент в качестве аргумента, например:

element1.CompareTo(element2)

CompareTo возвращает отрицательное значение, если element1 меньше, чем element2, 0, если они равны, положительное значение в противном случае. Sort использует это возвращаемое значение, чтобы выполнить некоторую сортировку. Затем он повторяет этот процесс для следующих двух элементов, выполняет дополнительную сортировку и так далее, пока ArrayList не будет отсортирован. Найдите «алгоритм сортировки», чтобы получить больше информации об этом процессе.

person Dmitry Osinovskiy    schedule 05.03.2013

Существуют разные алгоритмы сортировки. Однако независимо от того, есть моменты, когда алгоритм должен решить, какой элемент больше, и это когда вызывается CompareTo.

a.CompareTo(b) < 0;

Если a и b равны Integers (или в псевдокоде), вы также можете использовать:

a < b

Я думаю, вы найдете нотацию a < b во многих примерах псевдокода или алгоритма целочисленной сортировки. CompareTo метод IComparable<T> является объектно-ориентированной реализацией или нотацией.

person Matthias Meid    schedule 05.03.2013