Как сторожевой узел предлагает преимущества по сравнению с NULL?

Question

На странице Википедия Sentinel Node говорится, что преимущества дозорного узла по сравнению с NULL:

• Увеличена скорость операций
• Уменьшенный размер алгоритмического кода
• Повышение надежности структуры данных (возможно).

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

1. Что делает дозорный узел лучше, чем NULL?
2. Как бы вы реализовали дозорный узел (например) в списке?

Answer 1

Я думаю, что маленький пример кода был бы лучшим объяснением, чем теоретическое обсуждение.

Ниже приведен код удаления узла в двусвязном списке узлов, где NULL используется для обозначенияконец списка и где два указателя first и last используются для хранения адреса первого и последнего узла:

// Using NULL and pointers for first and last
if (n->prev) n->prev->next = n->next;
        else first = n->next;
if (n->next) n->next->prev = n->prev;
        else last = n->prev;

, и это тот же код, где вместо него есть специальный фиктивныйузел для обозначения конца списка, где адрес первого узла в списке хранится в поле next специального узла, а последний узел в списке хранится в поле prev специального манекенаузел:

// Using the dummy node
n->prev->next = n->next;
n->next->prev = n->prev;

То же самое упрощение также присутствует для вставки узла;например, чтобы вставить узел n перед узлом x (имеющий x == NULL или x == &dummy, означающий вставку в последнюю позицию), код будет:

// Using NULL and pointers for first and last
n->next = x;
n->prev = x ? x->prev : last;
if (n->prev) n->prev->next = n;
        else first = n;
if (n->next) n->next->prev = n;
        else last = n;

и

// Using the dummy node
n->next = x;
n->prev = x->prev;
n->next->prev = n;
n->prev->next = n;

Как вы видите, подход фиктивного узла удален для двусвязного списка всех особых случаев и всех условий.

На следующем рисунке представлены два подхода для одного и того же списка в памяти ...

Answer 2

У дозорных нет никакого преимущества, если вы просто выполняете простую итерацию и не смотрите на данные в элементах.

Однако, есть некоторая реальная выгода при использовании ее для алгоритмов типа «найти».Например, представьте список связанных списков std::list, в котором вы хотите найти определенное значение x.

. Что бы вы сделали без часовых:

for (iterator i=list.begin(); i!=list.end(); ++i) // first branch here
{
  if (*i == x) // second branch here
    return i;
}
return list.end();

Но с часовыми (конечно, end на самом деле должен быть реальным узлом для этого ...):

iterator i=list.begin();
*list.end() = x;

while (*i != x) // just this branch!
  ++i;

return i;

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

Для другого интересного и действительно полезного применения часовых смотрите "intro-sort", котораяалгоритм сортировки, который используется в большинстве std::sort реализаций.У него есть классный вариант алгоритма разбиения, который использует часовые для удаления нескольких веток.

Answer 3

Ответ на ваш вопрос (1) находится в последнем предложении связанной записи Википедии: "Поскольку узлы, которые обычно ссылаются на NULL, теперь ссылаются на" nil "(включая сам nil), это устраняет необходимостьдля дорогостоящей операции ветвления для проверки на NULL. "

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

Answer 4

Давайте сначала отложим стражу.С точки зрения сложности кода, для ответа в ltjax он предоставляет нам код

for (iterator i=list.begin(); i!=list.end(); ++i) // first branch here
{
  if (*i == x) // second branch here
    return i;
}
return list.end();

Код может быть лучше сформирован как:

auto iter = list.begin();
while(iter != list.end() && *iter != x)
    ++iter;
return iter;

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

Дело в том, что используемый здесь страж не для уменьшения сложности кода, а для того, чтобы уменьшить проверку индекса в каждом цикле.Для линейного поиска мы начинаем с проверки, является ли индекс допустимым диапазоном, и если в, то проверяем, соответствует ли значение тому, что мы хотим, без использования sentinel.Но с часовым, который находится в конце с желаемым значением, мы можем обойтись без проверки границы индекса, а только с проверкой значения, поскольку цикл гарантированно завершится.Это относится к управляемому дозорному циклу: повторяйте до тех пор, пока не увидите желаемое значение.

Рекомендуем прочитать: Введение в алгоритмы, третье издание, и если у вас есть формат pdf, просто найдите ключевое слово sentinel, чтобы получить все.На самом деле, этот пример такой лаконичный и интригующий.Обсуждения о том, как охотиться на слона и слона в Каире, могут вас заинтересовать.Конечно, я не говорю об охоте на слонов в реальности.

Answer 5

Я постараюсь ответить в контексте стандартной библиотеки шаблонов:

1) При вызове "next ()" NULL не обязательно указывает конец списка.Что делать, если произошла ошибка памяти?Возврат сторожевого узла - это точный способ указать, что произошел конец списка, а не какой-либо другой результат.Другими словами, NULL может указывать на разные вещи, а не только на конец списка.

2) Это всего лишь один из возможных методов: при создании списка создайте частный узел, который не используется совместно за пределамикласса (называется "lastNode", например).Обнаружив, что вы выполнили итерацию до конца списка, пусть "next ()" возвращает ссылку на "lastNode".Также есть метод с именем "end ()", возвращающий ссылку на "lastNode".Наконец, в зависимости от того, как вы реализуете свой класс, вам может потребоваться переопределить оператор сравнения, чтобы он работал правильно.

Пример:

class MyNode{

};

class MyList{

public:
    MyList () : lastNode();

    MyNode * next(){

       if (isLastNode) return &lastNode;
       else return //whatever comes next
    }

    MyNode * end() {

       return &lastNode;
    }

    //comparison operator
    friend bool operator == (MyNode &n1, MyNode &n2){

        return (&n1 == &n2); //check that both operands point to same memory
    }


private:
    MyNode lastNode;
};


int main(){

  MyList list;
  MyNode * node = list.next();

  while ( node != list.end() ){ 

     //do stuff!

     node = list.next();
  }

  return 0; 
}