Sentinel værdi - Sentinel value

Ikke forveksles med sentinel node eller kanariske værdi .

I computerprogrammering er en sentinel-værdi (også kaldet en flagværdi , tripværdi , rogue-værdi , signalværdi eller dummy-data ) en særlig værdi i forbindelse med en algoritme, der bruger dens tilstedeværelse som en betingelse for afslutning, typisk i en loop eller rekursiv algoritme.

Sentinel-værdien er en form for in-band- data, der gør det muligt at detektere slutningen af ​​dataene, når der ikke gives nogen out-of-band-data (såsom en eksplicit størrelseindikation). Værdien skal vælges på en sådan måde, at den garanteres at være forskellig fra alle juridiske dataværdier, da ellers ville tilstedeværelsen af ​​sådanne værdier for tidligt signalere datens afslutning ( semipredikatproblemet ). En sentinelværdi er undertiden kendt som en " Elefant i Kairo " på grund af en vittighed, hvor denne bruges som en fysisk sentinel. På sikre sprog kunne de fleste sentinelværdier erstattes med optionstyper , som håndhæver eksplicit håndtering af det ekstraordinære tilfælde.

Eksempler

Nogle eksempler på almindelige sentinelværdier og deres anvendelse:

Varianter

En relateret praksis, der anvendes under lidt forskellige omstændigheder, er at placere en bestemt værdi i slutningen af ​​dataene for at undgå behovet for en eksplicit test til afslutning i en eller anden behandlingssløjfe, fordi værdien vil udløse afslutning ved allerede testene til stede af andre grunde. I modsætning til ovenstående anvendelser er dette ikke, hvordan dataene naturligt lagres eller behandles, men er i stedet en optimering sammenlignet med den ligefremme algoritme, der kontrollerer for afslutning. Dette bruges typisk til søgning.

For eksempel, når man søger efter en bestemt værdi på en usorteret liste , sammenlignes hvert element med denne værdi, hvor sløjfen afsluttes, når ligestilling findes; for at behandle sagen om, at værdien skal være fraværende, skal man dog også efter hvert trin teste for at have afsluttet søgningen uden held. Ved at tilføje den søgte værdi til slutningen af ​​listen er en mislykket søgning ikke længere mulig, og der kræves ingen eksplicit afslutningstest i den indre sløjfe ; bagefter skal man stadig beslutte, om der blev fundet et ægte match, men denne test skal kun udføres en gang snarere end ved hver iteration. Knuth kalder den værdi, der er placeret så i slutningen af ​​dataene, en dummy-værdi snarere end en sentinel.

Eksempler

Array

For eksempel, hvis du søger efter en værdi i en matrix i C, er en ligefrem implementering som følger: bemærk brugen af ​​et negativt tal (ugyldigt indeks) til at løse semipredikatproblemet med at returnere "intet resultat": 

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
}

Dette gør dog to tests ved hver iteration af sløjfen: om værdien er fundet, og om slutningen af ​​arrayet er nået. Denne sidstnævnte test er, hvad der undgås ved at bruge en sentinel-værdi. Antages det, at arrayet kan udvides med et element (uden hukommelsesallokering eller oprydning; dette er mere realistisk for en sammenkædet liste, som nedenfor), kan dette omskrives som: 

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
}

Testen for i < len er stadig til stede, men den er flyttet uden for sløjfen, som nu kun indeholder en enkelt test (for værdien) og garanteres at afslutte på grund af sentinelværdien. Der er en enkelt kontrol ved afslutning, hvis sentinelværdien er blevet ramt, som erstatter en test for hver iteration.

Det er også muligt midlertidigt at erstatte det sidste element i arrayet med en sentinel og håndtere det, især hvis det nås: 

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
}

Se også

Referencer