9

現時点では、私の関数は 3 つの数値の中央値を見つけて並べ替えますが、常に 3 つの比較を行います。ネストされた if ステートメントをどこかで使用して、関数が 2 つの比較のみを行うことがあると考えています。

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

2

追加の操作を許可する場合、最大 2 つの比較を使用して中央値を見つけることができます。トリックは、排他を使用するか、3 つの数の間の関係を見つけることです。

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 は最小値または最大値です。その場合、2 番目の排他的 or (e^g) が必要です。

ここでも、 (ab) と (bc)の符号ビットの違いを調べます。それらの符号ビットが異なる場合、1 つのケースは a > b && b < c です。この場合、 a > cも得られます。これは、この場合は a が最大であるためです。したがって、a > c > b です。 もう 1 つのケースはa < b && b > c && a < cです。したがって、a < c < bです。 どちらの場合も、c は中央値です。

(ab)と(bc)の符号ビットが同じ場合、b は上記と同様の引数を使用した中央値です。実験によると、ランダムな入力では、中央値を見つけるために 1.667 回の比較が必要であり、次数を得るために 1 つの追加の比較が必要です。

于 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 の 3 つの選択肢から選択される比較をサポートしています。アルファベットが十分に小さい場合、この可能性は必要な比較の数をわずかに減らします。

また、過度に複雑なネストされた構造による間違った分岐予測からのペナルティは、保存された比較からの利益よりもはるかに大きくなる可能性があるため、これはおそらく実用的ではありません。

于 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 に答える