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