В компьютерном программировании , А значение сторожевого (также упоминается как значение флага , значение срабатывания , мошенник значение , значение сигнала , или фиктивные данные ) [1] является особым значением в контексте алгоритма , который использует свое присутствие в качестве условия завершение, обычно в цикле или рекурсивном алгоритме.
Контрольное значение - это форма внутриполосных данных, которая позволяет обнаруживать конец данных, когда не предоставляются внеполосные данные (например, явное указание размера). Значение должно быть выбрано таким образом, чтобы оно гарантированно отличалось от всех допустимых значений данных, поскольку в противном случае наличие таких значений преждевременно сигнализировало бы об окончании данных ( проблема полупредиката ). Дозорное значение иногда называют « Слон в Каире » из-за шутки, в котором оно используется в качестве физического дозорного. В безопасных языках большинство контрольных значений можно заменить типами опций , которые обеспечивают явную обработку исключительного случая.
Примеры [ править ]
Некоторые примеры общих дозорных ценностей и их использования:
- Нулевой символ для обозначения конца строки с нулевым символом в конце
- Нулевой указатель для обозначения конца связанного списка или дерева .
- Набор наиболее значимого бита в потоке равноудаленных значений данных, например, набор 8-го бита в потоке 7-битных символов ASCII, хранящихся в 8-битных байтах, указывающих на специальное свойство (например, инверсное видео , жирный шрифт или курсив ) или конец потока
- Отрицательное целое число, обозначающее конец последовательности неотрицательных целых чисел.
Варианты [ править ]
Связанная практика, используемая в несколько иных обстоятельствах, заключается в размещении некоторого определенного значения в конце данных, чтобы избежать необходимости явного теста для завершения в некотором цикле обработки, потому что значение будет запускать завершение уже тестами присутствует по другим причинам. В отличие от вышеупомянутого использования, это не естественный способ хранения или обработки данных, а оптимизация по сравнению с простым алгоритмом, который проверяет завершение. Обычно это используется при поиске. [2] [3]
Например, при поиске определенного значения в несортированном списке каждый элемент будет сравниваться с этим значением, и цикл завершится, когда будет найдено равенство; однако, чтобы справиться со случаем, когда значение должно отсутствовать, необходимо также проверять после каждого шага на предмет неудачного завершения поиска. При добавлении искомого значения в конец списка неудачный поиск становится невозможным, и во внутреннем цикле не требуется явной проверки завершения ; после этого нужно еще решить, было ли найдено истинное совпадение, но этот тест нужно выполнять только один раз, а не на каждой итерации. [4] Кнут называет значение, помещенное таким образом в конец данных, фиктивным значением, а не сигнальным.
Примеры [ править ]
Массив [ править ]
Например, при поиске значения в массиве в C простая реализация выглядит следующим образом; обратите внимание на использование отрицательного числа (недопустимый индекс) для решения проблемы полупредиката с возвратом «нет результата»:
int find ( int arr [], size_t len , int val ) { для ( int i = 0 ; i < len ; i ++ ) if ( arr [ i ] == val ) return i ; возврат -1 ; // не найдено }Однако при этом выполняется два теста на каждой итерации цикла: найдено ли значение и достигнут ли конец массива. Этого последнего теста можно избежать, используя контрольное значение. Предполагая, что массив может быть расширен одним элементом (без выделения памяти или очистки; это более реалистично для связанного списка, как показано ниже), это можно переписать как:
int найти ( int arr [], size_t len , int val ) { int я ; arr [ len ] = val ; // добавляем контрольное значение для ( i = 0 ;; i ++ ) if ( arr [ i ] == val ) break ; если ( я < лен ) вернуть я ; иначе вернуть -1 ; // не найдено }Тест для i < lenвсе еще присутствует, но он был перемещен за пределы цикла, который теперь содержит только один тест (для значения) и гарантированно завершится из-за значения дозорного. При завершении выполняется однократная проверка, было ли достигнуто контрольное значение, которое заменяет тест для каждой итерации.
Также можно временно заменить последний элемент массива часовым и обработать его, особенно если он достигнут:
int найти ( int arr [], size_t len , int val ) { int last ; если ( len == 0 ) вернуть -1 ; last = arr [ len - 1 ]; arr [ len - 1 ] = val ; // добавляем контрольное значение для ( int i = 0 ;; i ++ ) if ( arr [ i ] == val ) break ; arr [ len - 1 ] = последний; если ( arr [ i ] == val ) return i ; иначе вернуть -1 ; // не найдено }См. Также [ править ]
- Канареечное значение
- Сторожевой узел
- Полупредикатная проблема
- Слон в Каире
- Магическое число (программирование)
- Волшебная струна
- Шаблон пустого объекта
- Ошибки форматирования и хранения времени
Ссылки [ править ]
- ^ Кнут, Дональд (1973). Искусство программирования, Том 1: Фундаментальные алгоритмы (второе издание) . Эддисон-Уэсли . стр. 213 -214, а также р. 631. ISBN. 0-201-03809-9.
- ^ Мельхорн, Курт ; Сандерс, Питер (2008). Алгоритмы и структуры данных: базовый набор инструментов 3, представляющий последовательности в виде массивов и связанных списков (PDF) . Springer. ISBN 978-3-540-77977-3.п. 63
- ^ МакКоннелл, Стив (2004). Код завершен (2-е изд.). Редмонд: Microsoft Press. п. 621 . ISBN 0-7356-1967-0.
- ^ Кнут, Дональд (1973). Искусство программирования, Том 3: Сортировка и поиск . Эддисон-Уэсли . п. 395. ISBN 0-201-03803-X.
