Valor sentinela - Sentinel value

Não deve ser confundido com linfonodo sentinela ou valor canário .

Em programação de computador , um valor de sentinela (também referido como um valor da bandeira , valor viagem , valor desonestos , valor do sinal , ou dados fictício ) é um especial valor no contexto de um algoritmo que utiliza a sua presença como uma condição de terminação, tipicamente em um loop ou algoritmo recursivo.

O valor sentinela é uma forma de dados dentro da banda que torna possível detectar o fim dos dados quando nenhum dado fora da banda (como uma indicação explícita de tamanho) é fornecido. O valor deve ser selecionado de forma que seja garantido que ele seja distinto de todos os valores de dados legais, pois do contrário, a presença de tais valores sinalizaria prematuramente o fim dos dados (o problema do semipredicado ). Um valor sentinela é às vezes conhecido como " Elefante no Cairo ", devido a uma piada em que é usado como sentinela física. Em linguagens seguras, a maioria dos valores sentinela podem ser substituídos por tipos de opção , que impõem tratamento explícito do caso excepcional.

Exemplos

Alguns exemplos de valores sentinela comuns e seus usos:

Variantes

Uma prática relacionada, usada em circunstâncias ligeiramente diferentes, é colocar algum valor específico no final dos dados, a fim de evitar a necessidade de um teste explícito de encerramento em algum loop de processamento, porque o valor irá desencadear o encerramento pelos testes já presente por outros motivos. Ao contrário dos usos acima, não é assim que os dados são armazenados ou processados ​​naturalmente, mas sim uma otimização, em comparação com o algoritmo direto que verifica o término. Isso normalmente é usado em pesquisas.

Por exemplo, ao pesquisar um valor específico em uma lista não classificada , cada elemento será comparado a esse valor, com o loop terminando quando a igualdade for encontrada; porém, para tratar do caso de o valor estar ausente, deve-se também testar após cada etapa se a busca foi concluída sem sucesso. Ao anexar o valor pesquisado ao final da lista, uma pesquisa malsucedida não é mais possível e nenhum teste de encerramento explícito é necessário no loop interno ; depois, ainda é necessário decidir se uma correspondência verdadeira foi encontrada, mas esse teste precisa ser executado apenas uma vez, em vez de a cada iteração. Knuth chama o valor assim colocado no final dos dados, um valor fictício em vez de um sentinela.

Exemplos

Array

Por exemplo, se estiver procurando por um valor em uma matriz em C, uma implementação direta será a seguinte; observe o uso de um número negativo (índice inválido) para resolver o problema do semipredicado de retornar "nenhum resultado": 

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
}

No entanto, isso faz dois testes em cada iteração do loop: se o valor foi encontrado e se o fim do array foi atingido. Este último teste é o que é evitado usando um valor sentinela. Assumindo que a matriz pode ser estendida por um elemento (sem alocação de memória ou limpeza; isso é mais realista para uma lista vinculada, conforme abaixo), isso pode ser reescrito como: 

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
}

O teste para i < len ainda está presente, mas foi movido para fora do loop, que agora contém apenas um único teste (para o valor) e tem a garantia de terminar devido ao valor sentinela. Há uma única verificação na rescisão se o valor da sentinela foi atingido, que substitui um teste para cada iteração.

Também é possível substituir temporariamente o último elemento da matriz por um sentinela e tratá-lo, especialmente se for alcançado: 

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
}

Veja também

Referências