9

截至目前，我的函数找到了 3 个数字的中位数并对它们进行排序，但它总是进行三个比较。我想我可以在某处使用嵌套的 if 语句，这样有时我的函数只会进行两次比较。

int median_of_3(int list[], int p, int r)
{
    int median = (p + r) / 2;

    if(list[p] > list[r])
        exchange(list, p, r);
    if(list[p] > list[median])
        exchange(list, p, median);
    if(list[r] > list[median])
        exchange(list, r, median);

    comparisons+=3;                // 3 comparisons for each call to median_of_3

    return list[r];
}

我不确定我可以在哪里制作嵌套的 if 语句。

4

7 回答 7

26

如果您只需要中值，这里有一个基于 min/max 运算符的无分支解决方案：

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

英特尔 CPU 具有 SSE 最小/最大矢量指令，因此根据您或您的编译器的矢量化能力，它可以运行得非常快。

于 2013-09-26T12:04:21.453 回答
2

如果我们允许额外的操作，我们最多可以使用 2 次比较来找到中位数。诀窍是使用排他或找到三个数字之间的关系。

void median3(int A[], int p, int r)
{
    int m = (p+r)/2;
    /* let a, b, c be the numbers to be compared */
    int a = A[p], b = A[m], c = A[r];
    int e = a-b;
    int f = a-c;

    if ((e^f) < 0) {
        med_comparisons += 1;
        /* a is the median with 1 comparison */
        A[m] = a;
        /* b < a < c ? */
        if (b < c) /* b < a < c */ { A[p] = b, A[r] = c; }
        else       /* c < a < b */ { A[p] = c, A[r] = b; }
        comparisons += 2;
    } else {
        med_comparisons += 2;
        int g = b-c;
        if ((e^g) < 0) {
            /* c is the median with 2 comparisons */ 
            A[m] = c;
            /* a < c < b ? */
            if (a < b) /* a < c < b */ { A[p] = a, A[r] = b; }
            else       /* b < c < a */ { A[p] = b, A[r] = a; }
        } else {
            /* b is the median with 2 comparisons */
            A[m] = b;
            /* c < b < a ? */
            if (a > c) /* c < b < a */ { A[p] = c; A[r] = a; }
            else       /* a < b < c */ { /* do nothing */    }
        }
        comparisons += 3;
    }
}

第一个异或（e^f）是找出（ab）和（ac）之间符号位的差异。
如果它们具有不同的符号位，则 a 是中位数。否则，a 要么是最小值，要么是最大值。在这种情况下，我们需要第二个异或 (e^g)。

同样，我们将找出(ab) 和 (bc)之间符号位的差异。如果它们有不同的符号位，一种情况是 a > b && b < c。在这种情况下，我们也得到a > c，因为在这种情况下a 是最大值。所以我们有a > c > b。 另一种情况是a < b && b > c && a < c。所以我们有a < c < b ; 在这两种情况下， c 都是中位数。

如果(ab)和(bc)具有相同的符号位，则 b 是使用与上述类似参数的中位数。实验表明，一个随机输入需要1.667 次比较才能找出中位数，另外需要一次比较才能得到顺序。

于 2012-11-12T05:56:28.763 回答
1

要对 3 个项目进行排序，您需要进行 3 次比较。

要偶然找到中间的一个，您需要 2 个。

要准确找到中间那个，您平均需要 2+2/3 ~= 2.67（具有均匀分布的随机数据）

if (a<b) {
   // partial order = a,b
   if (b<c) {  } // 2 comparisons: order is a,b,c
      else { // order is a,c,b or c,a,b
          if (a<c) { } // order is a,c,b -- 3 comparisons
          else { }     // order is c,a,b -- 3 comparisons
      }
} else {
   // partial order = b,a  
   if (c<b) {  } // 2 comparisons: order is c,b,a
   else {  // order is b,c,a or b,a,c
      if (c>a) { } // order is b,a,c -- 3 comparisons
      else { }   // order is b,c,a -- 3 comparisons
   }
}

作为附加说明：一些语言（Fortran、IIRC）以及一些 ISA（VAX，再次是 IIRC）支持比较，其中下一个 PC 地址从三个选项中选择：LT、EQ、GT。如果字母表足够小，这个机会会稍微减少所需比较的次数。

此外，这可能没有实际用途，因为嵌套结构过于复杂而导致错误分支预测的惩罚可能比保存比较的收益大得多。

于 2012-10-17T15:41:26.453 回答
1 
int m = (p + r) / 2;
if (list[p] < list[m])
    if (list[p] >= list[r])
        return list[p];
    else if (list[m] < list[r])
        return list[m];
else
    if (list[p] < list[r])
        return list[p];
return list[r];
于 2012-10-17T15:45:23.377 回答
1

更像这样

#define MEDIAN(a,b,c) ( (a > b) ? max(b, min(a,c)) :
                                  min(b, max(a,c)) )
于 2016-03-16T00:06:45.840 回答
0

仅使用两个比较：

double median_of_three(double left, double middle, double right) 
{
    double med = middle;
    if (left  < med) med = left;
    if (right > med) med = right;
    return med;
}
于 2021-05-29T17:37:16.207 回答
0

Python

#!/usr/bin/env python3

def bigger(a,b):
    if a > b:
       return a
    else:
    return b

def biggest(a,b,c):
    return bigger(a,bigger(b,c))

def median(a,b,c):
    big = biggest(a,b,c)
    if big == a:
       return bigger(b,c)
    if big == b:
       return bigger(a,c)
    else:
       return bigger(a,b)

打印中位数

print(median(20,18,19)) # => 19
于 2018-06-19T17:33:01.753 回答