Что такое термин для функции, которая при повторном вызове имеет тот же эффект, что и один раз?

96

(Предполагая однопоточную среду)

Функция, которая удовлетворяет этому критерию:

bool MyClass::is_initialized = false;

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

По сути, я могу вызывать эту функцию несколько раз и не беспокоиться о ее инициализации MyClassнесколько раз

Функция, которая не соответствует этому критерию, может быть:

Foo* MyClass::ptr = NULL;

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

initialize()Многократный вызов вызовет утечку памяти

мотивация

Было бы неплохо иметь одно краткое слово, чтобы описать это поведение, чтобы можно было должным образом прокомментировать функции, которые должны соответствовать этому критерию (особенно полезно при описании функций интерфейса, которые, как ожидается, будут переопределены)

Руфус
источник
67
Для близкого (ых) избирателя (ей): хотя это правда, что 99,999% (приблизительная оценка) всех вопросов «имя-это-вещь» не по теме, поскольку у них нет единого, правильного, однозначного, объективного ответа и именование является чисто субъективным и на основе мнений, это один делает есть один, правильный, однозначный, объективный ответ, который был дан самим ОП.
Йорг Миттаг
30
Вызов его несколько раз делает иметь эффект, так как там может быть другой код , который изменил «вар» между ними.
RemcoGerlich
7
Почему этот вопрос был задан, если ОП знал ответ во время запроса ? Есть ли какая-либо другая причина, кроме построения репутации / очков / кармы?
Dotancohen
13
@dotancohen Q / Стиль автоответчика - одна из ключевых концепций StackExchange.
glglgl
17
@glglgl: Я согласен, для вопросов с достоинством. В чем заслуга этого вопроса? Я серьезно обеспокоен тем, что мы начнем получать ответы на каждый вопрос CS 101 и немедленно отвечать на него OP, на каждый отдельный термин CS, который задается и немедленно определяется OP, а также на все плюсы и минусы каждого базового алгоритма, а затем немедленно отвечать OP ( не обязательно это ОП). Это сайт, которым мы хотим, чтобы softwareengineering.SE был?
Dotancohen

Ответы:

244

Этот тип функции / операции называется идемпотентом

Идемпотентность (Великобритания: / ˌɪdɛmˈpoʊtəns /, [1] США: / ˌaɪdəm - /) [2] является свойством некоторых операций в математике и информатике, в соответствии с которыми они могут применяться несколько раз без изменения результата за пределы первоначального применения.

В математике это означает, что если f идемпотент, f ( f (x)) = f (x), что то же самое, что сказать ff = f .

В информатике это означает, что если f(x);идемпотент, f(x);то же самое, что и f(x); f(x);.

Примечание: эти значения кажутся разными, но в денотационной семантике государства слово «идемпотент» фактически имеет одинаковое точное значение как в математике, так и в информатике.

Руфус
источник
Комментарии не для расширенного обсуждения; этот разговор был перенесен в чат .
maple_shaft
51

Точный термин для этого (как упоминает Вуфас ) - идемпотентность. Я хотел бы добавить, что хотя вы можете называть свой func1метод идемпотентным, вы не можете называть его чистой функцией. Свойства чистой функции два: она должна быть идемпотентной и не должна иметь побочных эффектов, то есть не иметь мутаций локальных статических переменных, нелокальных переменных, изменяемых ссылочных аргументов или потоков ввода-вывода.

Причина, по которой я упоминаю это, состоит в том, что идемпотентная функция с побочными эффектами также не годится, поскольку технически идемпотентный относится к возвратному результату функции, а не к побочным эффектам. Так что технически ваш func2метод идемпотентен, поскольку выход не меняется в зависимости от ввода.

Скорее всего, вы хотите указать, что вы хотите чистую функцию. Пример чистой функции может быть следующим:

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

Больше чтения можно найти в статье в Википедии "Чистая функция" .

Нил
источник
37
Я думаю, что ваше определение идемпотентности слишком узкое, или, другими словами, вы используете математическое определение идемпотентности, а не программирование. Например, методы HTTP PUTи DELETEHTTP называются идемпотентными именно потому, что выполнение их побочных эффектов несколько раз имеет тот же эффект, что и выполнение их только один раз. Вы говорите «идемпотентность означает f∘f = f», тогда как в программировании мы имеем в виду «выполнение fимеет тот же эффект, что и выполнение f; f». Обратите внимание, что вы можете легко преобразовать второе значение в первое, добавив параметр "world".
Йорг Миттаг
23
@Neil "Идемпотентность - строго математический термин." Нет, это не так, он также используется в сетях и клиент-серверных коммуникациях / распределенных системах и описывается так, как его описывает JörgWMittag. Это полезная концепция, поскольку она допускает несколько запросов к серверу / клиенту с одной и той же операцией / сообщением без изменения того, что намеревалось сделать исходное сообщение. Это полезно, когда у вас ненадежная связь, и вам нужно повторить команду, потому что либо сообщение клиента было отброшено, либо ответ сервера был.
оп
7
Вы должны более подробно рассказать о разнице между чистым и идемпотентным. Ваш пример func1 не идемпотент, потому что func1(1) != func1(func1(1)).
Тезра
5
Чистота и идемпотентность разные. Чистая функция не должна быть идемпотентной в математическом смысле (она явно идемпотентна с точки зрения побочных эффектов, так как у нее ее нет). Идемпотентная (в смысле программирования) функция не должна быть чистой, как в примере, приведенном OP. Кроме того, как уже упоминалось, идемпотентность является полезным свойством со строго другим использованием, чем чистота. Ваше определение чистоты как «идемпотентное и без побочных эффектов» неверно или, по крайней мере, вводит в заблуждение, понижая голос.
Фракс
5
В контексте программирования «побочных эффектов» нет, но если бы вы расширили определение, включив его, то идемпотентная функция и чистая функция означали бы одно и то же. Нет, они бы не имели в виду одно и то же. Идемпотент, не чистый void f(int var) { someGlobalVariable = var; }. Чисто, не идемпотентно int func1(int var) { return var + 1; }.
JLRishe
6

