Idempotence - Idempotence

Pojmy v algebře najdete v Idempotent (teorie prstenů) a Idempotent matrix .
On / Off tlačítka vlaku v cílové znamení ovládacího panelu. Stisknutí tlačítka Zapnuto (zelené) je idempotentní operace, protože má stejný účinek, ať už se provádí jednou nebo vícekrát. Stejně tak je stisknutí Vypnuto idempotentní.

Idempotence ( UK : / ˌ ɪ d ɛ m p oʊ t ən s / , USA : / ˌ aɪ d ə m - / ) je vlastnost některých operací v matematiky a výpočetní techniky , přičemž mohou být použity vícekrát aniž by se změnil výsledek nad rámec původní aplikace. Pojem idempotence vzniká na řadě míst v abstraktní algebře (zejména v teorii projektorů auzavíracích operátorů ) a funkční programování (ve kterém je propojeno s vlastností referenční transparentnosti ).

Tento termín zavedl Benjamin Peirce v kontextu prvků algeber, které zůstávají invariantní, když se zvýší na kladnou celočíselnou moc, a doslova znamená „(kvalita mít) stejnou moc“, od idem + potence (stejná + síla).

Definice

Prvek x z množiny S opatřeném binární operátor • se říká, že idempotentních pod • pokud

x • x = x .

O binární operaci • se říká, že je idempotentní, pokud

∀ x ∈ S , x • x = x .

Příklady

Idempotentní funkce

V monoidu ( E E , ∘) funkcí od množiny E k sobě s složením funkcí ∘ jsou idempotentními prvky funkce f : E → E takové, že f ∘ f = f , to je takové, že ∀ x , f ( f ( x )) = f ( x ) (obraz každého prvku v E je pevný bod z f ). Například:

V případě, že množina E má n prvků, můžeme rozdělit do k- vybrán pevných bodech, a n - k ne-pevné body v f , a pak se k n - k je počet různých idempotentních funkcí. S ohledem na všechny možné oddíly tedy

je celkový počet možných idempotentních funkcí v sadě. Číslo sekvence počtu idempotentních funkcí, jak je dána součtem výše pro n = 0, 1, 2, 3, 4, 5, 6, 7, 8, ... začíná s 1, 1, 3, 10, 41, 196 , 1057, 6322, 41393, ... (sekvence A000248 v OEIS ).

Ani vlastnost bytí idempotentní, ani to, že není, není zachována pod složením funkcí. Jako příklad pro první, f ( x ) = x mod 3 a g ( x ) = max ( x , 5) jsou obě idempotentní, ale f ∘ g není, i když g ∘ f se stane. Jako příklad posledně jmenované funkce negace ¬ na booleovské doméně není idempotentní, ale ¬ ∘ ¬ je. Podobně unární negace - () skutečných čísel není idempotentní, ale - () ∘ - () je.

Význam počítačové vědy

Viz také: Referenční průhlednost , Reentrant (podprogram) a Stabilní řazení

V informatice může mít termín idempotence jiný význam v závislosti na kontextu, ve kterém je aplikován:

Toto je velmi užitečná vlastnost v mnoha situacích, protože to znamená, že operaci lze opakovat nebo opakovat tak často, jak je to nutné, aniž by došlo k nechtěným efektům. U neidempotentních operací může být nutné, aby algoritmus sledoval, zda byla operace již provedena nebo ne.

Příklady informatiky

Funkce vyhledávající jméno a adresu zákazníka v databázi je obvykle idempotentní, protože to nezpůsobí změnu databáze. Podobně žádost o změnu adresy zákazníka na XYZ je obvykle idempotentní, protože konečná adresa bude stejná bez ohledu na to, kolikrát je žádost odeslána. Žádost zákazníka o zadání objednávky však obvykle není idempotentní, protože více požadavků povede k zadání více objednávek. Žádost o zrušení konkrétní objednávky je idempotentní, protože bez ohledu na počet žádostí je objednávka zrušena.

