对于三种情况的排列,最快的算法是什么?

有人可以帮我解决在最小步骤中评估三个条件的最快方法吗? 我有三个条件,如果两个中的任何一个都是真的,那么整个表达式变为true否则为false

我试过两种方法:

 if ((condition1 && condition2) || (condition1 && condition3) || (condition2 && condition3)) 

另一种方法是通过引入变量i

 i = 0; if (condition1) i++; if (condition2) i++; if (condition3) i++; if (i >= 2) //do something 

我想要比上面两个更好的任何其他有效方法。

我在内存受限的环境中工作(Atmeta8具有8 KB的闪存)并且需要一个在C中工作的解决方案。

总是很难给出一个更好的“更好”的解决方案(更好的方面 – 代码行,可读性,执行速度,机器代码指令的字节数,……?)但是因为你在询问执行速度在这种情况下,我们可以专注于此。

您可以引入您建议的变量,并在知道答案后使用它将条件简化为简单的小于条件。 在大多数体系结构上,小于条件通常会转换为两个机器代码指令(例如, CMP (比较),然后是JL (跳过小于)或JNL (跳过,如果不小于)在Intel IA-32上)。 运气好的话,编译器会注意到(或者你可以自己做,但我更喜欢在任何地方都有相同模式的清晰度),在前两个if()语句中, trues < 2始终为真,并优化出来。

 int trues = 0; if (trues < 2 && condition1) trues++; if (trues < 2 && condition2) trues++; if (trues < 2 && condition3) trues++; // ... if (trues >= 2) { // do something } 

一旦得到答案,这就将conditionN N的可能复杂评估简化为简单的小于比较,因为大多数语言的布尔短路行为。