Термин идемпотентность . Обратите внимание, что между идемпотентной функцией (рекурсивно вызываемой сам по себе; второй блок кода и математическим определением) существует четкое различие и идемпотентность по функциональности (вызывается повторно с одним и тем же вводом последовательно; первый блок кода и часто используется в программировании).

Функция f с побочными эффектами называется идемпотентной при последовательной композиции f; f если при вызове дважды с одним и тем же списком аргументов второй вызов не имеет побочных эффектов и возвращает то же значение, что и первый вызов [необходимо цитирование] (при условии, что никакие другие процедуры не были вызваны между концом первого вызова и началом второго звонка).

Например, рассмотрим следующий код Python:

x = 0

def setx(n):
    global x
    x = n

setx(5)
setx(5)

Здесь setx является идемпотентом, потому что второй вызов setx (с тем же аргументом) не изменяет видимое состояние программы: x был уже установлен в 5 в первом вызове, и снова установлен в 5 во втором вызове, таким образом сохраняя такое же значение. Отметим, что это отлично от идемпотентности при композиции функций f ∘ f. Например, абсолютное значение идемпотентно при составлении функции:

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

abs(-5) == abs(abs(-5)) == abs(5) == 5
Tezra
источник
3

В физике я слышал, что это называется проекцией :

проекция является линейным преобразованием Р из векторного пространства в себя, что Р 2 = Р . То есть всякий раз, когда P применяется дважды к любому значению, он дает тот же результат, как если бы он был применен один раз (идемпотент).

Графически это имеет смысл, если вы посмотрите на карикатуру векторной проекции :

введите описание изображения здесь

На рисунке a 1 - это проекция a на b , которая похожа на первое применение вашей функции. Последующие проекции a 1 на b дают тот же результат a 1 . Другими словами, когда вы вызываете проекцию несколько раз, это имеет тот же эффект, что и вызов ее один раз.

Справедливое предупреждение: я никогда не слышал, чтобы это использовалось вне физики, поэтому, если у вас нет таких типов в вашей команде, вы можете запутать всех.

user1717828
источник
2
Это действительно хороший конкретный пример того, как идемпотентная функция может быть визуализирована (математически, особенно в области векторной геометрии / линейной алгебры). В то время как «идемпотентность» функции программного обеспечения является действительно близким понятием, я не думаю, что разработчики / программист часто используют слово «проекция» в этом контексте («функция проекции» в разработке программного обеспечения скорее будет относиться к функции, которая принимает объект и возвращает новый объект, полученный из него, или свойство этого объекта, например)
Pac0
2
@ Pac0 О, хорошо. Я работаю на границе между наукой и программированием и не понимаю, что слово уже перегружено. Я могу вспомнить несколько надуманных примеров на работе, где я бы использовал эту терминологию, но я
общеизвестно
3

Это детерминированный алгоритм, потому что при одинаковом входе (в данном случае без ввода) он всегда будет давать одинаковый выход.

В компьютерных науках детерминированный алгоритм - это алгоритм, который при заданном входном сигнале всегда будет давать один и тот же выходной сигнал, а базовый компьютер всегда будет проходить через одну и ту же последовательность состояний. Детерминированные алгоритмы на сегодняшний день являются наиболее изученным и знакомым алгоритмом, а также одним из наиболее практичных, поскольку они могут эффективно выполняться на реальных машинах.

Базы данных SQL интересуются детерминированными функциями .

Детерминированная функция всегда дает один и тот же ответ, когда она имеет одинаковые входные данные. Большинство встроенных функций SQL в SQLite являются детерминированными. Например, функция abs (X) всегда возвращает один и тот же ответ, если его входные данные X одинаковы.

Функция должна быть детерминированной, если она используется при расчете индекса.

Например, в SQLite, следующие недетерминированные функции не могут быть использованы в качестве индекса: random(), changes(), last_insert_rowid()и sqlite3_version().

Стивен Куан
источник
6
Аскер func2является детерминированным (без случайных эффектов), но уже объявлен нарушающим свойство, которое он ищет.
Draco18s
То, что один и тот же результат получается при повторении, не означает, что тот же результат получается при вложении или цепочке. Детерминированные функции важны для кэширования результатов, в большей степени, чем для индексации / хеширования.
Маккензм
3

В дополнение к другим ответам, если есть определенный вход для функции, обладающей этим свойством, это фиксированная точка , инвариантная точка или точка фиксации функции. Например, 1 для любой степени равен 1, поэтому (1ⁿ) ⁿ = 1ⁿ = 1.

Особый случай программы, которая производит себя как выходные данные, - это квин .

Davislor
источник
Квины относятся к программному обеспечению, а наборы Кантора - к математике :-). И, конечно, квины не являются идемпотентными - они либо терпят неудачу, когда выходные данные уже существуют, либо они «забивают» предыдущий результат и записывают новый, хотя и идентичный, выход.
Карл Виттофт