Java 找到三元组中间值的最快方法？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1582356/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Fastest way of finding the middle value of a triple?
提问by Gnark
Given is an array of three numeric values and I'd like to know the middle value of the three.
给定的是一个包含三个数值的数组，我想知道这三个值的中间值。
The question is, what is the fastestway of finding the middle of the three?
问题是，找到三个中间的最快方法是什么？
My approach is this kind of pattern - as there are three numbers there are six permutations:
我的方法是这种模式 - 因为有三个数字，所以有六个排列：
if (array[randomIndexA] >= array[randomIndexB] &&
array[randomIndexB] >= array[randomIndexC])
It would be really nice, if someone could help me out finding a more elegantand fasterway of doing this.
如果有人能帮我找到一种更优雅、更快速的方法，那就太好了。
采纳答案by Tim
If you are looking for the most efficient solution, I would imagine that it is something like this:
如果您正在寻找最有效的解决方案，我会想象它是这样的：
if (array[randomIndexA] > array[randomIndexB]) {
if (array[randomIndexB] > array[randomIndexC]) {
return "b is the middle value";
} else if (array[randomIndexA] > array[randomIndexC]) {
return "c is the middle value";
} else {
return "a is the middle value";
}
} else {
if (array[randomIndexA] > array[randomIndexC]) {
return "a is the middle value";
} else if (array[randomIndexB] > array[randomIndexC]) {
return "c is the middle value";
} else {
return "b is the middle value";
}
}
This approach requires at least two and at most three comparisons. It deliberately ignores the possibility of two values being equal (as did your question): if this is important, the approach can be extended to check this also.
这种方法需要至少两次，最多三次比较。它故意忽略了两个值相等的可能性（就像你的问题一样）：如果这很重要，可以扩展该方法来检查这一点。
回答by Stephen C
Here's how you can express this using only conditionals:
以下是仅使用条件来表达这一点的方法：
int a, b, c = ...
int middle = (a <= b)
? ((b <= c) ? b : ((a < c) ? c : a))
: ((a <= c) ? a : ((b < c) ? c : b));
EDITS:
编辑：
- Errors in above found by @Pagas have been fixed.
- @Pagas also pointed out that you cannot do this with fewer than 5 conditionals if you only use conditional, but you can reduce this using temporary variables or value swapping.
- I would add that it is hard to predict whether a pure conditional or assignment solution would be faster. It is likely to depend on how good the JIT is, but I think the conditional version would be easier for the optimizer to analyse.
- @Pagas 发现的上述错误已得到修复。
- @Pagas 还指出，如果仅使用条件，则不能使用少于 5 个条件来执行此操作，但是您可以使用临时变量或值交换来减少这种情况。
- 我要补充的是，很难预测纯条件或分配解决方案是否会更快。这可能取决于 JIT 有多好，但我认为优化器更容易分析条件版本。
回答by rsp
Using idxA to idxC in ary,
在 ary 中使用 idxA 到 idxC，
int ab = ary[idxA] < ary[idxB] ? idxA : idxB;
int bc = ary[idxB] < ary[idxC] ? idxB : idxC;
int ac = ary[idxA] < ary[idxC] ? idxA : idxC;
int idxMid = ab == bc ? ac : ab == ac ? bc : ab;
indexMiddle points to the middle value.
indexMiddle 指向中间值。
Explanation: from the 3 minima 2 are the overall minimum and the other value must be the middle. Because we check equality we can compare the indices in the last line instead of having to compare the array values.
说明：从 3 个最小值中 2 是整体最小值，另一个值必须是中间值。因为我们检查相等性，所以我们可以比较最后一行中的索引，而不必比较数组值。
回答by Toad
or a one liner for finding the index in the array containing the middle value:
或用于在包含中间值的数组中查找索引的单行：
int middleIndex = (a[0]<a[1]) ? ((a[0]<a[2) ? a[2] : a[0]) : ((a[1]<a[2) ? a[2] : a[1]);
回答by Thorbj?rn Ravn Andersen
If you must find one out of X values satisfying some criteria you have to at least compare that value to each of the X-1 others. For three values this means at least two comparisons. Since this is "find the value that is not the smallest and not the largest" you can get away with only two comparisons.
如果您必须找到满足某些标准的 X 值中的一个，您至少必须将该值与其他 X-1 个值中的每一个进行比较。对于三个值，这意味着至少进行两次比较。由于这是“找到不是最小也不是最大的值”，因此您只需进行两次比较就可以逃脱。
You should then concentrate on writing the code so you can very clearly see what goes on and keep it simple. Here this means nested if's. This will allow the JVM to optimize this comparison as much as possible at runtime.
然后你应该专注于编写代码，这样你就可以非常清楚地看到发生了什么并保持简单。这里的意思是嵌套的 if。这将允许 JVM 在运行时尽可能地优化这种比较。
See the solution provided by Tim (Fastest way of finding the middle value of a triple?) to see an example of this. The many code line does not necessarily turn out to be larger code than nested questionmark-colon's.
请参阅 Tim 提供的解决方案（找到三元组中间值的最快方法？）以查看此示例。许多代码行不一定比嵌套的问号冒号的代码更大。
回答by Mark Bessey
You might as well write this in the most straightforward, way. As you said, there are only six possibilities. No reasonable approach is going to be any faster or slower, so just go for something easy to read.
你不妨用最直接的方式来写这个。正如你所说，只有六种可能性。没有合理的方法会更快或更慢，所以只需要一些易于阅读的东西。
I'd use min() and max() for conciseness, but three nested if/thens would be just as good, I think.
为了简洁起见，我会使用 min() 和 max()，但我认为三个嵌套的 if/thens 也一样好。
回答by Zach Conn
This can be done with two comparisons at most.
这最多可以通过两次比较来完成。
int median(int a, int b, int c) {
if ( (a - b) * (c - a) >= 0 ) // a >= b and a <= c OR a <= b and a >= c
return a;
else if ( (b - a) * (c - b) >= 0 ) // b >= a and b <= c OR b <= a and b >= c
return b;
else
return c;
}
回答by Max
It's possible to answer the query without branches if the hardware can answer min and max queries without branches (most CPUs today can do this).
如果硬件可以在没有分支的情况下回答最小和最大查询，则可以在没有分支的情况下回答查询（当今大多数 CPU 都可以这样做）。
The operator ^ denotes bitwise xor.
运算符 ^ 表示按位异或。
Input: triple (a,b,c)
1. mx=max(max(a,b),c)
2. mn=min(min(a,b),c)
3. md=a^b^c^mx^mn
4. return md
This is correct because:
这是正确的，因为：
- xor is commutative and associative
- xor on equal bits produces zero
- xor with zero doesn't change the bit
- xor 是可交换的和结合的
- 相等位上的异或产生零
- 与零的异或不会改变位
The appropriate min/max functions should be chosen for int/float. If only positive floats are present then it's possible to use integer min/max directly on the floating point representation (this could be desirable, since integer operations are generally faster).
应为 int/float 选择适当的最小/最大函数。如果只存在正浮点数，则可以直接在浮点表示上使用整数 min/max（这可能是可取的，因为整数运算通常更快）。
In the unlikely scenario that the hardware doesn't support min/max, it's possible to do something like this:
在硬件不支持最小/最大的不太可能的情况下，可以执行以下操作：
max(a,b)=(a+b+|a-b|)/2
min(a,b)=(a+b-|a-b|)/2
However, this isn't correct when using float operations since the exact min/max is required and not something that's close to it. Luckily, float min/max has been supported in hardware for ages (on x86, from Pentium III and onwards).
但是，这在使用浮点运算时是不正确的，因为需要精确的最小值/最大值而不是接近它的值。幸运的是，float min/max 已经在硬件中支持多年（在 x86 上，从 Pentium III 开始）。
回答by Ivan Tolstosheyev
This one will work:
这将工作：
template<typename T> T median3_1_gt_2(const T& t1, const T& t2, const T& t3) {
if (t3>t1) {
return t1;
} else {
return std::max(t2, t3);
}
}
template<typename T> T median3(const T& t1, const T& t2, const T& t3) {
if (t1>t2) {
return median3_1_gt_2(t1, t2, t3);
} else {
return median3_1_gt_2(t2, t1, t3);
}
}
回答by azmi
if(array[aIndex] > array[bIndex]) {
if(array[bIndex] > array[cIndex]) return bIndex;
if(array[aIndex] > array[cIndex]) return cIndex;
return aIndex;
} else {
if(array[bIndex] < array[cIndex]) return bIndex;
if(array[aIndex] < array[cIndex]) return cIndex;
return aIndex;
}
