Сторожевое значение - Sentinel value

Не путать со сторожевым узлом или канареечным значением .

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

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

Примеры

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

Варианты

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

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

Примеры

Массив

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

int find(int arr[], size_t len, int val)
{
    for (int i = 0; i < len; i++)
        if (arr[i] == val)
            return i;
    return -1; // not found
}

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

int find(int arr[], size_t len, int val)
{
    int i;

    arr[len] = val; // add sentinel value
    for (i = 0;; i++)
        if (arr[i] == val)
            break;
    if (i < len)
            return i;
    else
            return -1; // not found
}

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

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

int find(int arr[], size_t len, int val)
{
    int last;

    if (len == 0)
        return -1;
    last = arr[len - 1];
    arr[len - 1] = val; // add sentinel value
    for (int i = 0;; i++)
        if (arr[i] == val)
            break;
    arr[len - 1] = last;
    if (arr[i] == val)
            return i;
    else
            return -1; // not found
}

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

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