Что такое инвариант?

Question

Слово, похоже, используется в ряде контекстов. Лучшее, что я могу понять, это то, что они означают переменную, которая не может измениться. Разве это не то, для чего нужны константы/финалы (чертовски вы Java!)?

Answer 1

Инвариант более «концептуальен», чем переменная. В общем, это свойство состояния программы, которое всегда верно. Говорят, что функция или метод, гарантирующий сохранение инварианта, сохраняет инвариант.

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

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

Answer 2

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

Answer 3

Обычно я рассматриваю их больше с точки зрения алгоритмов или структур.

Например, у вас может быть инвариант цикла, который можно было бы утверждать - всегда true в начале или в конце каждой итерации. То есть, если ваш цикл должен обрабатывать коллекцию объектов из одного стека в другой, вы можете сказать, что | stack1 | + | stack2 | = c, в верхней или нижней части цикла.

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

Answer 4

Магия википедии: Invariant (computer science)

В информатике, предикат, который, если это правда, будет оставаться истинным во всей определенной последовательности операций , является , называемой (an), инвариантной к этой последовательности .

Answer 5

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

Answer 6

Что-то, что не меняется в пределах блока кода

Answer 7

АДТ инвариантные specifes отношения среди полей данных (переменных экземпляра) , которые всегда должны быть истинными до и после выполнения любого метода экземпляра.

Answer 8

Как гласит эта строка:

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

Чтобы лучше понять эту надежду, этот пример на 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)

Loop инвариант:

инвариант должен быть правдой ВСЕГДА. Поэтому изначально вы начинаете свой код только с этого

while(cin>>x){ 
    } 

Эта петля считывает данные со стандартного ввода и сохраняет по x. Ну и хорошо. Но инвариант становится ложным, потому что первая часть нашего инварианта не соблюдалась (или сохранялась).

// we have read count grades so far, and 

Как сохранить инвариант верно?

Простой! счетчик инкремента.

So ++count; будет делать хорошо !. Теперь наш код становится чем-то вроде этого,

while(cin>>x){ 
++count; 
} 

Но

Даже теперь наш инвариант (понятие, которое должно быть TRUE) является Ложное, потому что теперь мы не удовлетворили вторую часть нашего инвариант.

// 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 всегда и код работает нормально.

Приведенный выше пример был взят и редактировался книга Accelerated C++ Эндрю-koening и Барбара-E