WikiDer > Сторожевое значение

Sentinel value
Не путать с дозорный узел или же канарейка.

В компьютерное программирование, а контрольное значение (также называемый значение флага, стоимость поездки, мошенническая ценность, значение сигнала, или же фиктивные данные)[1] это особенный ценить в контексте алгоритм который использует свое присутствие как условие прекращения, обычно в петля или рекурсивный алгоритм.

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

Примеры

Некоторые примеры общих дозорных ценностей и их использования:

Варианты

Связанная практика, используемая в несколько иных обстоятельствах, заключается в размещении некоторого определенного значения в конце данных, чтобы избежать необходимости явного теста на завершение в некотором цикле обработки, потому что значение будет запускать завершение уже тестами присутствует по другим причинам. В отличие от вышеупомянутого использования, это не естественный способ хранения или обработки данных, а оптимизация по сравнению с простым алгоритмом, который проверяет завершение. Обычно это используется при поиске.[2][3]

Например, при поиске определенного значения в несортированном список, каждый элемент будет сравниваться с этим значением, и цикл завершится, когда будет найдено равенство; однако, чтобы справиться со случаем, когда значение должно отсутствовать, необходимо также проверять после каждого шага на предмет неудачного завершения поиска. При добавлении искомого значения в конец списка неудачный поиск становится невозможным, и явный тест завершения не требуется в внутренний цикл; после этого нужно еще решить, было ли найдено истинное совпадение, но этот тест нужно выполнять только один раз, а не на каждой итерации.[4]Кнут называет значение, помещенное таким образом в конец данных, фиктивная стоимость а не часового.

Примеры

Множество

Например, при поиске значения в массиве на C простая реализация выглядит следующим образом; обратите внимание на использование отрицательного числа (недопустимый индекс) для решения проблемы полупредиката возврата «нет результата»:

int найти(int обр[], size_t len, int вал){    за (int я = 0; я < len; я++)        если (обр[я] == вал)            возвращаться я;    возвращаться -1; // не найден}

Однако при этом на каждой итерации цикла выполняется два теста: было ли найдено значение и достигнут ли конец массива. Этого последнего теста можно избежать, используя контрольное значение. Предполагая, что массив может быть расширен одним элементом (без выделения памяти или очистки; это более реалистично для связанного списка, как показано ниже), это можно переписать как:

int найти(int обр[], size_t len, int вал){    int я;    обр[len] = вал; // добавляем контрольное значение    за (я = 0;; я++)        если (обр[я] == вал)            перемена;    если (я < len)            возвращаться я;    еще            возвращаться -1; // не найден}

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

Также возможно временно заменять последний элемент массива дозорным и обработать его, особенно если он достигнут:

int найти(int обр[], size_t len, int вал){    int последний;    если (len == 0)        возвращаться -1;    последний = обр[len - 1];    обр[len - 1] = вал; // добавляем контрольное значение    за (int я = 0;; я++)        если (обр[я] == вал)            перемена;    обр[len - 1] = последний;    если (обр[я] == вал)            возвращаться я;    еще            возвращаться -1; // не найден}

Смотрите также

Рекомендации

  1. ^ Кнут, Дональд (1973). Искусство программирования, Том 1: Фундаментальные алгоритмы (второе издание). Эддисон-Уэсли. стр.213–214, также с. 631. ISBN 0-201-03809-9.
  2. ^ Мельхорн, Курт; Сандерс, Питер (2008). Алгоритмы и структуры данных: базовый набор инструментов 3, представляющий последовательности в виде массивов и связанных списков (PDF). Springer. ISBN 978-3-540-77977-3. п. 63
  3. ^ МакКоннелл, Стив (2004). Код завершен (2-е изд.). Редмонд: Microsoft Press. п.621. ISBN 0-7356-1967-0.
  4. ^ Кнут, Дональд (1973). Искусство программирования, Том 3: Сортировка и поиск. Эддисон-Уэсли. п. 395. ISBN 0-201-03803-X.