Jaki jest termin na funkcję, która przy wielokrotnym wywołaniu ma taki sam efekt jak wywołanie raz?

96

(Zakładając, że środowisko jednowątkowe)

Funkcja spełniająca to kryterium to:

bool MyClass::is_initialized = false;

void MyClass::lazy_initialize()
{
    if (!is_initialized)
    {
        initialize(); //Should not be called multiple times
        is_initialized = true;
    }
}

Zasadniczo mogę wywoływać tę funkcję wiele razy i nie martw się, że zainicjuje się MyClasswiele razy

Funkcją niespełniającą tego kryterium może być:

Foo* MyClass::ptr = NULL;

void initialize()
{
    ptr = new Foo();
}

initialize()Wielokrotne wywołanie spowoduje wyciek pamięci

Motywacja

Byłoby miło mieć jedno zwięzłe słowo opisujące to zachowanie, aby funkcje, które powinny spełniać to kryterium, mogły zostać należycie skomentowane (szczególnie przydatne przy opisywaniu funkcji interfejsu, które powinny zostać zastąpione)

Rufus
źródło
67
Do najbliższych wyborców: chociaż prawdą jest, że 99,999% (przybliżone oszacowanie) wszystkich pytań typu „nazwa-rzecz” jest nie na temat, ponieważ nie ma jednej, poprawnej, jednoznacznej, obiektywnej odpowiedzi oraz nazewnictwa jest czysto subiektywna i na podstawie opinii, ten ma mieć jeden, poprawny, jednoznaczną i obiektywną odpowiedź, która została podana przez samego OP.
Jörg W Mittag
30
Nazywając go wielokrotnie nie mają wpływu, ponieważ nie może być inny kod, który zmienił „var” pomiędzy.
RemcoGerlich
7
Dlaczego zadawano to pytanie, skoro OP znał odpowiedź w chwili zadawania pytania ? Czy istnieje jakiś powód inny niż rep / punkty / budowanie karmy?
dotancohen
13
@dotancohen Pytanie / odpowiedź w stylu odpowiedzi jest jedną z kluczowych koncepcji StackExchange.
glglgl
17
@glglgl: Zgadzam się z pytaniami merytorycznymi. Jakie zalety ma to pytanie? Jestem poważnie zaniepokojony, że zaczniemy dostawać każde OP CS 101 od razu zadane i natychmiast udzielone przez OP, każdy pojedynczy termin CS zadany i natychmiast zdefiniowany przez OP, a także wszystkie podstawowe zalety i wady algorytmu, które zostaną zakwestionowane, a następnie natychmiast odpowiedziane przez OP ( niekoniecznie ten PO). Czy to jest strona, którą chcemy, aby była softwareengineering.SE?
dotancohen

Odpowiedzi:

244

Ten typ funkcji / operacji nosi nazwę Idempotent

Idempotence (UK: / ˌɪdɛmˈpoʊtəns /, [1] US: / ˌaɪdəm - /) [2] jest własnością niektórych operacji w matematyce i informatyce, dzięki którym można je stosować wiele razy bez zmiany wyniku poza początkową aplikacją.

W matematyce oznacza to, że jeśli f jest idempotentny, f ( f (x)) = f (x), co jest równoznaczne z wypowiedzeniem ff = f .

W informatyce oznacza to, że jeśli f(x);jest idempotentny, f(x);jest taki sam jak f(x); f(x);.

Uwaga: znaczenia te wydają się inne, ale w denotacyjnej semantyce stanu słowo „idempotent” ma tak samo dokładne znaczenie zarówno w matematyce, jak i informatyce.

Rufus
źródło
Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .
wałek klonowy
51

Dokładny termin na to (jak wspomina Woofas ) to idempotencja. Chciałem dodać, że chociaż można nazwać tę func1metodę idempotent, nie można nazwać jej czystą funkcją. Właściwości czystej funkcji są dwa: musi być idempotentna i nie może mieć skutków ubocznych, to znaczy nie może powodować mutacji lokalnych zmiennych statycznych, zmiennych nielokalnych, zmiennych argumentów referencyjnych ani strumieni we / wy.

Powiadam o tym, że funkcja idempotentna z efektami ubocznymi też nie jest dobra, ponieważ technicznie idempotentna odnosi się do wyniku zwrotnego funkcji, a nie do efektów ubocznych. Więc technicznie twoja func2metoda jest idempotentna, ponieważ dane wyjściowe nie zmieniają się zgodnie z danymi wejściowymi.

