что такое детерминированная функция

Чистые и детерминированные функции

Перевод статьи Джастина Этеридж (Justin Etheredge), в которой автор объясняет тонкую разницу между детерминированными и чистыми функциями.

Вчера я читал блог Мэтта Подвизоки (Matt Podwysocki) (этот блог, кстати, потрясающий, идите и подпишитесь), и у него есть пост «Recursing into Recursion – Memoization». Отличный пост, если вы хотите познакомиться с мемоизацией. У меня уже был пост об обобщенной функции мемоизации некоторое время назад, поэтому мы будем говорить не о мемоизации. То, что возбудило во мне интерес, было в конце статьи Мэтта:

Не забывайте, что корректная мемоизация требует, чтобы функция, которую вы пишете, была чистой. Это означает, что для одних и тех же входных данных будут вычисляться и возвращаться одни и те же результаты.

Моя первая мысль была «Эй, Мэтт, чистота подразумевает, что функция не имеет побочных эффектов, а детерминированность означает, что функция всегда возвращает одни и те же результаты для данных наборов параметров». Затем, как у любого хорошего программиста, моей второй мыслью было «На самом деле, возможно, я не прав». Поэтому я пошел и изучил этот вопрос, и не удивительно, что я ошибался.

Вот описание чистой функции из википедии:

А вот определение детерминированного алгоритма Национальным Институтом стандартов и технологий (США):

Алгоритм, поведение которого можно полностью предсказать по входным данным.

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

Детерминированная и чистая:

Детерминированная, но не чистая:

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

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

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

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

Действительно здорово узнать что-то новое, но еще лучше узнать о том, что ваши знания были неверны.

Источник

Детерминированные и недетерминированные функции

Детерминированные функции каждый раз возвращают один и тот же результат, если предоставлять им один и тот же набор входных значений и использовать одно и то же состояние базы данных. Недетерминированные функции могут возвращать каждый раз разные результаты, даже если предоставлять им один и тот же набор входных значений и использовать одно и то же состояние базы данных. Например, функция AVG всегда возвращает один результат при указанных выше условиях, а функция GETDATE, возвращающая текущие дату и время, всегда возвращает разный результат.

Определяемые пользователями функции имеют несколько свойств, определяющих способность ядра Компонент SQL Server Database Engine индексировать результаты функции как с помощью индексов вычисляемых столбцов, вызывающих функцию, так и с помощью индексированных представлений, которые на нее ссылаются. Детерминизм функции — одно из таких свойств. Например, в представлении нельзя создать кластеризованный индекс, если оно ссылается на какие-либо недетерминированные функции. Дополнительные сведения о свойствах функций, включая детерминизм, см. в разделе Определяемые пользователем функции.

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

Детерминизм встроенных функций

На детерминизм встроенных функций повлиять нельзя. Каждая из них детерминирована или недетерминирована в зависимости от реализации в SQL Server. Например, если вы укажете в запросе предложение ORDER BY, детерминизм функции, используемой в этом запросе, не изменится.

Все встроенные строковые функции являются детерминированными, кроме FORMAT. Список этих функций см. в разделе Строковые функции (Transact-SQL).

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

Источник

Чистые функции — Введение в программирование

Транскрипт урока

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

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

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

Отвлеклись, давайте — к делу. В программировании детерминированная функция, это функция, которая всегда производит тот же результат при одинаковых вводных данных:

Вам наверное интересно, как ещё может вести себя функция. Недетерминированная функция непредсказуема, её результат зависит от чего-то ещё.

Например, представим функцию, которая принимает почтовый индекс и возвращает погоду на данный момент. Она, по всей видимости, подключается к метеорологическому серверу через интернет и отдаёт разные результаты в разное время, потому что погода меняется.

Ещё более простой пример — генератор случайных чисел. Обычно в любом языке программирования есть какой-нибудь встроенный способ генерации случайных чисел. В JavaScript он такой:

Как видите, каждый раз, когда вы вызываете его с одинаковыми аргументами (в данном случае — никаких аргументов вообще), результат всегда новый. Эта функция недетерминированная, но в этом вся её суть. Генератор случайных чисел должен давать вам разные числа по определению, даже если вызовы функции выглядят одинаково.

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

Детериминированные функции предсказуемы: они менее хрупкие, о них проще рассуждать и представлять их. Использовать их тоже проще, собирая сложные структуры и программы.

Так как детерминированные функции всегда производят тот же результат из тех же данных, их можно оптимизировать: они могут запоминать результат для конкретных данных и просто возвращать запомненное значение, когда в них поступят те же данные, вместо выполнения заново целого вычисления. Если функция детерминированная, всё гарантировано будет в порядке.

Мы должны затронуть ещё одну тему, перед тем как рассматривать самый красивый и замечательный тип функций. Существует понятие — побочные эффекты — то, как функция изменяет внешний мир.

