Найди ошибку: плохие сравнения. Часть 1

Article
01/27/2011

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

Прежде всего, какие требования налагаются на этот делегат? Они четко описаны: делегат сравнения принимает два элемента и возвращает 32-х битовое знаковое целое. Если первый элемент больше второго, тогда возвращаемое значение больше нуля. Если первый элемент меньше второго, возвращается значение меньшее нуля. Если первый элемент равен второму, тогда возвращается нуль.

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

Сравнение №1: Одеть шапку последней:

 enum Clothes
{
  Hat,
  Tie,
  Socks,
  Pocketwatch,
  Vest,
  Shirt,
  Shoes,
  Cufflinks,
  Gloves,
  Tailcoat,
  Underpants,
  Trousers
}
static int Compare(Clothes x, Clothes y)
{
  const int xGreater = 1;
  const int yGreater = -1;

  // If x has to go on after y then x is the greater 
  // If y has to go on after x then y is the greater
  // Otherwise, they are equal

  switch (x)
  {
  case Clothes.Tie:
    if (y == Clothes.Shirt) return xGreater;
    break;
  case Clothes.Socks:
    if (y == Clothes.Shoes) return yGreater;
    break;
  case Clothes.Pocketwatch:
    if (y == Clothes.Shirt || y == Clothes.Vest) return xGreater;
    break;
  case Clothes.Vest:
    if (y == Clothes.Shirt) return xGreater;
    if (y == Clothes.Tailcoat || y == Clothes.Pocketwatch) return yGreater;
    break;
  case Clothes.Shirt:
    if (y == Clothes.Tie || y == Clothes.Pocketwatch || 
      y == Clothes.Vest || y == Clothes.Cufflinks || y == Clothes.Tailcoat)
      return yGreater;
    break;
  case Clothes.Shoes:
    if (y == Clothes.Trousers || y == Clothes.Socks || y == Clothes.Underpants)
      return xGreater;
  break;
  case Clothes.Cufflinks:
    if (y == Clothes.Shirt) return xGreater;
    break;
  case Clothes.Tailcoat:
    if (y == Clothes.Vest || y == Clothes.Shirt) return xGreater;
    break;
  case Clothes.Underpants:
    if (y == Clothes.Trousers || y == Clothes.Shoes) return yGreater;
    break;
  case Clothes.Trousers:
    if (y == Clothes.Underpants) return xGreater;
    if (y == Clothes.Shoes) return yGreater;
      break;
  }
  return 0;
}

Хорошо, но прежде чем продолжать чтение, постарайтесь найти ошибку в этом коде. Он кажется совершенно простым: если две вещи должны быть надеты в определенном порядке, тогда возвращается значение, соответствующее этому порядку, если это не так, то мы говорим, что нам все равно, в каком порядке их надевать, и возвращаем 0.

Работает ли этот код?

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

Недокументированным, но чрезвычайно важным допущением алгоритма сортировки является то, что функция сравнения обеспечивает непротиворечивое, полное упорядочивание. Обеспечение полного упорядочивания (total order) означает, что функция сравнения должна сохранять инвариант, который заключается в следующем: элементы равные другому элементу, равны между собой. Идея, что две вещи, которые можно надеть в любом порядке, равны, попросту неверна. В нашем примере, Tie (Галстук) равен Hat (Шапка), а Hat (Шапка) равна Shirt (Рубашка), и, таким образом, алгоритм сортировки считает, что Tie (Галстук) равен Shirt (Рубашка), а это не так.

Предположим, что первым элементом в списке является “Hat” (Шапка). Алгоритм сортировки просматривает список целиком, понимает, что все элементы равны первому элементу и приходит к выводу, что этот список уже отсортирован. Очевидно, что список, в котором каждый элемент равен первому элементу, отсортирован! Реальная реализация быстрой сортировки в BCL является достаточно сложной и содержит несколько хитрых трюков оптимизации для некоторых распространенных случаев, например таких, когда подмножество списка уже является отсортированным. Если сравнения являются непоследовательными, то можно легко обмануть эти эвристики и получить неверные результаты. На самом деле, в случае предоставления подобной функции сравнения, некоторые алгоритмы сортировки могут попасть в бесконечный цикл или даже завершится с ошибкой.

Правильным алгоритмом для частичного упорядочивания является топологическая сортировка; всегда следует использовать правильные инструменты.

В следующий раз: будем делать то же самое снова.

Оригинал статьи

Найди ошибку: плохие сравнения. Часть 1

Additional resources