Najprawdopodobniej chcesz określić, że chcesz mieć czystą funkcję. Przykładem czystej funkcji może być:

int func1(int var)
{
    return var + 1;
}

Więcej lektur można znaleźć w artykule na Wikipedii „Czysta funkcja” .

Neil
źródło
37
Myślę, że twoja definicja idempotencji jest zbyt wąska, lub inaczej mówiąc, używasz matematycznej definicji idempotencji, a nie programowania. Na przykład metody PUTi DELETEHTTP są nazywane idempotentnymi właśnie dlatego , że wielokrotne wykonywanie ich skutków ubocznych daje taki sam efekt, jak wykonywanie ich tylko raz. Mówisz „idempotencja oznacza f∘f = f”, podczas gdy w programowaniu mamy na myśli „wykonywanie fma ten sam efekt, co wykonywanie f; f”. Zauważ, że możesz łatwo przekształcić drugie znaczenie w poprzednie, dodając parametr „world”.
Jörg W Mittag
23
@Neil „Idempotencja jest terminem ściśle matematycznym”. Nie, nie jest, jest również stosowany w systemach sieciowych i komunikacyjnych / systemach rozproszonych serwera klienta i jest opisany tak, jak opisuje to JörgWMittag. Jest to przydatna koncepcja, ponieważ pozwala na wielokrotne wysyłanie żądań do serwera / klienta z tą samą operacją / komunikatem bez zmiany tego, co zamierzał zrobić ten oryginalny komunikat. Jest to przydatne, gdy masz niewiarygodną komunikację i musisz ponowić polecenie, ponieważ wiadomość klienta została usunięta lub odpowiedź serwera.
opa
7
Powinieneś bardziej szczegółowo opisać różnicę między czystym a idempotentnym. Twój przykładowy func1 nie jest idempotentny, ponieważ func1(1) != func1(func1(1)).
Tezra
5
Czystość i idempotencja są różne. Czysta funkcja nie musi być idempotentna w sensie matematycznym (jest oczywiście idempotentna pod względem skutków ubocznych, ponieważ jej nie ma). Funkcja idempotentna (w sensie programowania) nie musi być czysta, jak w przykładzie podanym przez OP. Ponadto, jak wspomniano opa, idempotencja jest użyteczną właściwością o ściśle innym zastosowaniu niż czystość. Twoja definicja czystości jako „idempotentna i bez skutków ubocznych” jest błędna lub przynajmniej wprowadza w błąd, przegłosowuje.
Frax
5
W kontekście programowania nie ma „efektów ubocznych”, ale gdybyś rozszerzył definicję, aby to uwzględnić, to funkcja idempotentna i funkcja czysta oznaczałyby to samo. Nie, wcale by nie znaczyły tego samego. Idempotent, nie czysta: void f(int var) { someGlobalVariable = var; }. Czysta, nie idempotent: int func1(int var) { return var + 1; }.
JLRishe
6

Terminem jest idempotencja . Zauważ, że istnieje wyraźna różnica między funkcją Idempotent (wywoływaną rekurencyjnie na sobie; Drugi blok kodu i definicja matematyczna), a idempotencją funkcjonalną (wywoływaną wielokrotnie z tym samym wejściem sekwencyjnym; Pierwszy blok kodu i często termin oznaczony w Programowaniu).

Mówi się, że funkcja f ze skutkami ubocznymi jest idempotentna w składzie sekwencyjnym f; f, jeśli wywołany dwukrotnie z tą samą listą argumentów, drugie wywołanie nie wywołuje żadnych skutków ubocznych i zwraca taką samą wartość jak pierwsze wywołanie [potrzebne odwołanie] (zakładając, że między końcem pierwszego wywołania a początkiem nie wywołano żadnych innych procedur drugiego połączenia).

Rozważmy na przykład następujący kod Python:

x = 0

def setx(n):
    global x
    x = n

setx(5)
setx(5)

W tym przypadku setx jest idempotentny, ponieważ drugie wywołanie setx (z tym samym argumentem) nie zmienia widocznego stanu programu: x zostało już ustawione na 5 w pierwszym wywołaniu i ponownie ustawione na 5 w drugim wywołaniu, dzięki czemu ta sama wartość. Zauważ, że różni się to od idempotencji w składzie funkcji f ∘ f. Na przykład wartość bezwzględna jest idempotentna w składzie funkcji:

def abs(n):
    if n < 0:
        return -n
    else:
        return n

