Дозорное значение

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

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

Примеры

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

Нулевой символ для обозначения конца строки, завершающейся нулем .
Нулевой указатель для обозначения конца связанного списка или дерева .
Установленный старший бит в потоке значений данных с одинаковым интервалом между ними, например, установленный 8-й бит в потоке 7-битных символов ASCII , хранящихся в 8-битных байтах, указывающих специальное свойство (например, инверсное видео , жирный шрифт или курсив ) или конец потока.
Отрицательное целое число, обозначающее конец последовательности неотрицательных целых чисел.

Варианты

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

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

Примеры

Множество

Например, при поиске значения в массиве в 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

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

См. также

Ссылки

^ Мельхорн, Курт ; Сандерс, Питер (2008). «3. Представление последовательностей массивами и связанными списками» (PDF) . Алгоритмы и структуры данных: базовый набор инструментов . Спрингер. п. 63. ИСБН 978-3-540-77977-3 .
^ МакКоннелл, Стив (2004). Код завершен (2-е изд.). Редмонд: Microsoft Press. п. 621. ИСБН 0-7356-1967-0 .
^ Кнут, Дональд (1973). Сортировка и поиск . Искусство компьютерного программирования . Том. 3. Аддисон-Уэсли . п. 395. ИСБН 0-201-03803-Х .

[1] Мельхорн, Курт ; Сандерс, Питер (2008). «3. Представление последовательностей массивами и связанными списками» (PDF) . Алгоритмы и структуры данных: базовый набор инструментов . Спрингер. п. 63. ИСБН 978-3-540-77977-3 .

[2] МакКоннелл, Стив (2004). Код завершен (2-е изд.). Редмонд: Microsoft Press. п. 621. ИСБН 0-7356-1967-0 .

[3] Кнут, Дональд (1973). Сортировка и поиск . Искусство компьютерного программирования . Том. 3. Аддисон-Уэсли . п. 395. ИСБН 0-201-03803-Х .

[1]

[2]

[3]