7

任何人都可以帮助我了解以最少步骤评估三个条件的最快方法吗？我有三个条件，如果两个条件中的任何一个为真，则整个表达式变为trueelse 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

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

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

4

8 回答 8

9

这可以简化为：

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

根据每种情况的可能性，您可以优化排序以获得更快的短路（尽管这可能是过早的优化......）

于 2013-06-20T14:18:16.647 回答
4

总是很难给出一个“更好”的解决方案（在哪些方面更好——代码行、可读性、执行速度、机器代码指令的字节数……？）但是因为你问的是执行速度这种情况下，我们可以重点说一下。

您可以引入您建议的变量，并在知道答案后使用它将条件简化为简单的小于条件。在大多数架构上，小于条件通常会转换为两条机器代码指令（例如，在 Intel IA-32 上， CMP（比较）后跟JL（如果小于则跳转）或JNL（如果不小于则跳转））。运气好的话，编译器会注意到（或者你可以自己做，但我更喜欢到处都有相同模式所带来的清晰性），这在前两个语句中总是正确的，并对其进行trues < 2优化。if()

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

conditionN由于大多数语言的布尔短路行为，一旦知道答案，这会将可能的复杂评估减少为简单的小于比较。

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

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
}

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

  • 请注意，除非您实际分析了您的代码并确定这是罪魁祸首，否则这可能是过早优化的情况。始终努力让代码首先被人类程序员阅读，然后让计算机快速执行，除非你能证明你正在查看的特定代码是一个实际的性能瓶颈。了解该分析器的工作原理并充分利用它。请记住，在大多数情况下，程序员的时间比 CPU 时间要昂贵得多，而聪明的技术需要更长的时间来让维护程序员解析。
  • 此外，编译器是非常聪明的软件。有时他们实际上会检测到编写代码的意图，并能够使用旨在使这些操作更快的特定结构，但这取决于它能够确定您正在尝试做什么。一个完美的例子是使用中间变量交换两个变量，这在 IA-32 上可以通过XCHG消除中间变量来完成，但是编译器必须能够确定您实际上正在这样做，而不是聪明的事情可能会给在某些情况下的另一个结果。
  • 由于绝大多数编写的非显式一次性软件在其生命周期中的绝大部分时间都处于维护模式（并且许多编写的一次性软件仍然存在并且远远超过其预期的最佳使用日期），因此优化可维护性是有意义的除非这在其他方面付出了不可接受的代价。当然，如果你在一个紧密的循环中评估这些条件一万亿次，那么有针对性的优化可能很有意义。但是分析器会从性能的角度准确地告诉您代码的哪些部分需要更仔细地检查，这意味着您可以避免不必要地使代码复杂化。

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

于 2013-06-20T14:20:22.707 回答
3

取决于你的语言，我可能会诉诸于：

$cond = array(true, true, false);

if (count(array_filter($cond)) >= 2)

或者

if (array_reduce($cond, function ($i, $k) { return $i + (int)$k; }) >= 2)
于 2013-06-20T14:14:48.367 回答
1

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

如果什么都不知道，我会推荐第二种解决方案 - 只是因为您的意图（至少 2 个条件应该为真）更好地反映在代码中。

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

于 2013-06-20T14:21:37.780 回答
1

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

如果你去：

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

那么你可能有最好的机会，而不依赖于任何进一步的信息，从编译器中获得最好的机器代码。在汇编中，可以将condition2分支的第二次评估返回到第一次评估condition3以减少代码大小，但是在 C 中没有可靠的方法来表达这一点。

如果你知道你通常会通过测试，并且你知道哪两个条件通常会导致失败，那么你可能更喜欢这样写：

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

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

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

但是，更可能有意义地提高性能的是识别条件之间的任何共同因素，或者可以以简化整体测试的方式测试条件的任何方式。

例如，如果测试很简单，那么在汇编中你几乎可以肯定地使用进位做一些基本的技巧来快速积累条件。将其移植回 C有时是可行的。

于 2013-06-21T20:38:10.130 回答
1

您可以考虑简单地添加它们。如果您使用来自标准的masroses stdbool.h，true则为 1，(condition1 + condition2 + condition3) >= 2这就是您想要的。

但这仍然只是一个微优化，通常你不会通过这种技巧获得很多生产力。

于 2013-06-20T14:39:00.187 回答
0

您似乎愿意评估所有条件，因为您自己在问题中提出了这样的解决方案。如果条件是非常复杂的公式，需要许多 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 */
}

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

于 2013-06-20T15:29:04.430 回答
0

试试这个：

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.
    */
}
于 2013-06-21T04:16:15.493 回答