Число сравнений, выполненных в медиане 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.
Решение
Если вам нужно только среднее значение, вот решение без ответвлений, основанное на операторах 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) состоит в том, чтобы выяснить разницу между знаковым битом между (a-b) и (a-c).
Если у них разный знак, то медиана. В противном случае, а является либо минимумом, либо максимумом. В этом случае нам нужен второй эксклюзив или (e ^ g).
Опять же, мы собираемся выяснить разницу между знаковым битом (а-б) и (б-в).
Если у них есть другой бит знака, один случай, что а> б && б < с. В этом случае мы также получаем а> с так как а это максимум в этом случае. Итак, мы имеем а> с> б.
Другой случай < б && б> с && < с. Итак, мы имеем < с < б;
В обоих случаях медиана.
Если (А-б) а также (До нашей эры) имеют те же бит знака, тогда б медиана используя аналогичные аргументы, как указано выше. Эксперименты показывают, что случайный вход потребуется 1.667 сравнений выяснить медиана и еще одно сравнение, чтобы получить заказ.
Чтобы отсортировать 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. При достаточно малом алфавите этот шанс немного уменьшает количество необходимых сравнений.
Также это, вероятно, не имеет практического применения, если принять во внимание, что штрафы от неправильных предсказаний ветвлений из-за слишком сложных вложенных структур могут быть намного больше, чем выгоды от сохраненного сравнения.
Больше похоже на это
#define MEDIAN(a,b,c) ( (a > b) ? max(b, min(a,c)) :
min(b, max(a,c)) )
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