Sekvence idempotentních podprogramů, kde se alespoň jeden podprogram liší od ostatních, však nemusí být nutně idempotentní, pokud pozdější podprogram v sekvenci změní hodnotu, na které dřívější podprogram závisí - idempotence není uzavřena pod sekvenčním složením . Předpokládejme například, že počáteční hodnota proměnné je 3 a existuje podprogramová sekvence, která proměnnou přečte, poté ji změní na 5 a poté znovu načte. Každý krok v sekvenci je idempotentní: oba kroky čtení proměnné nemají žádné vedlejší účinky a krok změny proměnné na 5 bude mít vždy stejný účinek bez ohledu na to, kolikrát se provede. Nicméně provedení celé sekvence jednou vytvoří výstup (3, 5), ale jeho provedení podruhé vytvoří výstup (5, 5), takže sekvence není idempotentní. 

int x = 3;
void read() { printf("%d\n", x); }
void change() { x = 5; }
void sequence() { read(); change(); read(); }

int main() {
  sequence();  // prints "3\n5\n"
  sequence();  // prints "5\n5\n"
  return 0;
}

V protokolu HTTP ( Hypertext Transfer Protocol ) jsou idempotence a bezpečnost hlavními atributy, které oddělují metody HTTP . Z hlavních metod HTTP by GET, PUT a DELETE měly být implementovány idempotentním způsobem podle standardu, ale POST nemusí být. GET načte stav zdroje; PUT aktualizuje stav zdroje; a DELETE odstraní zdroj. Stejně jako ve výše uvedeném příkladu nemá čtení dat obvykle žádné vedlejší účinky, proto je idempotentní (ve skutečnosti nulové ). Aktualizace a odstraňování daných dat jsou obvykle idempotentní, pokud požadavek jednoznačně identifikuje zdroj a v budoucnu pouze tento zdroj. PUT a DELETE s jedinečnými identifikátory redukují na jednoduchý případ přiřazení proměnné buď hodnoty, nebo hodnoty null, respektive, a jsou idempotentní ze stejného důvodu; konečný výsledek je vždy stejný jako výsledek počátečního spuštění, i když se odpověď liší.

Porušení požadavku na jedinečnou identifikaci při ukládání nebo vymazání obvykle způsobí porušení idempotence. Například ukládání nebo mazání dané sady obsahu bez zadání jedinečného identifikátoru: POST požadavky, které nemusí být idempotentní, často neobsahují jedinečné identifikátory, takže vytvoření identifikátoru je delegováno na přijímací systém, který následně vytvoří odpovídající nový záznam. Podobně požadavky PUT a DELETE s nespecifickými kritérii mohou mít za následek různé výsledky v závislosti na stavu systému - například požadavek na odstranění nejnovějšího záznamu. V každém případě budou následná spuštění dále upravovat stav systému, takže nejsou idempotentní.

Při zpracování toku událostí označuje idempotence schopnost systému produkovat stejný výsledek, i když je stejný soubor, událost nebo zpráva přijata více než jednou.

V architektuře load -store jsou instrukce, které by mohly způsobit poruchu stránky, idempotentní. Pokud tedy dojde k chybě stránky, operační systém může načíst stránku z disku a poté jednoduše znovu spustit chybnou instrukci. V procesoru, kde takové pokyny nejsou idempotentní, je řešení chyb stránek mnohem složitější.

Při přeformátování výstupu se očekává , že pěkný tisk bude idempotentní. Jinými slovy, pokud je výstup již „hezký“, pro hezkou tiskárnu by nemělo být co dělat.

V architektuře orientované na služby (SOA) lze vícestupňový orchestrační proces složený výhradně z idempotentních kroků přehrát bez vedlejších efektů, pokud některá část tohoto procesu selže.

Mnoho operací, které jsou idempotentní, často má způsoby, jak „obnovit“ proces, pokud je přerušen - způsoby, které končí mnohem rychleji, než začít úplně od začátku. Například obnovení přenosu souborů , synchronizace souborů , vytvoření sestavení softwaru , instalace aplikace a všech jejích závislostí pomocí správce balíčků atd.

Aplikované příklady

Typické tlačítko pro přechod pro chodce je příkladem idempotentního systému

Aplikované příklady, se kterými se mnoho lidí může setkat ve svém každodenním životě, zahrnují tlačítka pro volání výtahu a tlačítka pro přechod pro chodce . Počáteční aktivace tlačítka přesune systém do žádajícího stavu, dokud není požadavek uspokojen. Následné aktivace tlačítka mezi počáteční aktivací a uspokojením požadavku nemají žádný účinek, pokud není systém navržen tak, aby upravil čas pro uspokojení požadavku na základě počtu aktivací.

Viz také

Reference

Další čtení