Hodnota hlídky - Sentinel value

v programování, a sentinelová hodnota (označované také jako a hodnota příznaku, hodnota vypnutí, nepoctivá hodnota, hodnota signálunebo fiktivní data)^[1] je speciální hodnota v kontextu algoritmus který používá svou přítomnost jako podmínku ukončení, obvykle v a smyčka nebo rekurzivní algoritmus.

Hodnota strážného je formou v pásmu data, která umožňují detekovat konec dat, když ne out-of-band data (například výslovné označení velikosti). Hodnota by měla být zvolena takovým způsobem, aby bylo zaručeno, že se bude lišit od všech hodnot zákonných údajů, protože v opačném případě by přítomnost těchto hodnot předčasně signalizovala konec údajů ( polopredikátový problém ). Hodnota strážného je někdy známá jako „Slon v Káhiře „kvůli vtipu, kde se používá jako fyzický indikátor. V bezpečných jazycích lze většinu hodnot indikátorů nahradit typy možností, které vynucují výslovné řešení výjimečného případu.

Příklady

Některé příklady běžných hodnot sentinelových hodnot a jejich použití:

Nulový charakter pro označení konce a řetězec zakončený nulou
Nulový ukazatel pro označení konce a spojový seznam nebo a strom.
Sada nejvýznamnější bit v proudu rovnoměrně rozmístěných datových hodnot, například sada 8. bitu v proudu 7 bitů ASCII znaky uložené v 8bitovém formátu bajtů označující speciální vlastnost (jako inverzní video, tučně nebo kurzíva ) nebo konec streamu
Záporné celé číslo pro označení konce sekvence nezáporných celých čísel

Varianty

Souvisejícím postupem, který se používá za mírně odlišných okolností, je umístit určitou specifickou hodnotu na konec dat, aby se předešlo potřebě explicitního testu pro ukončení v některé smyčce zpracování, protože tato hodnota již ukončí testy již přítomný z jiných důvodů. Na rozdíl od výše uvedeného použití to není způsob, jakým jsou data přirozeně ukládána nebo zpracovávána, ale je to místo toho optimalizace ve srovnání s přímým algoritmem, který kontroluje ukončení. To se obvykle používá při vyhledávání.^[2]^[3]

Například při hledání konkrétní hodnoty v netříděném stavu seznam, každý prvek bude porovnán s touto hodnotou, přičemž smyčka bude ukončena, když bude nalezena rovnost; Abychom se však mohli vypořádat s případem, že by hodnota měla chybět, je třeba po každém kroku také otestovat neúspěšné dokončení hledání. Připojením hledané hodnoty na konec seznamu již není možné neúspěšné hledání a v testu se nevyžaduje explicitní test ukončení. vnitřní smyčka; poté je stále nutné rozhodnout, zda byla nalezena skutečná shoda, ale tento test je třeba provést pouze jednou, nikoli při každé iteraci.^[4]Knuth volá takto umístěnou hodnotu na konci dat, a fiktivní hodnota spíše než hlídka.

Příklady

Pole

Například pokud hledáte hodnotu v poli v C, přímá implementace je následující; Všimněte si použití záporného čísla (neplatný index) k vyřešení problému polopredikátu vrácení "žádný výsledek":

int nalézt(int přílet[], size_t len, int val){    pro (int i = 0; i < len; i++)        -li (přílet[i] == val)            vrátit se i;    vrátit se -1; // nenalezeno}

To však dělá dva testy při každé iteraci smyčky: zda byla nalezena hodnota a zda bylo dosaženo konce pole. Této druhé zkoušce se lze vyhnout použitím ověřovací hodnoty. Za předpokladu, že pole může být rozšířeno o jeden prvek (bez přidělení paměti nebo vyčištění; toto je realističtější pro propojený seznam, jak je uvedeno níže), lze jej přepsat jako:

int nalézt(int přílet[], size_t len, int val){    int i;    přílet[len] = val; // přidat hodnotu strážného    pro (i = 0;; i++)        -li (přílet[i] == val)            přestávka;    -li (i < len)            vrátit se i;    jiný            vrátit se -1; // nenalezeno}

Test pro i je stále přítomen, ale byl přesunut mimo smyčku, která nyní obsahuje pouze jeden test (pro hodnotu), a je zaručeno, že bude ukončena kvůli hodnotě sentinel. Existuje jedna kontrola ukončení, pokud byla zasažena hodnota sentinel, která nahradí test pro každou iteraci.

Je také možné dočasně nahradit poslední prvek pole hlídkou a zpracovat jej, zvláště pokud je dosaženo:

int nalézt(int přílet[], size_t len, int val){    int poslední;    -li (len == 0)        vrátit se -1;    poslední = přílet[len - 1];    přílet[len - 1] = val; // přidat hodnotu strážného    pro (int i = 0;; i++)        -li (přílet[i] == val)            přestávka;    přílet[len - 1] = poslední;    -li (přílet[i] == val)            vrátit se i;    jiný            vrátit se -1; // nenalezeno}

`Viz také`

`Reference`

^ Knuth, Donald (1973). The Art of Computer Programming, Volume 1: Fundamental Algorithms (druhé vydání). Addison-Wesley. str.213 –214, také str. 631. ISBN 0-201-03809-9.
^ Mehlhorn, Kurt; Sanders, Peter (2008). Algoritmy a datové struktury: Základní sada nástrojů 3 Reprezentující sekvence podle polí a propojených seznamů (PDF). Springer. ISBN 978-3-540-77977-3. str. 63
^ McConnell, Steve (2004). Kód dokončen (2. vyd.). Redmond: Microsoft Press. str.621. ISBN 0-7356-1967-0.
^ Knuth, Donald (1973). Umění počítačového programování, svazek 3: Třídění a vyhledávání. Addison-Wesley. str. 395. ISBN 0-201-03803-X.

[1] ^ Knuth, Donald (1973). The Art of Computer Programming, Volume 1: Fundamental Algorithms (druhé vydání). Addison-Wesley. str.213 –214, také str. 631. ISBN 0-201-03809-9.

[2] ^ Mehlhorn, Kurt; Sanders, Peter (2008). Algoritmy a datové struktury: Základní sada nástrojů 3 Reprezentující sekvence podle polí a propojených seznamů (PDF). Springer. ISBN 978-3-540-77977-3. str. 63

[3] ^ McConnell, Steve (2004). Kód dokončen (2. vyd.). Redmond: Microsoft Press. str.621. ISBN 0-7356-1967-0.

[4] ^ Knuth, Donald (1973). Umění počítačového programování, svazek 3: Třídění a vyhledávání. Addison-Wesley. str. 395. ISBN 0-201-03803-X.

[1]

[2]

[3]

[4]