什么是不变量?

这个词似乎在许多上下文中使用。我能想到的最好的解释就是它们指的是一个不能改变的变量。这不就是常量/期末考试吗(该死的 Java!)为什么?

45664 次浏览

这是一个条件,您知道在逻辑中的某个特定位置始终为真,并且可以在调试时检查,以找出出错的地方。

我通常更多地从算法或结构的角度来看待它们。

例如,您可以有一个可以断言的循环不变量——在每次迭代的开始或结束时始终为真。也就是说,如果您的循环应该处理从一个堆栈到另一个堆栈的对象集合,您可以在循环的顶部或底部说 | stack1 | + | stack2 | = c。

如果不变检查失败,它将表明出现了错误。在本例中,这可能意味着您忘记将处理过的元素推送到最终的堆栈上,等等。

维基百科的魔力: 不变量(计算机科学)

在计算机科学中, 如果是真的,则在整个过程中都是真的 具体的操作顺序是 称为那个的不变式 序列。

不变量比变量更“概念化”。通常,它是程序状态的一个属性,该属性始终为 true。保持不变量不变的函数或方法称为保持不变量不变的函数或方法。

例如,一个二叉查找树可能有一个不变式,即对于每个节点,该节点左边子节点的键小于该节点自己的键。正确编写此树的插入函数将保持该不变量。

正如您所看到的,这不是可以存储在变量中的那种东西: 它更像是程序的 关于语句。通过确定程序应该维护哪种类型的不变量,然后检查代码以确保它实际上维护了这些不变量,可以避免代码中的逻辑错误。

接下来,不变量在编写干净的代码时非常有用,因为从概念上知道什么样的不变量应该出现在 进去中,您的代码允许您轻松地决定如何组织代码以达到这些目标。正如前面提到的,它们在调试中也很有用,因为检查不变式是否得到维护通常是一种很好的方法,可以检查您试图执行的任何操作是否实际上正在执行您希望它执行的操作。

在代码块中不会改变的东西

ADT 不变量指定关系 在数据字段(实例变量)之间 前后都必须如此 任何实例方法的执行。

正如这句话所说:

在计算机科学中,一个谓词,如果为真,则在一个特定的操作序列中始终为真,称为该序列的(a)不变量。

为了更好地理解这一点,希望 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)读取一次成功后,增加 countsum = sum + x

3)重复1-2直到读取停止(即 ctrl + D)

循环不变量:

不变量必须是 True 一直都是。因此,最初您只需要这样开始您的代码

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将向 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 一直都是,代码工作正常。

上面的例子是由安德鲁-科宁和芭芭拉-E 写的书 取自

它通常是一个在特定的数学运算下不会改变的量。 例子是一个标量,它在旋转时不会改变。例如,在磁共振成像中,利用旋转不变量来表征组织的特性是有用的,因为这样它的估计在理想情况下并不依赖于扫描仪中身体的方向。

在《 实践中的 Java 并发》一书中有一个关于不变式以及它为什么重要的很好的例子。

尽管该示例以 Java 为中心,但它描述了一些负责计算所提供的整数因子的代码。示例代码试图缓存提供的最后一个数字,以及为提高性能而计算的因子。在这个场景中,示例代码中没有考虑到一个不变量,这使得代码在并发场景中容易受到竞态条件的影响。

enter image description here

这里所有的答案都很棒,但是我觉得我可以在这个问题上给出更多的解释:

从语言的角度来看,不变性意味着永远不变的东西。虽然这个概念实际上来自数学,它是一种流行的证明技术,当与归纳结合。

证明的过程是这样的: 如果你能找到一个处于初始状态的不变量,并且这个不变量在任何应用于该状态的[合法]变换中都能保持,那么你就可以证明,如果某个状态没有这个不变量,那么它就永远不会发生,无论应用于该初始状态的变换序列是什么。

现在,先前的思维方式(再次结合归纳法)使得预测计算机软件的逻辑成为可能。当执行进入循环时尤其重要,循环中的不变量可以用来证明某个循环将产生某个结果,或者它永远不会以某种方式改变程序的状态。

当使用不变式来断言一个循环逻辑时,它被称为 循环不变式循环不变式。它可以在外部循环中使用,但对于循环来说,它非常重要,因为通常有很多种可能性,或者无限多种可能性。

请注意,我使用的词“谓词”的逻辑计算机软件,并没有证明。这是因为虽然在数学 不变可以作为一个证明,它从来不能证明计算机软件执行时将产生什么是预期的,由于事实上,该软件是在许多抽象上执行,这永远不能证明他们将产生什么是预期的(例如硬件抽象层)。

最后,虽然理论上和严格地预测软件逻辑只对高关键性应用程序(如医疗和军事应用程序)很重要。在调试时,仍然可以使用不变式来帮助典型的程序员。它可以用来知道程序在某个位置的哪个位置失败是因为它没有保持某个不变量——我们中的许多人在使用它的时候都没有考虑它。

这个答案是给我5岁的孩子的。不要认为不变量是一个常数或固定的数值。但它可以是。然而,不仅如此。

相反,不变量类似于不同实体之间的固定关系。例如,你的年龄总是比你的亲生父母小。你的年龄和你父母的年龄都会随着时间的推移而改变,但是我上面提到的关系是不变的。

不变量也可以是数值常数。例如,pi的值是圆周长与直径之间的不变比率。无论圆的大小,这个比值都是 pi

Class Invariant是一个在调用相关函数之前和之后都应该为真的条件

例如,平衡树有一个称为 isBalancedInvariant。当您通过某些方法(例如 addNode、 RemoveNode...)修改树时,在修改树之前和之后,isBalanced应该始终为 true