C++ 在 if 语句设置条件为真和 or-ing 循环条件之间的行为差异
C++ difference in behavior between if statement setting condition to true and or-ing a condition in loop
我正在为我的 CS class 开发 Datalog 解释器,我 运行 遇到了一个 st运行ge 问题,我的规则评估需要太多遍才能完成。在查看我的代码后,我在下面做了两处修改,修复了我的评估以正确的遍数执行:
//original form
bool addedFacts = false;
for (X x: xs) {
addedFacts = addedFacts || set.insert(x).second;
}
//modified form
bool addedFacts = false;
for (X x: xs) {
if (set.insert(x).second) {
addedFacts = true;
}
}
对我来说,这两个代码结构在逻辑上是等价的。有没有一个执行正确,一个执行incorrectly/inefficiently的原因?
这是发生的问题的可构建示例:
#include <iostream>
#include <set>
#include <vector>
using std::set;
using std::vector;
using std::cout;
using std::endl;
const int CAP = 100;
class Rule {
public:
int factor;
Rule(int factor) {
this->factor = factor;
}
bool evaluateInefficient(set<int>& facts) {
vector<int> data;
bool addedFacts = false;
for (int fact : facts) {
data.push_back(fact);
}
for (int datum : data) {
int newFact = datum * factor;
if (newFact < CAP) {
addedFacts = addedFacts || facts.insert(newFact).second;
}
}
return addedFacts;
}
bool evaluate(set<int>& facts) {
vector<int> data;
bool addedFacts = false;
for (int fact : facts) {
data.push_back(fact);
}
for (int datum : data) {
int newFact = datum * factor;
if (newFact < CAP) {
if (facts.insert(newFact).second) {
addedFacts = true;
}
}
}
return addedFacts;
}
};
int doublyInefficient(vector<Rule>& rules) {
set<int> facts;
facts.insert(1);
bool addedFacts = true;
int passes = 0;
while (addedFacts) {
passes++;
addedFacts = false;
for (Rule rule : rules) {
addedFacts = addedFacts || rule.evaluateInefficient(facts);
}
}
return passes;
}
int singlyInefficient(vector<Rule>& rules) {
set<int> facts;
facts.insert(1);
bool addedFacts = true;
int passes = 0;
while (addedFacts) {
passes++;
addedFacts = false;
for (Rule rule : rules) {
addedFacts = addedFacts || rule.evaluate(facts);
}
}
return passes;
}
int efficient(vector<Rule>& rules) {
set<int> facts;
facts.insert(1);
bool addedFacts = true;
int passes = 0;
while (addedFacts) {
passes++;
addedFacts = false;
for (Rule rule : rules) {
if (rule.evaluate(facts)) {
addedFacts = true;
}
}
}
return passes;
}
int main(int argc, char* argv[]) {
//build the rules
vector<Rule> rules;
rules.push_back(Rule(2));
rules.push_back(Rule(3));
rules.push_back(Rule(5));
rules.push_back(Rule(7));
rules.push_back(Rule(11));
rules.push_back(Rule(13));
//Show three different codes that should (in my mind) take the same amount of passes over the rules but don't
cout << "Facts populated after " << doublyInefficient(rules) << " passes through the Rules." << endl;
cout << "Facts populated after " << singlyInefficient(rules) << " passes through the Rules." << endl;
cout << "Facts populated after " << efficient(rules) << " passes through the Rules." << endl;
getchar();
}
我在 visual studio 2017 年 运行 处于调试和发布模式(32 位)时得到以下输出。据我所知,代码未优化。
Facts populated after 61 passes through the Rules.
Facts populated after 17 passes through the Rules.
Facts populated after 7 passes through the Rules.
addedFacts = addedFacts || set.insert(x).second;
和
if (set.insert(x).second) {
addedFacts = true;
}
绝对不是一回事。第一块代码相当于:
if (!addedFacts) {
addedFacts = set.insert(x).second;
}
!addedFacts
检查有很大不同。
由于短路评估而产生差异:
考虑 (expr1 || expr2)
形式的表达式。短路意味着如果 expr1
计算为 true
,则表达式 expr2
根本不会被计算(参见 this online c++ standard draft,重点是我的):
5.15 Logical OR operator
The || operator groups left-to-right. The operands are both
contextually converted to bool (Clause [conv]). It returns true if
either of its operands is true, and false otherwise. Unlike |, ||
guarantees left-to-right evaluation; moreover, the second operand is
not evaluated if the first operand evaluates to true.
因此,在您的表达式 addedFacts || set.insert(x).second
中,从 addedFacts
第一次变为 true
的那一点起,表达式 set.insert(x).second
将不再执行。我想这是 "wrong" 行为,因为你的 set
将不包含相应的 x
es。
我正在为我的 CS class 开发 Datalog 解释器,我 运行 遇到了一个 st运行ge 问题,我的规则评估需要太多遍才能完成。在查看我的代码后,我在下面做了两处修改,修复了我的评估以正确的遍数执行:
//original form
bool addedFacts = false;
for (X x: xs) {
addedFacts = addedFacts || set.insert(x).second;
}
//modified form
bool addedFacts = false;
for (X x: xs) {
if (set.insert(x).second) {
addedFacts = true;
}
}
对我来说,这两个代码结构在逻辑上是等价的。有没有一个执行正确,一个执行incorrectly/inefficiently的原因? 这是发生的问题的可构建示例:
#include <iostream>
#include <set>
#include <vector>
using std::set;
using std::vector;
using std::cout;
using std::endl;
const int CAP = 100;
class Rule {
public:
int factor;
Rule(int factor) {
this->factor = factor;
}
bool evaluateInefficient(set<int>& facts) {
vector<int> data;
bool addedFacts = false;
for (int fact : facts) {
data.push_back(fact);
}
for (int datum : data) {
int newFact = datum * factor;
if (newFact < CAP) {
addedFacts = addedFacts || facts.insert(newFact).second;
}
}
return addedFacts;
}
bool evaluate(set<int>& facts) {
vector<int> data;
bool addedFacts = false;
for (int fact : facts) {
data.push_back(fact);
}
for (int datum : data) {
int newFact = datum * factor;
if (newFact < CAP) {
if (facts.insert(newFact).second) {
addedFacts = true;
}
}
}
return addedFacts;
}
};
int doublyInefficient(vector<Rule>& rules) {
set<int> facts;
facts.insert(1);
bool addedFacts = true;
int passes = 0;
while (addedFacts) {
passes++;
addedFacts = false;
for (Rule rule : rules) {
addedFacts = addedFacts || rule.evaluateInefficient(facts);
}
}
return passes;
}
int singlyInefficient(vector<Rule>& rules) {
set<int> facts;
facts.insert(1);
bool addedFacts = true;
int passes = 0;
while (addedFacts) {
passes++;
addedFacts = false;
for (Rule rule : rules) {
addedFacts = addedFacts || rule.evaluate(facts);
}
}
return passes;
}
int efficient(vector<Rule>& rules) {
set<int> facts;
facts.insert(1);
bool addedFacts = true;
int passes = 0;
while (addedFacts) {
passes++;
addedFacts = false;
for (Rule rule : rules) {
if (rule.evaluate(facts)) {
addedFacts = true;
}
}
}
return passes;
}
int main(int argc, char* argv[]) {
//build the rules
vector<Rule> rules;
rules.push_back(Rule(2));
rules.push_back(Rule(3));
rules.push_back(Rule(5));
rules.push_back(Rule(7));
rules.push_back(Rule(11));
rules.push_back(Rule(13));
//Show three different codes that should (in my mind) take the same amount of passes over the rules but don't
cout << "Facts populated after " << doublyInefficient(rules) << " passes through the Rules." << endl;
cout << "Facts populated after " << singlyInefficient(rules) << " passes through the Rules." << endl;
cout << "Facts populated after " << efficient(rules) << " passes through the Rules." << endl;
getchar();
}
我在 visual studio 2017 年 运行 处于调试和发布模式(32 位)时得到以下输出。据我所知,代码未优化。
Facts populated after 61 passes through the Rules.
Facts populated after 17 passes through the Rules.
Facts populated after 7 passes through the Rules.
addedFacts = addedFacts || set.insert(x).second;
和
if (set.insert(x).second) {
addedFacts = true;
}
绝对不是一回事。第一块代码相当于:
if (!addedFacts) {
addedFacts = set.insert(x).second;
}
!addedFacts
检查有很大不同。
由于短路评估而产生差异:
考虑 (expr1 || expr2)
形式的表达式。短路意味着如果 expr1
计算为 true
,则表达式 expr2
根本不会被计算(参见 this online c++ standard draft,重点是我的):
5.15 Logical OR operator
The || operator groups left-to-right. The operands are both contextually converted to bool (Clause [conv]). It returns true if either of its operands is true, and false otherwise. Unlike |, || guarantees left-to-right evaluation; moreover, the second operand is not evaluated if the first operand evaluates to true.
因此,在您的表达式 addedFacts || set.insert(x).second
中,从 addedFacts
第一次变为 true
的那一点起,表达式 set.insert(x).second
将不再执行。我想这是 "wrong" 行为,因为你的 set
将不包含相应的 x
es。