А ваш хороший друг — функция console.log — имеет: она выводит что-то на экран. Эта штука на экране — определённо что-то за рамками функции, это компьютер, мир в котором живёт функция.

Или рассмотрим следующий код:

Опять же, это не плохо, поскольку программа без побочных эффектов не может быть полезной. Мы хотим, чтобы наши программы что-то делали, как-то меняли мир — показывали что-то на экране, шумели, отсылали электронные письма и так далее. Но минимизировать побочные эффекты в ваших функциях и программах возможно, и на самом деле — это хорошая идея.

Чем меньше побочных эффектов имеет функция, тем лучше.

Когда функция детерминированная и не имеет побочных эффектов, мы называем её «чистой» функцией. Настолько она предсказуема, чиста и прозрачна. В этом смысле чистые функции близки к математическим. x в квадрате с одним и тем же значением x, всегда будет давать одинаковый результат, а вычисление квадрата x не будет менять сам x.

Всё, что касается чистых функций кажется «проще»: они просты для чтения, для отладки и поиска ошибок, для тестирования. Чистые функции в системе не зависят ни от чего по-определению, поэтому порядок, в котором они вызываются не имеет значения. Это значит, что их легко запустить, например, параллельно — одновременно — на разных процессорах или даже разных компьютерах.

Чистые функции живут вне времени. Само понятие времени, действий, протекающих в какой-то последовательности, не касается чистых функций. Время их не беспокоит. Когда вы смотрите на чистые функции, читаете код, делаете отладку, тестируете или просто используете их — вам не нужно думать о времени, о том, что случилось до и случится после. Это дает некоторую свободу, и все «простые» штуки, касающиеся чистых функций — последствия этого факта.

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

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

Если вы смотрели видео, но не выполняли упражнения и тесты — то обязательно сделайте это. Курс рассчитан именно на это, а видео сами по себе — это только часть процесса. Есть большая разница между «кажется, понял» и «умею».

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

Я надеюсь, что программирование станет важной и интересной частью вашей жизни.

Выводы

Детерминированная функция всегда возвращает одинаковое значение при определённом вводе (аргументы).

surfaceAreaCalculator это детерминированная функция.

Недетерминированная функция не всегда будет возвращать одинаковое значение при определённом вводе.

Функция, которая возвращает погоду на данный момент для какой-нибудь координаты — недетерминированная: погода всегда меняется, поэтому мы не можем быть уверены, какой ответ выдаст функция.

Другой пример — генератор случайных чисел:

Побочные эффекты: то, как функция меняет внешний мир.

surfaceAreaCalculator не имеет никаких побочных эффектов. Она ничего не меняет за пределами своих границ.

Функция console.log имеет побочный эффект: она что-то выводит на экран.

То, что функции возвращают, не имеет ничего общего с тем, как они влияют на внешний мир.

Чем меньше побочных эффектов имеет функция, тем лучше.

Когда функция детерминированная и не имеет побочных эффектов, мы называем её «чистой» функцией. Чистые функции:

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

Дополнительные материалы

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты.

Источник

Взаимоотношения чистых и детерминированных функций

Для начала, вспомним каждое из определений. Чистая функция – это функция, которая не имеет побочных эффектов и для фиксированного набора аргументов возвращает один и тот же результат. Давайте посмотрим на пару примеров.

Чистые функции

Вот функция _sum:

Результат её работы не зависит ни от чего, кроме аргументов, и не делает ничего с окружающей средой.

А вот _weighed_sum:

Эта функция «грязная»: результат её работы кроме «a и b» зависит ещё от глобальной переменной WEIGHT. Получается, если мы зафиксируем значения аргументов функции, мы не сможем гарантировать, что результат всегда будет один и тот же.

Теперь посмотрим на _save_sum_to_database:

Эта функция тоже «грязная»: она использует базу данных и результат её работы зависит от БД. Функция будет вести себя по-разному, если БД доступна и недоступна.

С чистыми функциями разобрались! Они используют только свои аргументы, не ходят во «внешний мир» и гарантируют один и тот же результат при тех же аргументах.

Теперь вспомним, что такое детерминированные функции

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

Простой пример недетерминированной функции – randint. Входные аргументы мы знаем, а результат – нет.

Если внимательно посмотреть на определения чистых и детерминированных функций, то станет понятно, что чистые функции – подмножество детерминированных.

Это важный вывод: зная это, становится проще понимать свойства разных кусков кода и делать их чище.

Есть вопрос? Напишите в комментариях!

Источник

Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004. Электронный ресурс, страница 10

Описание файла

Онлайн просмотр документа «Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004. Электронный ресурс»

Текст 10 страницы из документа «Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004. Электронный ресурс»

удовлетворяющих системе уравнений (суммы по модулю 2):

Теорема 6. Код Хэмминга порядка n содержит 2 n – k наборов, где и исправляет одну ошибку.

Доказательство. Рассмотрим систему уравнений из определения кода Хэмминга

