пятница, 28 ноября 2008 г.

Пишем компаратор для сортировки

Это перевод Writing a sort comparison function. Автор: Реймонд Чен.

Когда вы пишете функцию сравнения (например, для передачи в функцию сортировки ListBox), убедитесь, что ваша функция удовлетворяет следующим условиям:
  • Рефлексивность: Compare(a, a) = 0.
  • Анти-симметричность: Compare(a, b) имеет знак, противоположный знаку Compare(b, a).
  • Транзитивность: если Compare(a, b) ≤ 0 и Compare(b, c) ≤ 0, то Compare(a, c) ≤ 0.
Из этих правил следует несколько легко-доказуемых следствий. Первые два довольно очевидны, а вот третье может оказаться неожиданностью.
  • Транзитивность равенства: если Compare(a, b) = 0 и Compare(b, c) = 0, то Compare(a, c) = 0.
  • Транзитивность неравенстра: если Compare(a, b) < 0 и Compare(b, c) < 0, то Compare(a, c) < 0.
  • Подстановка: если Compare(a, b) = 0, то Compare(a, c) имеет тот же знак, что и Compare(b, c).
Из этих трёх правил довольно тяжело реализовать неверно первые два. Но вот с третьим правилом можно легко напортачить.

Заметим, что эти правила требуют от вас введения полного порядка на своих элементах. Если у вас есть только частичный порядок - вы должны расширить его до полного каким-либо согласованным и единообразным образом. Я видел, как у кое-кого возникли проблемы, когда они реализовывали компаратор для набора задач. При этом завершение одной из задач могло быть необходимым условием для заверешния других задач. Функция сравнения реализовывала такой алгоритм:
  • Если a является необходимым для b (возможно через цепочку промежуточных зависимостей), тогда a < b.
  • Если b является необходимым для a (опять-таки, возможно через цепочку промежуточных зависимостей), тогда a > b.
  • А в противном случае a = b. "Ни одна из задач не является необходимым условием для другой, поэтому меня не волнует, в каком порядке они находятся."
Звучит отлично. Тогда с такой функцией вы можете рассортировать список задач так, чтобы задачи, зависящие от других задач, были бы в списке после своих зависимостей.

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

Посмотрите на такую диагарамму зависимости:

a ----> b

c

Элемент "a" предшествует "b", а элемент "c" не связан ни с "a", ни с "b". Если бы вы использовали функцию сравнения выше, то она бы объявила вам, что "a = c" и "b = c" (поскольку "c" не связано с "a" или "b"), откуда, в свою очередь, по транзитивности равенства следует, что "a = b", что противоречит "a < b", потому что "a" является необходимым условием для "b". Если ваш компаратор непоследователен или противоречив, вы всегда будете получать искажённые результаты.

Мораль истории: когда вы пишете функцию сравнения, вы должны быть точно уверены в том, какой элемент идёт до, а какой после. Не объявляйте два элемента "равными" друг другу просто потому, что вы не знаете, в каком порядке они должны идти.

4 комментария:

  1. int compare( int a, int b )
    {
    if( a > b + 1 )
    return -1;
    if( a < b - 1 )
    return 1;
    return 0;
    }

    Удовлетворяет всем свойствам, транзитивности равенства нет. Я чего-то не понимаю?

    ОтветитьУдалить
  2. Похоже, ошибка автора. Третье свойство он трактовал как "либо-либо". Откуда и следуют "очевидные" следствия 1 и 2.

    Третье следствие не изменяется, поскольку выводится из условий 1 и 2.

    ОтветитьУдалить
  3. Нет, все-таки скорее моя ошибка. Для моей compare не выполнена требуемая транзитивность.

    compare(1, 2) <= 0
    compare(2, 3) <= 0
    и при этом compare(1, 3) > 0.

    Сорри за невнимательность(

    ОтветитьУдалить
  4. Эх, надо было мне на бумажке проверять. В уме это прикинул, а местами крайние в третьем поменять не догадался.

    ОтветитьУдалить

Можно использовать некоторые HTML-теги, например:

<b>Жирный</b>
<i>Курсив</i>
<a href="http://www.example.com/">Ссылка</a>

Вам необязательно регистрироваться для комментирования - для этого просто выберите из списка "Анонимный" (для анонимного комментария) или "Имя/URL" (для указания вашего имени и ссылки на сайт). Все прочие варианты потребуют от вас входа в вашу учётку (поддерживается OpenID).

Пожалуйста, по возможности используйте "Имя/URL" вместо "Анонимный". URL можно просто не указывать.

Ваше сообщение может быть помечено как спам спам-фильтром - не волнуйтесь, оно появится после проверки администратором.