另一种可能的变体,如果您的语言允许您将布尔条件转换为整数,则可以利用它来减少源代码行的数量。 但是,您仍将评估每个条件。

 if( (int)(condition1) + (int)(condition2) + (int)(condition3) >= 2) { // do something } 

这是基于这样的假设:将布尔FALSE值转换为整数会导致0,并且转换为TRUE会导致1.您也可以使用条件运算符获得相同的效果,但要注意它可能会引入额外的分支。

 if( ((condition1) ? 1 : 0) + ((condition2) ? 1 : 0) + ((condition3) ? 1 : 0) >= 2) { // do something } 

根据编译器的优化器的智能程度,它可以确定一旦任何两个条件评估为真,整个条件将始终评估为真,并基于此进行优化。

  • 请注意, 除非您实际编写了代码并将其确定为罪魁祸首否则这可能是过早优化的情况。 始终努力让代码首先由人类程序员可读 ,并且计算机可以快速执行,除非您能够明确certificate您正在查看的特定代码片段是实际的性能瓶颈。 了解该分析器的工作原理并充分利用它。 请记住,在大多数情况下,程序员时间比CPU时间要贵很多,而且需要更长时间才能让维护程序员解析。
  • 此外,编译器是非常聪明的软件; 有时它们实际上会检测所编写代码的意图 ,并能够使用特定的构造来使这些操作更快,但这依赖于它能够确定你想要做什么。 一个完美的例子是使用中间变量交换两个变量,在IA-32上可以使用XCHG消除中间变量,但是编译器必须能够确定你实际上是在做这个而不是聪明的东西可能在某些情况下给出另一个结果 。
  • 由于绝大多数非明确一次性软件的大部分使用寿命都是在维护模式下进行的(而且许多一次性软件都是有效的,并且远远超过其预期的最佳日期),因此优化可维护性是有意义的。除非在其他方面付出不可接受的代价。 当然,如果您在紧密循环中评估这些条件数万亿次,那么目标优化可能很有意义。 但是,从性能的角度来看,探查器会准确地告诉您需要仔细检查代码的哪些部分,这意味着您可以避免不必要地使代码复杂化。

而上述警告说,我最近一直在研究代码,乍一看几乎肯定会被认为是过早的细节优化。 如果您需要高性能并使用分析器来确定代码的哪些部分是瓶颈,那么优化并不是不成熟的。 (但是,根据具体情况,他们可能仍然是不明智的。)

这可以简化为:

 if((condition1 && (condition2 || condition3)) || (condition2 && condition3)) //do something 

根据每种情况的可能性,您可以优化排序以获得更快的短路(尽管这可能是过早的优化……)

取决于你的语言,我可能会采取以下方式:

 $cond = array(true, true, false); if (count(array_filter($cond)) >= 2) 

要么

 if (array_reduce($cond, function ($i, $k) { return $i + (int)$k; }) >= 2) 

对此没有绝对的答案。 这在很大程度上取决于底层架构。 例如,如果你用VHDL或Verilog编程一些硬件电路,那么肯定第一个会给你最快的结果。 我假设你的目标是某种CPU,但即使在这里,它也将取决于目标cpu,它支持的指令以及它们将采用的时间。 此外,您没有指定目标语言(例如,您的第一种方法可以短路,这可能会严重影响速度)。

如果不知道其他什么我会推荐第二个解决方案 – 只是因为你的意图(至少2个条件应该是真的)更好地反映在代码中。

两个解决方案的速度差异不是很高 – 如果这只是一些逻辑,而不是执行很多次的最内层循环的一部分,我甚至会猜测过早优化并尝试优化其他地方。

由于我们不是采用深度流水线架构,因此分支避免可能没有价值,这通常会引导桌面开发人员提供的优化。 在这里,捷径是金色的。

如果你去:

 if ((condition1 && (condition2 || condition3)) || (condition2 && condition3)) 

然后你可能有最好的机会,不依赖于任何进一步的信息,从编译器中获取最好的机器代码。 在汇编时,可以做一些事情,比如将condition2 2的第二次评估分支回到condition2的第一次评估,以减少代码大小,但是没有可靠的方法在C中表达这一点。

如果您知道通常会通过测试失败,并且您知道通常会导致哪两个条件,那么您可能更愿意写:

 if ((rare1 || rare2) && (common3 || (rare1 && rare2))) 

但是编译器仍然很有可能完全重新排列并使用自己的快捷方式。

您可能希望使用__builtin_expect()_Rarely()或编译器提供的任何内容来注释事物,以指示条件的可能结果。

然而,更有可能有意义地提高性能的是识别条件之间的任何常见因素或以简化整体测试的方式测试条件的任何方式。

例如,如果测试很简单,那么在assembly中你几乎可以肯定做一些基本的诡计,带来快速积累条件。 将其移回C 有时是可行的。

您可以考虑简单地添加它们。 如果你使用标准stdbool.h masros,那么true是1,而(condition1 + condition2 + condition3) >= 2就是你想要的。

但它仍然只是微观优化,通常你不会通过这种技巧获得大量的生产力。

您似乎希望评估所有条件,因为您在自己的问题中提出了这样的解决方案。 如果条件是非常复杂的公式,需要花费很多CPU周期来计算(比如大约几百毫秒),那么您可以考虑使用线程同时评估所有三个条件以获得加速。 就像是:

 pthread_create(&t1, detached, eval_condition1, &status); pthread_create(&t2, detached, eval_condition2, &status); pthread_create(&t3, detached, eval_condition3, &status); pthread_mutex_lock(&status.lock); while (status.trues < 2 && status.falses < 2) { pthread_cond_wait(&status.cond, &status.lock); } pthread_mutex_unlock(&status.lock); if (status.trues > 1) { /* do something */ } 

这是否能让您加快速度取决于计算条件的成本。 计算时间必须支配线程创建和同步开销。

试试这个:

 unsigned char i; i = condition1; i += condition2; i += condition3; if (i & (unsigned char)0x02) { /* At least 2 conditions are True 0b00 - 0 conditions are true 0b01 - 1 conditions are true 0b11 - 3 conditions are true 0b10 - 2 conditions are true So, Checking 2nd LS bit is good enough. */ }