什么是最快的算法三个条件排列？ [英] what is the fastest algorithm for permutations of three condition?

问题描述

任何人可以帮助我关于评估在最短的步骤三个条件最快的方法？
我有三个条件，如果有两个出来是真实的，那么整个前pression变得真正其他假。

Can anybody help me regarding quickest method for evaluating three conditions in minimum steps? I have three conditions and if any of the two comes out to be true,then whole expression becomes true else 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

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

I want any other effective method better than the above two.

我在内存受限的环境中工作（Atmeta8与8 KB的快闪记忆体），并需要在C的解决方案。

I am working in a memory constrained environment (Atmeta8 with 8 KB of flash memory) and need a solution that works in C.

推荐答案

它总是很难给出一个公正的更好的解决方案（以更好什么方面 - code，可读性，执行速度，数量的行机器code指令字节，...？），但既然你问的执行速度在这种情况下，我们可以专注于这一点。

It is always hard to give a just "better" solution (better in what regard -- lines of code, readability, execution speed, number of bytes of machine code instructions, ...?) but since you are asking about execution speed in this case, we can focus on that.

可以引入变量你建议，并用它来降低的条件的简单小于条件一旦答案是已知的。 -小于条件平凡转化为在大多数架构两台机器code指令（例如， CMP （比较），其次是 JL （跳跃，如果小于）或英特尔IA-32 JNL （跳跃如果不小于））。随着一点点运气，编译器会注意到（或者你可以自己做，但我$ PFER附带到处具有相同图案的清晰度p $）的 trues＆LT; 2 将总是的是前两个如果（）陈述属实，并优化了出来。

You can introduce that variable you suggest, and use it to reduce the conditions to a simple less-than condition once the answer is known. Less-than conditions trivially translate to two machine code instructions on most architectures (for example, CMP (compare) followed by JL (jump if less than) or JNL (jump if not less than) on Intel IA-32). With a little luck, the compiler will notice (or you can do it yourself, but I prefer the clarity that comes with having the same pattern everywhere) that trues < 2 will always be true in the first two if() statements, and optimize it out.

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

此，一旦答案是已知的，减少了 conditionN 的可能复杂的评估，以一个简单的小于比较，因为大多数语言的布尔短路行为

This, once an answer is known, reduces the possibly complex evaluation of conditionN to a simple less-than comparison, because of the boolean short-circuiting behavior of most languages.

另一种可能的变型，如果你的语言让你投一个布尔条件为整数，就是要利用这一点，以减少源$ C ​​$ C线的数量。你仍然会评估然而，每个条件。

Another possible variant, if your language allows you to cast a boolean condition to an integer, is to take advantage of that to reduce the number of source code lines. You will still be evaluating each condition, however.

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

这基于铸造一个布尔值FALSE为整数的结果为0，和铸造TRUE结果1.您还可以使用条件运算符相同的效果，尽管知道它可能会引入更多的分支假设工作

This works based on the assumption that casting a boolean FALSE value to an integer results in 0, and casting TRUE results in 1. You can also use the conditional operator for the same effect, although be aware that it may introduce additional branching.

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

根据编译器的optimzer多么聪明，它的可能的能够确定，一旦任何两个条件评估为真，整个条件将始终评估为真，并优化基于

Depending on how smart the compiler's optimzer is, it may be able to determine that once any two conditions have evaluated to true the entire condition will always evaluate to true, and optimize based on that.

• 请注意，除非你实际上异形您code和确定这是罪魁祸首，这是有可能的premature优化的情况。 始终努力为code是由人类程序员第一可读和快速由计算机二来执行，除非你能证明确切的证据证明的尤其的一块$的C $ c您正在寻找是的实际的性能瓶颈。 了解该分析器是如何工作的的，并把它用好。请记住，在大多数情况下，程序员时间是一个可怕的很多比CPU时间更昂贵，而高明的技术需要更长的时间维护程序员进行解析。


• 此外，编译器的软件真聪明件;有时他们实际上将检测到的意图的写code，并能使用旨在使这些操作变得更快具体结构，但依赖于它能够确定你正在尝试做的。这方面的一个很好的例子是使用一个中间变量，它在IA-32可使用 XCHG 省去了中介变量来实现交换两个变量，但是编译器必​​须能够以确定你实际上是这样做，而不是一些聪明这可能会给另一个结果在某些情况下。


• 由于绝大多数写的不明确的，一次性的软件花费绝大多数的寿命在维护模式（以及大量的一次性编写的软件是活着，以及长超过其预期的最佳食用日期），它是有道理的优化可维护性，除非自带在其他方面无法接受的成本。当然，如果你正在评估这些条件一个紧密的循环内的万亿次，针对性的优化非常好可能是有意义的。但是分析器会告诉你到底是哪需要你code的部分被从性能上看更严密审查，这意味着您避免$ C $不必要地复杂℃。

• Note that unless you have actually profiled your code and determined this to be the culprit, this is likely a case of premature optimization. Always strive for code to be readable by human programmers first, and fast to execute by the computer second, unless you can show definitive proof that the particular piece of code you are looking at is an actual performance bottleneck. Learn how that profiler works and put it to good use. Keep in mind that in most cases, programmer time is an awful lot more expensive than CPU time, and clever techniques take longer for the maintenance programmer to parse.
• Also, compilers are really clever pieces of software; sometimes they will actually detect the intent of the code written and be able to use specific constructs meant to make those operations faster, but that relies on it being able to determine what you are trying to do. A perfect example of this is swapping two variables using an intermediary variable, which on IA-32 can be done using XCHG eliminating the intermediary variable, but the compiler has to be able to determine that you are actually doing that and not something clever which may give another result in some cases.
• Since the vast majority of the non-explicitly-throwaway software written spends the vast majority of its lifetime in maintenance mode (and lots of throwaway software written is alive and well long past its intended best before date), it makes sense to optimize for maintainability unless that comes at an unacceptable cost in other respects. Of course, if you are evaluating those conditions a trillion times inside a tight loop, targetted optimization very well might make sense. But the profiler will tell you exactly which portions of your code need to be scrutinized more closely from a performance point of view, meaning that you avoid complicating the code unnecessarily.

和上面告诫说，我一直在努力code最近进行更改，在乍看之下几乎肯定会被认为是premature细节优化。如果您对高性能的要求，使用Profiler来确定哪些code的部分是瓶颈，那么优化不是premature。 （它们仍然可以不明智，然而，这取决于确切的情况。）

And the above caveats said, I have been working on code recently making changes that at first glance would almost certainly be considered premature detail optimization. If you have a requirement for high performance and use the profiler to determine which parts of the code are the bottlenecks, then the optimizations aren't premature. (They may still be ill-advised, however, depending on the exact circumstances.)

这篇关于什么是最快的算法三个条件排列？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！