Valore sentinella - Sentinel value

Da non confondere con il nodo sentinella o il valore canarino .

In programmazione di computer , un valore sentinella (indicato anche come un valore di flag , valore di intervento , valore ladro , valore del segnale , o dati fittizi ) è una speciale valore nel contesto di un algoritmo che utilizza la sua presenza come condizione di terminazione, tipicamente in un ciclo o algoritmo ricorsivo.

Il valore sentinella è una forma di dati in banda che consente di rilevare la fine dei dati quando non vengono forniti dati fuori banda (come un'indicazione esplicita della dimensione). Il valore dovrebbe essere selezionato in modo tale da garantire che sia distinto da tutti i valori dei dati legali poiché altrimenti la presenza di tali valori segnalerebbe prematuramente la fine dei dati (il problema semipredicato ). Un valore di sentinella è talvolta noto come " Elefante al Cairo ", a causa di uno scherzo in cui viene usato come sentinella fisica. Nelle lingue sicure, la maggior parte dei valori sentinella potrebbe essere sostituita con tipi di opzioni , che impongono una gestione esplicita del caso eccezionale.

Esempi

Alcuni esempi di valori sentinella comuni e dei loro usi:

Varianti

Una pratica correlata, utilizzata in circostanze leggermente diverse, è quella di inserire un valore specifico alla fine dei dati, al fine di evitare la necessità di un test esplicito per la terminazione in qualche ciclo di elaborazione, perché il valore innescherà già la terminazione dai test presente per altri motivi. A differenza degli usi precedenti, questo non è il modo in cui i dati vengono archiviati o elaborati naturalmente, ma è invece un'ottimizzazione, rispetto al semplice algoritmo che controlla la terminazione. Questo è in genere utilizzato nella ricerca.

Ad esempio, quando si cerca un valore particolare in un elenco non ordinato , ogni elemento verrà confrontato con questo valore, con il ciclo che termina quando viene trovata l'uguaglianza; tuttavia, per affrontare il caso in cui il valore debba essere assente, è necessario anche testare dopo ogni passaggio per aver completato la ricerca senza successo. Aggiungendo il valore cercato alla fine della lista, una ricerca non riuscita non è più possibile e non è richiesto alcun test di terminazione esplicito nel ciclo interno ; in seguito, si deve ancora decidere se è stata trovata una corrispondenza vera, ma questo test deve essere eseguito solo una volta anziché ad ogni iterazione. Knuth chiama il valore così posto alla fine dei dati, un valore fittizio piuttosto che una sentinella.

Esempi

Vettore

Ad esempio, se si cerca un valore in un array in C, un'implementazione semplice è la seguente; notare l'uso di un numero negativo (indice non valido) per risolvere il problema semipredicato di restituire "nessun risultato": 

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
}

Tuttavia, questo esegue due test ad ogni iterazione del ciclo: se il valore è stato trovato e se è stata raggiunta la fine dell'array. Quest'ultimo test è ciò che si evita utilizzando un valore sentinella. Supponendo che l'array possa essere esteso di un elemento (senza allocazione di memoria o pulizia; questo è più realistico per un elenco collegato, come di seguito), questo può essere riscritto come: 

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
}

Il test for i < len è ancora presente, ma è stato spostato all'esterno del loop, che ora contiene un solo test (per il valore), ed è garantito che terminerà a causa del valore sentinel. C'è un unico controllo alla terminazione se il valore sentinella è stato raggiunto, che sostituisce un test per ogni iterazione.

È anche possibile sostituire temporaneamente l'ultimo elemento dell'array con una sentinella e gestirlo, soprattutto se raggiunto: 

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
}

Guarda anche

Riferimenti