Idempotencja - Idempotence

On / Off przycisków pociągu za znak przeznaczenia panelu sterowania. Naciśnięcie przycisku Włącz (zielony) jest operacją idempotentną, ponieważ ma ten sam efekt, niezależnie od tego, czy jest wykonywana raz, czy wiele razy. Podobnie naciśnięcie Off jest idempotentne.

Idempotentność ( UK : / ˌ ɪ d ɛ m P t ən s / , USA : / ˌ d ə m - / ) jest właściwością niektórych operacji w matematyce oraz informatyce przy czym mogą one być stosowane kilka razy, bez zmieniania wynik wykraczający poza początkowe zastosowanie. Pojęcie idempotencji pojawia się w wielu miejscach w algebrze abstrakcyjnej (w szczególności w teorii rzutników i operatorów domknięcia ) oraz w programowaniu funkcjonalnym (w którym wiąże się z właściwością przezroczystości referencyjnej ).

Termin ten został wprowadzony przez Benjamina Peirce'a w kontekście elementów algebr, które pozostają niezmienne po podniesieniu do dodatniej potęgi całkowitej i dosłownie oznacza „( cecha posiadania) tej samej potęgi”, od idem + moc (ta sama + potęga).

Definicja

Elementem x zestawu S wyposażony operatora binarnego • mówi się idempotentnych pod • jeżeli

xx = x .

Operacja binarna • mówi się, że jest idempotentna, jeśli

xS , xx = x .

Przykłady

Funkcje idempotentne

W monoidzie ( E E , ∘ ) funkcji ze zbioru E do siebie ze złożeniem funkcji ∘ , elementami idempotentnymi są funkcje f : EE takie, że ff = f , czyli takie, że x , f ( f ( x )) = f ( x ) (obraz każdego elementu E jest punktem stałym w f ). Na przykład:

Jeśli zbiór E ma n elementów, możemy podzielić go na k wybranych punktów stałych i nk punktów niestałych pod f , a wtedy k nk jest liczbą różnych funkcji idempotentnych. Stąd biorąc pod uwagę wszystkie możliwe podziały,

to całkowita liczba możliwych idempotentnych funkcji na zestawie. Sekwencja całkowitą od liczby funkcji idempotentnych podaną przez sumę powyżej dla n = 0, 1, 2, 3, 4, 5, 6, 7, 8, ... rozpoczyna się 1, 1, 3, 10, 41, 196 , 1057, 6322, 41393, … (sekwencja A000248 w OEIS ).

Ani właściwość bycia idempotentnym, ani bycia nie jest zachowana w kompozycji funkcji. Na przykład w przypadku pierwszego f ( x ) = x mod 3 i g ( x ) = max ( x , 5) są idempotent, ale Fg nie jest jednak gF zdarza się. Jako przykład dla tego ostatniego, funkcja negacji ¬ w domenie Boole'a nie jest idempotentna, ale ¬ ∘ ¬ jest. Podobnie, jednoargumentowa negacja −( ) liczb rzeczywistych nie jest idempotentna, ale −( ) ∘ −( ) jest.

Znaczenie informatyki

W informatyce termin idempotencja może mieć różne znaczenie w zależności od kontekstu, w jakim jest stosowany:

Jest to bardzo przydatna właściwość w wielu sytuacjach, ponieważ oznacza, że ​​operację można powtarzać lub ponawiać tak często, jak to konieczne, bez powodowania niezamierzonych skutków. W przypadku operacji nieidempotentnych algorytm może być zmuszony do śledzenia, czy operacja została już wykonana, czy nie.

Przykłady informatyki

Funkcja wyszukująca nazwę i adres klienta w bazie danych jest zazwyczaj idempotentna, ponieważ nie spowoduje to zmiany bazy danych. Podobnie prośba o zmianę adresu klienta na XYZ jest zazwyczaj idempotentna, ponieważ ostateczny adres będzie taki sam bez względu na to, ile razy zostanie złożone żądanie. Jednak prośba klienta o złożenie zamówienia zazwyczaj nie jest idempotentna, ponieważ wiele żądań doprowadzi do złożenia wielu zamówień. Prośba o anulowanie konkretnego zamówienia jest idempotentna, ponieważ bez względu na to, ile żądań zostanie złożonych, zamówienie pozostaje anulowane.

