我正在为我的CS课开发数据日志解释器，我遇到了一个奇怪的问题，我的规则评估需要太多次才能完成。在查看了我的代码后，我进行了以下两项修改，将我的评估固定为以正确的传递次数执行：
//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;
}
}
对我来说，这两种代码结构在逻辑上似乎是等价的。是否有理由正确执行而执行不正确/效率低下？ 下面是所发生问题的可构建示例：
#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将根本不会被计算(参见这个在线 C++ 标准草案，ephasis 是我的(：
5.15 逻辑 OR 运算符
|| 运算符从左到右分组。操作数都是 上下文转换为布尔值(子句 [conv](。如果 它的任何操作数都是真的，否则是假的。不像 |， || 保证从左到右的评估;此外，第二个操作数是 如果第一个操作数的计算结果为 true，则不计算。
因此，在您的表达式addedFacts || set.insert(x).second中，从addedFacts第一次变得true开始，表达式set.insert(x).second将不再被执行。我想这是"错误"的行为，因为您的set不会包含相应的x。