abs(-5) == abs(abs(-5)) == abs(5) == 5
Tezra
źródło
3

W fizyce słyszałem, że jest to projekcja :

projekcją jest liniową transformację P z przestrzeni wektorowej do siebie tak, że P 2 = P . Oznacza to, że ilekroć P jest zastosowane dwukrotnie do dowolnej wartości, daje taki sam wynik, jak gdyby zastosowano je raz (idempotent).

Graficznie ma to sens, jeśli spojrzysz na kreskówkę z projekcją wektorową :

wprowadź opis zdjęcia tutaj

Na zdjęciu, 1 jest projekcją do B , który jest podobny do pierwszego zastosowania swojej funkcji. Kolejne występy na 1 w celu b dać ten sam rezultat 1 . Innymi słowy, wielokrotne wywoływanie projekcji ma taki sam efekt jak jednorazowe wywołanie.

Uczciwe ostrzeżenie: nigdy nie słyszałem o tym używanym poza fizyką, więc jeśli nie masz tego typu w zespole, możesz wszystkich pomylić.

użytkownik1717828
źródło
2
To jest rzeczywiście ładny konkretny przykład tego, jak można wizualizować funkcję idempotentną (matematycznie, a zwłaszcza w polu geometrii wektorowej / algebry liniowej). Chociaż „idempotencja” funkcji oprogramowania jest bardzo bliską koncepcją, nie sądzę, aby programiści / informatycy często używali słowa „projekcja” w tym kontekście („funkcja projekcji” w inżynierii oprogramowania raczej odnosi się do funkcji, która przyjmuje obiekt i zwraca nowy obiekt uzyskany z niego lub na przykład właściwość tego obiektu)
Pac0
2
@ Pac0 Oh, ok. Pracuję na pograniczu nauki i programowania i nie zdawałem sobie sprawy, że słowo to było już przeciążone. Mogę wymyślić kilka wymyślonych przykładów w pracy, w których
użyłbym
3

Jest to algorytm deterministyczny, ponieważ przy tych samych danych wejściowych (w tym przypadku bez danych wejściowych) zawsze będzie generować takie same dane wyjściowe.

W informatyce algorytm deterministyczny jest algorytmem, który przy określonym wejściu zawsze będzie wytwarzał ten sam wynik, a maszyna leżąca u jego podstaw zawsze przechodzi przez tę samą sekwencję stanów. Algorytmy deterministyczne są zdecydowanie najlepiej zbadanym i znanym rodzajem algorytmu, a także jednym z najbardziej praktycznych, ponieważ można je efektywnie uruchamiać na prawdziwych maszynach.

Bazy danych SQL są zainteresowane funkcjami deterministycznymi .

Funkcja deterministyczna zawsze daje tę samą odpowiedź, gdy ma takie same dane wejściowe. Większość wbudowanych funkcji SQL w SQLite jest deterministycznych. Na przykład funkcja abs (X) zawsze zwraca tę samą odpowiedź, o ile jej wejście X jest takie samo.

Funkcja musi być deterministyczna, jeśli jest używana do obliczania indeksu.

Na przykład, w SQLite następujące funkcje nie deterministyczne nie może być stosowany w indeksie: random(), changes(), last_insert_rowid()i sqlite3_version().

Stephen Quan
źródło
6
Pytający func2jest deterministyczny (nie ma w nim żadnych efektów losowych), ale już zadeklarował, że narusza właściwość, której szuka.
Draco18s
To, że ten sam wynik powstaje w wyniku powtarzania, nie jest tym samym, co mówienie, że ten sam wynik powstaje przez zagnieżdżanie lub tworzenie łańcuchów. Funkcje deterministyczne są ważne dla buforowania wyników, bardziej niż dla indeksowania / mieszania.
mckenzm
3

W uzupełnieniu do innych odpowiedzi, jeśli nie ma konkretnego wejścia do functon który ma tę właściwość, że jest to punkt stały , niezmienny punkt lub fixpoint funkcji. Na przykład 1 do dowolnej potęgi jest równy 1, więc (1ⁿ) ⁿ = 1ⁿ = 1.

Szczególnym przypadkiem programu, który produkuje się jako wyjście, jest quine .

Davislor
źródło
Quines jest programowy, podobnie jak zestawy Cantora :-). I oczywiście, quinesy nie są idempotentne - albo zawodzą, gdy dane wyjściowe już istnieją, albo „blokują” poprzedni wynik i zapisują nowe, aczkolwiek identyczne dane wyjściowe.
Carl Witthoft