Sekwencja idempotentnych podprogramów, w których co najmniej jeden podprogram różni się od pozostałych, nie musi być jednak koniecznie idempotentna, jeśli późniejszy podprogram w sekwencji zmienia wartość, od której zależy wcześniejszy podprogram — idempotentność nie jest zamykana przy składaniu sekwencyjnym . Załóżmy na przykład, że początkowa wartość zmiennej to 3 i istnieje sekwencja podprogramu, która odczytuje zmienną, następnie zmienia ją na 5, a następnie ponownie ją odczytuje. Każdy krok w sekwencji jest idempotentny: oba kroki odczytu zmiennej nie mają skutków ubocznych, a krok zmieniający zmienną na 5 będzie zawsze miał ten sam efekt, bez względu na to, ile razy zostanie wykonany. Niemniej jednak wykonanie całej sekwencji raz daje wynik (3, 5), ale wykonanie go po raz drugi daje wynik (5, 5), więc sekwencja nie jest idempotentna.

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;
}

W protokole Hypertext Transfer Protocol (HTTP) idempotencja i bezpieczeństwo to główne atrybuty, które oddzielają metody HTTP . Z głównych metod HTTP, GET, PUT i DELETE powinny być zaimplementowane w sposób idempotentny zgodnie ze standardem, ale POST nie musi. GET pobiera stan zasobu; PUT aktualizuje stan zasobu; a DELETE usuwa zasób. Tak jak w powyższym przykładzie, odczytywanie danych zwykle nie ma skutków ubocznych, więc jest idempotentne (w rzeczywistości nullipotentne ). Aktualizowanie i usuwanie danych danych jest zwykle idempotentne, o ile żądanie jednoznacznie identyfikuje zasób i tylko ten zasób w przyszłości. PUT i DELETE z unikalnymi identyfikatorami ograniczają się do prostego przypadku przypisania do zmiennej odpowiednio wartości lub wartości null i są idempotentne z tego samego powodu; wynik końcowy jest zawsze taki sam jak wynik początkowego wykonania, nawet jeśli odpowiedź jest inna.

Naruszenie wymogu unikatowej identyfikacji podczas przechowywania lub usuwania zazwyczaj powoduje naruszenie idempotencji. Na przykład przechowywanie lub usuwanie danego zestawu treści bez określenia unikalnego identyfikatora: żądania POST, które nie muszą być idempotentne, często nie zawierają unikalnych identyfikatorów, więc utworzenie identyfikatora jest delegowane do systemu odbierającego, który następnie tworzy odpowiedni nowy rekord. Podobnie żądania PUT i DELETE z nieokreślonymi kryteriami mogą skutkować różnymi wynikami w zależności od stanu systemu - na przykład żądanie usunięcia najnowszego rekordu. W każdym przypadku kolejne wykonania będą dalej modyfikować stan systemu, więc nie są idempotentne.

W przetwarzaniu strumienia zdarzeń idempotencja odnosi się do zdolności systemu do generowania tego samego wyniku, nawet jeśli ten sam plik, zdarzenie lub komunikat są odbierane więcej niż raz.

W architekturze load-store instrukcje, które mogą spowodować błąd strony, są idempotentne. Jeśli więc wystąpi błąd strony, system operacyjny może załadować stronę z dysku, a następnie po prostu ponownie wykonać błędną instrukcję. W procesorze, w którym takie instrukcje nie są idempotentne, radzenie sobie z błędami stron jest znacznie bardziej złożone.

Podczas ponownego formatowania wydruku oczekuje się , że ładne drukowanie będzie idempotentne. Innymi słowy, jeśli wydruk jest już „ładny”, nie powinno być nic do roboty dla ładnej drukarki.

W architekturze zorientowanej na usługi (SOA) wieloetapowy proces orkiestracji składający się wyłącznie z idempotentnych kroków może zostać odtworzony bez skutków ubocznych, jeśli jakakolwiek część tego procesu zawiedzie.

Wiele operacji, które są idempotentne, często ma sposoby na „wznowienie” procesu, jeśli zostanie on przerwany – sposoby, które kończą się znacznie szybciej niż rozpoczynanie wszystkiego od początku. Na przykład wznawianie transferu plików , synchronizowanie plików , tworzenie kompilacji oprogramowania , instalowanie aplikacji i wszystkich jej zależności za pomocą menedżera pakietów itp.

Zastosowane przykłady

Typowy przycisk przejścia dla pieszych jest przykładem systemu idempotentnego

Przykładami, z którymi wiele osób może się spotkać w swoim codziennym życiu, są przyciski wywołania windy i przyciski przejścia dla pieszych . Początkowa aktywacja przycisku przenosi system w stan żądania, aż żądanie zostanie spełnione. Kolejne aktywacje przycisku między początkową aktywacją a spełnieniem żądania nie przynoszą efektu, chyba że system jest zaprojektowany tak, aby dostosować czas realizacji żądania na podstawie liczby aktywacji.

Zobacz też

Bibliografia

Dalsza lektura