Что такое инвариант?
Слово, кажется, используется в ряде контекстов. Лучшее, что я могу понять, это то, что они имеют в виду переменную, которая не может измениться. Разве не для этого нужны константы / финалы (черт возьми, Java!)?
9 ответов
Инвариант более "концептуален", чем переменная. В общем, это свойство состояния программы, которое всегда верно. Говорят, что функция или метод, обеспечивающий выполнение инварианта, поддерживают инвариант.
Например, двоичное дерево поиска может иметь инвариант, что для каждого узла ключ левого дочернего узла меньше, чем собственный ключ узла. Правильно написанная функция вставки для этого дерева будет поддерживать этот инвариант.
Как вы можете сказать, это не та вещь, которую вы можете хранить в переменной: это скорее утверждение о программе. Выясняя, какой тип инвариантов должна поддерживать ваша программа, а затем просматривая код, чтобы убедиться, что он фактически поддерживает эти инварианты, вы можете избежать логических ошибок в вашем коде.
Это условие, которое, как вы знаете, всегда является истинным в определенном месте вашей логики и может быть проверено при отладке, чтобы выяснить, что пошло не так.
Магия википедии: инвариант (информатика)
В компьютерных науках предикат, который, если он истинен, будет оставаться верным в течение определенной последовательности операций, называется () инвариантным к этой последовательности.
Этот ответ предназначен для моего 5-летнего ребенка. Не думайте об инварианте как о постоянном или фиксированном числовом значении. Но может быть. Однако это еще не все.
Скорее, инвариант - это что-то вроде фиксированного отношения между различными объектами. Например, ваш возраст всегда будет меньше, чем у ваших биологических родителей. И ваш возраст, и возраст ваших родителей меняются с течением времени, но отношения, о которых я упоминал выше, являются неизменными.
Инвариант также может быть числовой константой. Например, значениеpi- неизменное соотношение длины окружности к ее диаметру. Независимо от того, насколько большой или маленький круг, это соотношение всегда будетpi.
Я обычно рассматриваю их больше с точки зрения алгоритмов или структур.
Например, вы можете иметь инвариант цикла, который может быть утвержден - всегда true в начале или конце каждой итерации. То есть, если ваш цикл должен был обрабатывать коллекцию объектов из одного стека в другой, вы могли бы сказать, что |stack1|+|stack2|=c, в верхней или нижней части цикла.
Если проверка инварианта не удалась, это означает, что что-то пошло не так. В этом примере это может означать, что вы забыли поместить обработанный элемент в окончательный стек и т. Д.
Как говорится в этой строке:
В компьютерных науках предикат, который, если он истинен, будет оставаться верным в течение определенной последовательности операций, называется () инвариантным к этой последовательности.
Чтобы лучше понять эту надежду, этот пример в C++ помогает.
Рассмотрим сценарий, в котором вы должны получить некоторые значения и получить их общее количество в переменной с именем count и добавить их в переменную с именем sum
Инвариант (опять же это больше похоже на концепцию):
// invariant:
// we have read count grades so far, and
// sum is the sum of the first count grades
Код для вышеупомянутого будет что-то вроде этого,
int count=0;
double sum=0,x=0;
while (cin >> x) {
++count;
sum+=x;
}
Что делает приведенный выше код?
1) Читает ввод от cin и кладет их в x
2) После одного успешного чтения увеличьте count а также sum = sum + x
3) Повторите 1-2, пока чтение не остановится (т.е. Ctrl+D)
Инвариант петли:
Инвариант должен быть Истинным ВСЕГДА. Итак, изначально вы начинаете свой код только с этого
while(cin>>x){
}
Этот цикл читает данные из стандартного ввода и сохраняет их в x. Ну и хорошо. Но инвариант становится ложным, потому что первая часть нашего инварианта не была соблюдена (или оставалась верной).
// we have read count grades so far, and
Как сохранить инвариант истинным?
Просто! счетчик приращений.
Так ++count; будет хорошо! Теперь наш код становится примерно таким,
while(cin>>x){
++count;
}
Но
Даже сейчас наш инвариант (концепция, которая должна быть ИСТИНА) является Ложным, потому что теперь мы не удовлетворили вторую часть нашего инварианта.
// sum is the sum of the first count grades
Так что же теперь делать?
добавлять x в sum и сохранить его в sum (sum+=x) и в следующий раз cin>>x будет читать новое значение в х.
Теперь наш код становится примерно таким,
while(cin>>x){
++count;
sum+=x;
}
Давай проверим
Соответствует ли код нашему инварианту
// invariant:
// we have read count grades so far, and
// sum is the sum of the first count grades
код:
while(cin>>x){
++count;
sum+=x;
}
Ах!. Теперь инвариант цикла всегда True и код работает нормально.
Приведенный выше пример был взят и модифицирован из книги " Ускоренный C++ " Эндрю-Кенинга и Барбары-Е
Class Invariant - это условие, которое всегда должно выполняться до и после вызова соответствующей функции
Например, сбалансированное дерево имеет
Invariant который называется
isBalanced. Когда вы изменяете свое дерево с помощью некоторых методов (например, addNode, removeNode...) -
isBalanced должно быть всегда истинным до и после изменения дерева
Все ответы здесь отличные, но я чувствовал, что могу пролить больше света на этот вопрос:
Инвариант с языковой точки зрения означает то, что никогда не меняется. Хотя эта концепция на самом деле исходит из математики, это один из популярных методов доказательства в сочетании с индукцией.
Вот как проходит доказательство: если вы можете найти инвариант, который находится в начальном состоянии, и что этот инвариант сохраняется независимо от любого [законного] преобразования, примененного к состоянию, тогда вы можете доказать, что если определенное состояние не имеет этого инвариантно, то это никогда не может произойти, независимо от того, какая последовательность преобразований применяется к начальному состоянию.
Итак, предыдущий способ мышления (снова в сочетании с индукцией) позволяет предиктировать логику компьютерного программного обеспечения. Это особенно важно, когда выполнение происходит в циклах, в которых инвариант может использоваться, чтобы доказать, что определенный цикл даст определенный результат или что он никогда не изменит состояние программы определенным образом.
Когда инвариант используется для предиката логики цикла, он называется инвариантом цикла. Его можно использовать вне циклов, но для циклов это действительно важно, потому что у вас часто есть много возможностей или бесконечное количество возможностей.
Обратите внимание, что я использую слово "предикат" для логики компьютерной программы, а не для доказательства. И это потому, что, хотя в математике инвариант может использоваться в качестве доказательства, он никогда не может доказать, что компьютерное программное обеспечение при выполнении даст то, что ожидается, из-за того, что программное обеспечение выполняется поверх многих абстракций, что никогда не может быть доказано. что они дадут то, что ожидается (подумайте, например, об аппаратной абстракции).
Наконец, хотя теоретическое и строгое предсказание логики программного обеспечения важно только для критически важных приложений, таких как медицинские и военные. Инвариант все еще можно использовать для помощи обычному программисту при отладке. Его можно использовать, чтобы узнать, где в определенном месте. Программа потерпела неудачу, потому что она не смогла сохранить определенный инвариант - многие из нас все равно используют ее, не задумываясь об этом.
Обычно это количество, которое не изменяется при определенных математических операциях. Примером является скаляр, который не изменяется при поворотах. Например, при магнитно-резонансной томографии полезно характеризовать свойство ткани с помощью инварианта вращения, потому что тогда его оценка в идеале не зависит от ориентации тела в сканере.
Исходя из того, что это такое, инварианты весьма полезны при написании чистого кода, поскольку концептуальное знание того, какие инварианты должны присутствовать в вашем коде, позволяет вам легко решить, как организовать ваш код для достижения этих целей. Как упоминалось ранее, они также полезны при отладке, так как проверка того, поддерживается ли инвариант, часто является хорошим способом выяснить, действительно ли любая манипуляция, которую вы пытаетесь выполнить, выполняет то, что вы хотите.
В книге " Java Concurrency in Practice" есть отличный пример инварианта и его значение.
Хотя этот пример ориентирован на Java, он описывает некоторый код, который отвечает за вычисление множителей предоставленного целого числа. В примере кода делается попытка кэширования последнего предоставленного числа и факторов, которые были рассчитаны для повышения производительности. В этом сценарии есть инвариант, который не был учтен в примере кода, что сделало код восприимчивым к условиям гонки в параллельном сценарии.
Инвариант ADT определяет отношения между полями данных (переменными экземпляра), которые всегда должны быть истинными до и после выполнения любого метода экземпляра.