什么是三个条件排列的最快算法？

Question

请问有什么最快的方法可以在最少步骤内评估三个条件吗？我有三个条件，如果其中任意两个为真，则整个表达式为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

我希望有比上述两种方法更有效的方法。

我在一个内存受限的环境中工作（使用8 KB闪存内存的Atmeta8）并需要一个在C语言中运行的解决方案。

- shafeeq

---

我们确定这是C语言，而不是例如Java、C++、C#或其他类似C的语言吗？ - user

@MichaelKjörling：是的，OP在PHP答案上发表了评论。 - Wooble

@Wooble 哦，我现在明白了。好的，继续吧。 :) - user

这些条件是已经计算好的布尔变量，还是尚未评估的表达式，您希望避免对它们进行评估？ - jxh

@jxh 他们需要被计算。 - shafeeq

我知道你需要知道其中两个是否为真。在你的问题中，condition1，condition2和condition3是 int 变量吗？我问这个问题是因为它们在你的问题中看起来像变量。 - jxh

Answer 1

这可以简化为：

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

根据每个条件的可能性，您可以优化排序以获得更快的短路（尽管这可能过早进行优化...）

- Wooble

---

抱歉，这段文本似乎没有意义，无法翻译。请提供更多上下文或正确的文本。 - shafeeq

虽然这可能是过早的优化。- 不，不会的，因为它不需要任何努力，也不会引入任何重大的代码更改。 - Christian Rau

@ChristianRau：嗯，需要花费一些精力来计算每个条件的统计概率，这可能很容易，也可能不那么容易。 - Wooble

不仅仅是按可能性排序。如果其中一个条件更难评估，则应将其移动到更有可能被短路的位置。 - sh1

Answer 2

很难给出一个公正的“更好”的解决方案（在哪个方面更好 - 代码行数，可读性，执行速度，机器代码指令字节数等？），但由于您在这种情况下询问执行速度，我们可以专注于此。

您可以引入建议的变量，并在答案已知后将其用于将条件减少到简单的小于条件。小于条件在大多数体系结构上可以轻松地转换为两个机器代码指令（例如，在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
}

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

请注意：除非你已经对代码进行了分析并确定这是罪魁祸首，否则这很可能是过早优化的情况。 始终要让代码首先易于人类程序员阅读，其次才是计算机执行速度快，除非你能证明你正在查看的特定代码片段是一个实际存在的性能瓶颈。学习如何使用分析器并将其充分利用。请记住，在大多数情况下，程序员的时间比 CPU 时间更昂贵，而巧妙的技术需要更长时间来解析维护程序员。

另外，编译器是非常聪明的软件；有时它们实际上会检测到所写代码的意图，并能够使用特定的结构使这些操作更快，但这取决于它能否确定你试图做什么。一个完美的例子是使用中间变量交换两个变量，在 IA-32 上可以使用XCHG消除中间变量，但编译器必须能够确定你实际上正在这样做，而不是某些情况下可能导致其他结果的聪明方法。

由于绝大多数非显式一次性使用的软件都在维护模式下度过了它的大部分生命周期（而且很多一次性使用的软件在其预期的最佳使用日期之后仍然活跃），因此优化可维护性是有意义的，除非这会带来其他方面无法接受的代价。当然，如果你在一个紧密的循环内评估这些条件一万亿次，有针对性的优化可能是有意义的。但分析器将告诉您哪些代码部分需要从性能角度更加仔细地审查，这意味着您可以避免不必要地使代码复杂化。

在上述警告的前提下，我最近一直在编写代码并进行更改，这些更改乍一看几乎肯定会被认为是过早的详细优化。如果您需要高性能，并使用分析器确定代码的瓶颈部分，则这些优化不算过早。（但是，根据具体情况，它们仍可能是不明智的。）

- user

---

尊敬的@Michael，我所说的更好是指执行速度更快。 你的第二种方法值得赞赏，谢谢。 但正如你所说，代码应该易于阅读，因为我们编写的是给机器而不是人类，注释才是我们理解代码的手段。 - shafeeq

优化执行速度和内存使用率两者都很困难。单独优化其中一个很容易，但同时优化两者则更加困难；通常情况下，人们会选择其中一个并以牺牲另一个为代价进行优化。你确定找不到两个位来重新利用吗？（变量真的被保存在闪存中吗？如果是这样的话：糟糕！） - user

Answer 3

根据您的语言，我可能会采用以下方式：

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

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

或者

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

- deceze

---

@shafeeq 那种信息真的应该直接放在问题中，但至少它在某个地方被明确提到了。 - user

Answer 4

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

如果您选择：

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

如果您不依赖任何进一步的信息，那么您很可能有最好的机会从编译器中获取最佳的机器代码。在汇编中，可以做一些事情，例如让condition2的第二次评估返回到condition3的第一次评估，以减少代码大小，但是在C语言中没有可靠的方法来表达这一点。

如果您知道通常会失败的测试，并且知道哪两个条件通常会导致失败，则可能更喜欢编写：

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

但编译器仍有相当大的机会完全重组它并使用自己的快捷排列。

您可能想要使用__builtin_expect()或_Rarely()或其他编译器提供的注释来指示条件的可能结果。

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

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

- sh1

Answer 5

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

如果不知道其他情况，我会推荐第二个解决方案——只是因为您的意图（至少应满足2个条件）更好地反映在代码中。

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

- flolo

---

实际上，这是针对Atmega8的代码，并且这是在内部循环中。因此，考虑速度因素，第一种方法更好。这样可以吗？ - shafeeq

Answer 6

你可以考虑简单地添加它们。如果你使用来自标准库stdbool.h的宏，那么true就是1，而(condition1 + condition2 + condition3) >= 2就是你想要的。但这只是微小的优化，通常这种技巧不会带来很多生产力。

- akalenuk

---

请注意，这几乎完全是我在我的答案中建议的技术（除了显式转换）。 - user

Answer 7

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

这取决于计算条件的成本是否昂贵。计算时间必须主导线程创建和同步开销，以确定是否能够加快速度。

- jxh

Answer 8

试试这个：

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.
    */
}

- sukumarst

---

在所有条件都被评估之后引入一个额外的操作（按位“与”）如何帮助减少需要评估的条件数量？这种技术不太可能消除比较的需要，因此只会增加代码。 OP的问题基于需要评估所有组成条件，而不是找出其中至少两个为真所需的时间。另外，您的示例仅在计数中设置了特定位时才有效；如果涉及五个条件怎么办？ 5（十进制）= 101（二进制）; 101（二进制）和2（十六进制）== 0。失败。 - user