3个函数的中位数比较数？

Question

到目前为止,我的函数找到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语句.

Answer 1

如果您只需要中值,这里是基于最小/最大运算符的无分支解决方案:

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

英特尔CPU具有SSE最小/最大向量指令,因此根据您或您的编译器的向量化能力,这可以非常快速地运行.

Answer 2

要对 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。如果字母表足够小，这种机会会稍微减少所需比较的次数。

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