java找到三元组中间值的最快方法？

Question

给定的是一个由三个数值组成的数组，我想知道这三个数值的中间值

问题是，找到三者中间的最快方法是什么

我的方法是这种模式——因为有三个数字，所以有六种排列：

if (array[randomIndexA] >= array[randomIndexB] &&
    array[randomIndexB] >= array[randomIndexC])

如果有人能帮我找到一种更优雅、更快的方法，那就太好了

Answer 1

以下是仅使用条件表达的方法：

int a, b, c = ...
int middle = (a <= b) 
    ? ((b <= c) ? b : ((a < c) ? c : a)) 
    : ((a <= c) ? a : ((b < c) ? c : b));

编辑：

1. @Pagas发现的上述错误已修复
2. @Pagas还指出，如果只使用条件语句，则不能使用少于5个条件语句，但可以使用临时变量或值交换来减少这种情况
3. 我想补充一点，很难预测一个纯粹的条件或赋值解决方案是否会更快。这可能取决于JIT有多好，但我认为优化器更容易分析有条件的版本

Answer 2

如果硬件能够在没有分支的情况下回答min和max查询（今天的大多数CPU都可以这样做），那么可以在没有分支的情况下回答查询

运算符^表示按位异或

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

这是正确的，因为：

• xor是交换的和结合的
• 等位异或产生零
• 带零的异或不会改变位

应为int/float选择适当的min/max函数。 如果只存在正浮点，则可以直接在浮点表示上使用整数min/max（这可能是可取的，因为整数运算通常更快）

在硬件不支持最小/最大的不太可能的情况下，可以执行以下操作：

max(a,b)=(a+b+|a-b|)/2
min(a,b)=(a+b-|a-b|)/2

然而，在使用浮点操作时，这是不正确的，因为需要精确的最小/最大值，而不是接近它的值。幸运的是，浮点最小值/最大值已经在硬件中支持了很长时间（在x86上，从奔腾III开始）

Answer 3

还有一个主意。有三个数字{a,b,c}。然后：

middle = (a + b + c) - min(a,b,c) - max(a,b,c);

当然，我们必须记住数字限制

Answer 4

最多可以进行两次比较

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;
}

Answer 5

这里有一个答案，使用min/max，没有分支（https://stackoverflow.com/a/14676309/2233603）。实际上，4 min/max运算足以找到中值，不需要xor：

median = max(min(a,b), min(max(a,b),c));

不过，它不会给出中值的指数

所有案件的细目：

a b c
1 2 3   max(min(1,2), min(max(1,2),3)) = max(1, min(2,3)) = max(1, 2) = 2
1 3 2   max(min(1,3), min(max(1,3),2)) = max(1, min(3,2)) = max(1, 2) = 2
2 1 3   max(min(2,1), min(max(2,1),3)) = max(1, min(2,3)) = max(1, 2) = 2
2 3 1   max(min(2,3), min(max(2,3),1)) = max(2, min(3,1)) = max(2, 1) = 2
3 1 2   max(min(3,1), min(max(3,1),2)) = max(1, min(3,2)) = max(1, 2) = 2
3 2 1   max(min(3,2), min(max(3,2),1)) = max(2, min(3,1)) = max(2, 1) = 2

Answer 6

如果你在寻找最有效的解决方案，我可以想象它是这样的：

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";
  }
}

这种方法至少需要两次，最多需要三次比较。它故意忽略了两个值相等的可能性（就像你的问题一样）：如果这很重要，那么可以扩展方法来检查这一点