boolean atLeastTwo(boolean a, boolean b, boolean c) {
if ((a && b) || (b && c) || (a && c)) {
return true;
}
else{
return false;
}
}
他说这可以进一步改善,但如何?
30 回答
803
return (a==b) ? a : c;
说明:
如果 a==b ,则两者都为真或两者都为假 . 如果两者都是真的,我们找到了两个真正的布尔值,并且可以返回true(通过返回 a ) . 如果两者都是假的,即使 c 为真,也不会有两个真正的布尔值,所以我们返回false(通过返回 a ) . 这是 (a==b) ? a 部分 . : c 怎么样?好吧,如果 a==b 为假,那么 a 或 b 中的一个必须为真,所以我们找到了第一个真正的布尔值,唯一重要的是如果 c 也是真的,那么我们返回 c 作为答案 .
212
在C:
return !!a + !!b + !!c >= 2;
12
我不喜欢三元(顶部答案中的 return a ? (b || c) : (b && c); ),而且我没有看到有人提到它 . 它是这样写的:
boolean atLeastTwo(boolean a, boolean b, boolean c) {
if (a) {
return b||c;
}
else {
return b&&C;
}
boolean atLeastTwo(boolean a, boolean b, boolean c) {
if ((a || b) && (c))
return true;
if (a && b)
return true;
if (true)
return false;
// The last line is a red herring, as it will never be reached:
return Math.random() > 0.5;
}
这可以进一步归结为以下内容:
return ((a || b) && (c)) || (a && b);
但现在不再有趣了 .
14
在Ruby中:
[a, b, c].count { |x| x } >= 2
哪个可以在JavaVM上的JRuby中运行 . ;-)
12
在这里得到答案(到目前为止):
public class X
{
static boolean a(final boolean a, final boolean b, final boolean c)
{
return ((a && b) || (b && c) || (a && c));
}
static boolean b(final boolean a, final boolean b, final boolean c)
{
return a ? (b || c) : (b && c);
}
static boolean c(final boolean a, final boolean b, final boolean c)
{
return ((a & b) | (b & c) | (c & a));
}
static boolean d(final boolean a, final boolean b, final boolean c)
{
return ((a?1:0)+(b?1:0)+(c?1:0) >= 2);
}
}
// There is no point in an else if you already returned.
boolean atLeastTwo(boolean a, boolean b, boolean c) {
if ((a && b) || (b && c) || (a && c)) {
return true;
}
return false;
}
然后
// There is no point in an if(true) return true otherwise return false.
boolean atLeastTwo(boolean a, boolean b, boolean c) {
return ((a && b) || (b && c) || (a && c));
}
a&&b || b&&c || a&&c : 394 ms
a ? b||c : b&&c : 435 ms
a&b | b&c | c&a : 420 ms
a + b + c >= 2 : 640 ms
a ^ b ? c : a : 571 ms
a != b ? c : a : 487 ms
DEAD : 170 ms
30 回答
说明:
如果
a==b
,则两者都为真或两者都为假 . 如果两者都是真的,我们找到了两个真正的布尔值,并且可以返回true(通过返回a
) . 如果两者都是假的,即使c
为真,也不会有两个真正的布尔值,所以我们返回false(通过返回a
) . 这是(a==b) ? a
部分 .: c
怎么样?好吧,如果a==b
为假,那么a
或b
中的一个必须为真,所以我们找到了第一个真正的布尔值,唯一重要的是如果c
也是真的,那么我们返回c
作为答案 .在C:
我不喜欢三元(顶部答案中的
return a ? (b || c) : (b && c);
),而且我没有看到有人提到它 . 它是这样写的:这是一种以测试为导向的通用方法 . 不像迄今为止提供的大多数解决方案那样“高效”,而是清晰,经过测试,工作和推广 .
总结一下 . 它被称为布尔代数有一个原因:
如果你看那里的真值表,你可以看到乘法是布尔值,而且简单的加法就是xor .
回答你的问题:
我认为我还没有看到这个解决方案:
它的优点是,一旦它达到你正在寻找的数量,它就会中断 . 因此,如果这是“这1,000,000个值中至少有2个是真的”,前两个实际上是真的,那么它应该比一些更“正常”的解决方案更快 .
这真的取决于你所说的“改进”:
更清晰?
更简洁?
更一般?
更具伸缩性?
快点?
哪一个“改进”在很大程度上取决于具体情况 .
有太多方法可以做到这一点......
最简单的方法(IMO)不会让人感到困惑和易读:
由于没有说明代码应该如何改进,我将努力通过使代码更有趣来改进代码 . 这是我的解决方案:
如果有人想知道这段代码是否有效,这里是使用相同逻辑的简化:
}
这可以进一步归结为以下内容:
但现在不再有趣了 .
在Ruby中:
[a, b, c].count { |x| x } >= 2
哪个可以在JavaVM上的JRuby中运行 . ;-)
在这里得到答案(到目前为止):
并通过反编译器运行它们(javap -c X> results.txt):
您可以看到?:1比原始版本的固定版本略好一些 . 最好的是完全避免分支的那个 . 从较少指令(在大多数情况下)的观点来看这是好的,并且对于CPU的分支预测部分更好,因为分支预测中的错误猜测可能导致CPU停止 .
我认为最有效的一个是整个moonshadow . 它平均使用最少的指令,并减少CPU中流水线停顿的可能性 .
要100%确定你需要找出每条指令的成本(以CPU周期为单位),遗憾的是这些成本并不容易获得(你必须查看热点的来源,然后查看CPU供应商的规格)为每个生成的指令采取) .
请参阅Rotsor的更新答案,以获取代码的运行时分析 .
作为@TofuBeer TofuBeer的优秀帖子的补充,请考虑@pdox pdox的答案:
还要考虑“javap -c”给出的反汇编版本:
pdox的答案编译为比以前任何答案更少的字节代码 . 它的执行时间与其他时间相比如何?
至少在我的电脑上,pdox的答案比@moonshadow moonshadow的答案略快,使得pdox的整体速度最快(在我的HP / Intel笔记本电脑上) .
最明显的改进包括:
然后
但这些改进很小 .
而不是写:
写:
至于表达本身,这样的事情:
或者这个(无论你发现哪个更容易掌握):
它只测试
a
和b
一次,最多测试c
一次 .参考文献
一个C解决方案 .
或者您可能更喜欢:
另一种方法是做到这一点,但不是一个非常好的方式:
Boolean
哈希码值固定为1231为真,1237为false,因此可能同样使用<= 3699
可读性应该是目标 . 阅读代码的人必须立即理解您的意图 . 所以这是我的解决方案 .
直接代码的另一个例子:
不是显然,最简洁的代码 .
Addendum
另一个(稍微优化)的版本:
这可能会稍快一些,假设与0的比较将比使用2的比较使用更快(或可能更少)的代码 .
字面解释适用于所有主要语言:
但我可能会让人们更容易阅读,并可扩展到三个以上 - 这似乎是许多程序员忘记的事情:
他可能不会寻找像bitwise比较运算符那样复杂的东西(通常不是复杂的但是使用布尔运算,使用位运算符是非常奇怪的)或者像转换为int并将它们相加的非常迂回的东西 .
解决这个问题的最直接和最自然的方法是使用如下表达式:
如果你愿意,可以把它放在一个函数中,但它不是很复杂 . 该解决方案在逻辑上简洁而有效 .
只是为了使用XOR来回答一个相对直接的问题......
您不需要使用运算符的短路形式 .
return (a & b) | (b & c) | (c & a);
这将执行与您的版本相同数量的逻辑操作,但是完全无分支 .
这样的问题可以用_465128解决:
从中推断您需要第一行的组和第一列的两个组,从而获得多基因润滑剂的最佳解决方案:
我们可以将bools转换为整数并执行这个简单的检查:
这是使用map / reduce的另一个实现 . 这可以很好地扩展到分布式环境中的数十亿布尔值 . 使用MongoDB:
创建一个数据库
values
的布尔值:创建 Map ,减少功能:
Edit :我喜欢CurtainDog's answer关于将map / reduce应用于通用列表,所以这里有一个map函数,它接受一个回调来确定是否应该计算一个值 .
运行map / reduce:
为什么不按字面意思实现呢? :)
在C中你可以写
a+b+c >= 2
(或!!a+!!b+!!c >= 2
非常安全) .为了回应 TofuBeer 对java字节码的比较,这里有一个简单的性能测试:
这将在我的机器上打印以下内容(使用HotSpot Server VM(14.1-b02,混合模式)在Intel Core 2 sun java 1.6.0_15-b03上运行Ubuntu):
第一次和第二次迭代:
后来的迭代:
我想知道,对于(a b c> = 2)情况,java VM可以做什么会降低性能 .
如果我用
-client
VM开关运行java会发生什么:神秘...
如果我在GNU Java Interpreter中运行它,它会慢几百倍,但
a&&b || b&&c || a&&c
版本会胜出 .使用运行OS X的最新代码从Tofubeer获得的结果:
来自Paul Wagland的Mac Java 1.6.0_26-b03-383-11A511的结果
在Clojure:
用法: