Число сравнений, выполненных в медиане 3 функции?

На данный момент моя функция находит медиану из 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.

Источник

7 ответов

Если вам нужно только среднее значение, вот решение без ответвлений, основанное на операторах min/max:

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

Процессоры Intel имеют SSE мин / макс векторные инструкции, поэтому, в зависимости от способности векторизации вашего или вашего компилятора, это может выполняться очень быстро.

Источник 
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];
Источник

Если мы допустим дополнительные операции, мы могли бы использовать не более двух сравнений, чтобы найти медиану. Хитрость заключается в том, чтобы использовать эксклюзив или найти связь между тремя числами.

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).
Если у них разный знак, то медиана. В противном случае, а является либо минимумом, либо максимумом. В этом случае нам нужен второй эксклюзив или (e^g).

Опять же, мы собираемся выяснить разницу между знаковым битом между (ab) и (bc). Если у них разные знаковые биты, один случай - это a > b && b В этом случае мы также получаем a > c, потому что a является максимумом в этом случае. Итак, у нас есть a > c > b. Другой случай - это c && a . Итак, у нас есть ;В обоих случаях с является медианой.

Если (ab) и (bc) имеют один и тот же бит знака, то b - это медиана, использующая аргументы, аналогичные приведенным выше. Эксперименты показывают, что для случайного ввода потребуется 1,667 сравнений, чтобы узнать медиану, и еще одно сравнение для получения порядка.

Источник

Больше похоже на это

#define MEDIAN(a,b,c) ( (a > b) ? max(b, min(a,c)) :
                                  min(b, max(a,c)) )
Источник

Чтобы отсортировать 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) поддерживают сравнения, где следующий адрес ПК выбирается из трех вариантов: LT,EQ,GT. При достаточно малом алфавите этот шанс немного уменьшает количество необходимых сравнений.

Также это, вероятно, не имеет практического применения, если принять во внимание, что штрафы от неправильных предсказаний ветвлений из-за слишком сложных вложенных структур могут быть намного больше, чем выгоды от сохраненного сравнения.

Источник

Python V2

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(1,18,10)) # => 10
Источник

Используя только два сравнения:

      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;
}
Источник
Другие вопросы по тегам