找到三重中间值的最快方法？

Question

给定是一个包含三个数值的数组,我想知道这三个数值的中间值.

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

我的方法是这种模式 - 因为有三个数字有六种排列:

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

如果有人可以帮助我找到更优雅,更快捷的方法,那将是非常好的.

Answer 1

这里有一个使用min/max和没有分支的答案(/sf/answers/1027341661/).实际上4分钟/最大操作足以找到中位数,不需要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 2

如果硬件可以在没有分支的情况下回答最小和最大查询(现在大多数CPU可以执行此操作),则可以在没有分支的情况下回答查询.

运算符^表示按位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

这是正确的,因为:

• xor是可交换的和联想的
• 相等位上的xor产生零
• xor为零不会改变位

应为int/float选择适当的最小/最大函数.如果只存在正浮点数,那么可以直接在浮点表示上使用整数最小值/最大值(这可能是合乎需要的,因为整数运算通常更快).

在不太可能出现硬件不支持min/max的情况下,可以执行以下操作:

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

但是,使用浮点运算时这是不正确的,因为需要精确的最小值/最大值而不是接近它的值.幸运的是,浮动最小/最大值已经硬件支持多年(在x86上,从奔腾III及以后).

Answer 3

如果您正在寻找最有效的解决方案,我会想象它是这样的:

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

该方法需要至少两次,最多三次比较.它故意忽略了两个值相等的可能性(就像你的问题一样):如果这很重要,可以扩展方法以检查这一点.

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

还有一个想法.有三个数字{a,b,c}.然后:

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

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

Answer 6

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

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

EDITS:

1. @Pagas发现的上述错误已得到修复.
2. @Pagas还指出,如果仅使用条件,则不能使用少于5个条件,但您可以使用临时变量或值交换来减少此条件.
3. 我想补充一点,很难预测纯条件解决方案或分配解决方案是否会更快.它可能取决于JIT的好坏,但我认为条件版本对于优化器来说更容易分析.

Answer 7

我没有看到实现交换的解决方案：

int middle(int a, int b, int c) {
    // effectively sort the values a, b & c
    // putting smallest in a, median in b, largest in c

    int t;

    if (a > b) {
        // swap a & b
        t = a;
        a = b;
        b = t;
    }

    if (b > c) {
        // swap b & c
        t = b;
        b = c;
        c = t;

        if (a > b) {
            // swap a & b
            t = a;
            a = b;
            b = t;
        }
    }

    // b always contains the median value
    return b;
}