Таким образом, по выходному слову можно определить номер искаженного разряда и восстановить исходное слово.

Замечание. Обычно разряды с номерами 1, 2, 4, 8, …, 2 k –1 называют проверочными (или контрольными), остальные — информационными.

Доказательство. Имеем (теорема 5). Правое неравенство в теореме 7 следует из того, что S₁ (n) = n + 1. Заметим предварительно, что аналогично нельзя получить и левое неравенство, так как

Глава V. Основы теории конечных
автоматов

§35. Понятие ограниченно детерминированных (автоматных) функций, их представление диаграммой Мура.
Единичная задержка

Пусть даны A = <a₁, a₂, …, a_r> — входной алфавит и B = <b₁, b₂, …, b_m> — выходной алфавит. Определим множества A ∞ и B ∞ как множества всевозможных последовательностей в алфавитах A и B соответственно.

Определение 3. Детерминированная функция  : A ∞ B ∞ называется ограниченно детерминированной, если у неё имеется лишь конечное число различных остаточных функций.

Определение 4. Автоматом (инициальным) называется любая шестёрка (A, B, Q, G, F, q₀), где A, B, Q — конечные алфавиты (A называют входным алфавитом, B — выходным алфавитом, Q — множеством состояний), G: A  Q  Q, F: A  Q  B, q₀  Q — начальное состояние.

Входом автомата служит последовательность a(1)a(2)a(3)…a(t)… A * (конечная или бесконечная), выходом автомата служит последовательность z(t), при этом автомат задаётся системой канонических уравнений

Определение 5. Отображение : A ∞  B ∞ называется автоматной функцией, если существует автомат, который реализует это отображение.

Утверждение. Функция является автоматной тогда и только тогда, когда она является ограниченно детерминированной.

Пример. Пусть A = B = Q = <0, 1>и система канонических уравнений выглядит следующим образом:

Такой автомат, очевидно, осуществляет отображение a(1)a(2)…0a(1)a(2)… и называется единичной задержкой.

Определение 6. Диаграммой Мура для автомата называется ориентированный граф с множеством вершин Q, у которого каждой паре (a, q) сопоставляется дуга, идущая из вершины q в вершину, соответствующую G (a, q). Этой дуге приписывается пометка (a, F (a, q)). Особым образом помечена вершина, соответствующая начальному состоянию. Диаграмма Мура однозначно задаёт автомат.

§36. Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими
отображений

Определение. Схемой из функциональных элементов и элемента задержки называется схема из функциональных элементов в функциональном базисе, к которому добавлен элемент, реализующий функцию единичной задержки. В схеме из функциональных элементов и элементов задержки допускаются ориентированные циклы, но любой ориентированный цикл должен проходить хотя бы через одну задержку.

Пусть A = B = <0, 1>, E₂ n — множество всех булевых векторов длины n.

Теорема 1. Схема из функциональных элементов и задержки осуществляет автоматное отображение.

Доказательство. 1) Пусть в схеме имеется r элементов задержки. Пусть i-я задержка R_i приписана вершине v_i, в которую идёт дуга из вершины w_i. Для всех i = 1, …, r удалим из СФЭЗ дуги (w_i, v_i). По определению СФЭЗ в полученном после этого графе не будет ориентированных циклов и он, тем самым будет представлять собой СФЭ. Входами этой СФЭ будут все входы исходной схемы, а также все вершины v_i, i = 1, …, r (заметим, что все они различны и отличны от входов исходной схемы). Выходами полученной СФЭ объявим все выходы исходной схемы и вершины w_i, i = 1, …, r. Пусть в исходной схеме выходам приписаны переменные z₁, …, z_m, входам — переменные x₁, …, x_n. Вершинам v_i припишем переменные q‘₁, …, q‘_r, а вершинам w_i — переменные q₁, …, q_r. В соответствии с определением функционирования СФЭ, для некоторых функций алгебры логики f_i, g_j справедливо:

Естественно считать, что равенства (1) выполняются в каждый момент времени t = 1, 2, 3,…, то есть

Так как, в соответствии с каноническими уравнениями элемента единичной задержки его выход в момент t совпадает с его входом в момент t – 1, то естественно считать, что в исходной схеме q‘_i (t) = q_i (t – 1) при
t = 1, 2, … для всех i = 1, …, r, где q_i (0) = 0. Тогда равенства (2) принимают вид (где i = 1, …, m и j = 1, …, r):

Полученные равенства определяют функционирование СФЭЗ и называются её каноническими уравнениями.

§37. Моделирование автоматной функции схемой из
функциональных элементов и элементов задержки

Теорема 2. Для любой автоматной функции существует моделирующая её СФЭЗ в базисе из функциональных элементов дизъюнкции, конъюнкции, отрицания и элемента задержки.

Тогда можно построить схему из функциональных элементов в базисе <,&, > с n + r входами и m + r выходами, реализующую семейство функций

Источник