Данный массив представляет собой массив из трех числовых значений, и я хотел бы знать среднее значение трех.
Вопрос: какой самый быстрый способ найти середину трех?
Мой подход - это такой шаблон - поскольку существует три числа, есть шесть перестановок:
if (array[randomIndexA] >= array[randomIndexB] &&
array[randomIndexB] >= array[randomIndexC])
Было бы очень приятно, если бы кто-то помог мне найти способ более элегантный и быстрее.
Если вы ищете наиболее эффективное решение, я бы предположил, что это что-то вроде этого:
if (array[randomIndexA] > array[randomIndexB]) {
if (array[randomIndexB] > array[randomIndexC]) {
return "b is the middle value";
} else if (array[randomIndexA] > array[randomIndexC]) {
return "c is the middle value";
} else {
return "a is the middle value";
}
} else {
if (array[randomIndexA] > array[randomIndexC]) {
return "a is the middle value";
} else if (array[randomIndexB] > array[randomIndexC]) {
return "c is the middle value";
} else {
return "b is the middle value";
}
}
Этот подход требует как минимум двух и не более трех сравнений. Он сознательно игнорирует возможность равенства двух значений (как и ваш вопрос): если это важно, можно также расширить этот подход, чтобы проверить это.
Здесь есть ответ с использованием min/max и никаких ветвей (fooobar.com/questions/153227/...). На самом деле достаточно 4 мин/макс, чтобы найти медиану, нет необходимости в xor's:
median = max(min(a,b), min(max(a,b),c));
Хотя, это не даст вам медианный индекс значений...
Разбивка всех случаев:
a b c
1 2 3 max(min(1,2), min(max(1,2),3)) = max(1, min(2,3)) = max(1, 2) = 2
1 3 2 max(min(1,3), min(max(1,3),2)) = max(1, min(3,2)) = max(1, 2) = 2
2 1 3 max(min(2,1), min(max(2,1),3)) = max(1, min(2,3)) = max(1, 2) = 2
2 3 1 max(min(2,3), min(max(2,3),1)) = max(2, min(3,1)) = max(2, 1) = 2
3 1 2 max(min(3,1), min(max(3,1),2)) = max(1, min(3,2)) = max(1, 2) = 2
3 2 1 max(min(3,2), min(max(3,2),1)) = max(2, min(3,1)) = max(2, 1) = 2
Можно ответить на запрос без ответвлений, если оборудование может отвечать на запросы min и max без ветвей (большинство современных процессоров могут это сделать).
Оператор ^ обозначает побитовое xor.
Input: triple (a,b,c)
1. mx=max(max(a,b),c)
2. mn=min(min(a,b),c)
3. md=a^b^c^mx^mn
4. return md
Это правильно, потому что:
Соответствующие функции min/max должны быть выбраны для int/float. Если присутствуют только положительные поплавки, тогда можно использовать целое число min/max непосредственно в представлении с плавающей запятой (это может быть желательно, поскольку операции с целыми числами обычно быстрее).
В маловероятном сценарии, что аппаратное обеспечение не поддерживает min/max, можно сделать что-то вроде этого:
max(a,b)=(a+b+|a-b|)/2
min(a,b)=(a+b-|a-b|)/2
Однако это неверно при использовании операций с плавающей точкой, поскольку требуется точный min/max, а не что-то, что близко к нему. К счастью, float min/max поддерживался в аппаратных средствах на века (на x86, от Pentium III и далее).
Это можно сделать с помощью двух сравнений максимум.
int median(int a, int b, int c) {
if ( (a - b) * (c - a) >= 0 ) // a >= b and a <= c OR a <= b and a >= c
return a;
else if ( (b - a) * (c - b) >= 0 ) // b >= a and b <= c OR b <= a and b >= c
return b;
else
return c;
}
И еще одна идея. Есть три цифры {a,b,c}. Тогда:
middle = (a + b + c) - min(a,b,c) - max(a,b,c);
Конечно, мы должны помнить о числовых ограничениях...
Здесь вы можете выразить это, используя только условные выражения:
int a, b, c = ...
int middle = (a <= b)
? ((b <= c) ? b : ((a < c) ? c : a))
: ((a <= c) ? a : ((b < c) ? c : b));
РЕДАКТИРОВАТЬ:
Я не видел решения, которое реализует свопы:
int middle(int a, int b, int c) {
// effectively sort the values a, b & c
// putting smallest in a, median in b, largest in c
int t;
if (a > b) {
// swap a & b
t = a;
a = b;
b = t;
}
if (b > c) {
// swap b & c
t = b;
b = c;
c = t;
if (a > b) {
// swap a & b
t = a;
a = b;
b = t;
}
}
// b always contains the median value
return b;
}
Вы могли бы написать это самым простым способом. Как вы сказали, есть только шесть возможностей. Никакой разумный подход не будет более быстрым или медленным, поэтому просто пойдите для чего-то легкого для чтения.
Я бы использовал min() и max() для лаконичности, но три вложенных if/thens были бы такими же хорошими, я думаю.
Если вы должны найти один из значений X, удовлетворяющий некоторым критериям, вам нужно хотя бы сравнить это значение с каждым из X-1. Для трех значений это означает, по крайней мере, два сравнения. Поскольку это "найти значение, которое не является самым маленьким, а не самым большим", вы можете обойтись только двумя сравнениями.
Затем вы должны сконцентрироваться на написании кода, чтобы вы могли четко видеть, что происходит, и держать его простым. Здесь это означает вложенный if. Это позволит JVM оптимизировать это сравнение как можно больше во время выполнения.
См. решение, предоставленное Tim (Самый быстрый способ найти среднее значение тройки?), чтобы увидеть пример этого. Многие строки кода необязательно оказываются более крупными, чем вложенные вопросительные знаки-двоеточие.
median = (a+b+c) - Math.min(Math.min(a,b),c) - Math.max(Math.max(a,b),c)
Это основной, я не знаю, насколько это эффективно, но эти функции используют, если условия в конце концов. Если вы хотите, чтобы вы могли включить это утверждение в инструкции if-else, это потребует времени. Почему так ленив?
Самый простой способ - сортировка. Например, рассмотрите этот код:
import java.util.Arrays;
int[] x = {3,9,2};
Arrays.sort(x); //this will sort the array in ascending order
//so now array x will be x = {2,3,9};
//now our middle value is in the middle of the array.just get the value of index 1
//Which is the middle index of the array.
int middleValue = x[x.length/2]; // 3/2 = will be 1
Что это. Это очень просто.
Таким образом, вам не нужно учитывать размер массива. Поэтому, если у вас есть 47 разных значений, вы также можете использовать этот код для поиска среднего значения.
Этот будет работать:
template<typename T> T median3_1_gt_2(const T& t1, const T& t2, const T& t3) {
if (t3>t1) {
return t1;
} else {
return std::max(t2, t3);
}
}
template<typename T> T median3(const T& t1, const T& t2, const T& t3) {
if (t1>t2) {
return median3_1_gt_2(t1, t2, t3);
} else {
return median3_1_gt_2(t2, t1, t3);
}
}
if(array[aIndex] > array[bIndex]) {
if(array[bIndex] > array[cIndex]) return bIndex;
if(array[aIndex] > array[cIndex]) return cIndex;
return aIndex;
} else {
if(array[bIndex] < array[cIndex]) return bIndex;
if(array[aIndex] < array[cIndex]) return cIndex;
return aIndex;
}
На основе отличного ответа от Gyorgy вы можете получить средний индекс без ветвей, заменив min/max условными ходами:
int i = (array[A] >= array[B]) ? A : B;
int j = (array[A] <= array[B]) ? A : B;
int k = (array[i] <= array[C]) ? i : C;
int median_idx = (array[j] >= array[k]) ? j : k;
javac должен генерировать ConditionalNode для каждого из этих тройных назначений, которые преобразуются в пары cmp/cmov в сборке. Также обратите внимание, что сравнения были выбраны так, что в случае равенства возвращается первый индекс в алфавитном порядке.
largest=(a>b)&&(a>c)?a:(b>c?b:c);
smallest=(a<b)&&(a<c)?a:(b<c?b:c);
median=a+b+c-largest-smallest;
Способ 1
int a,b,c,result;
printf("enter three number");
scanf("%d%d%d",&a,&b,&c);
result=a>b?(c>a?a:(b>c?b:c)):(c>b?b:(a>c?a:c));
printf("middle %d",result);
Способ 2
int a=10,b=11,c=12;
//Checking for a is middle number or not
if( b>a && a>c || c>a && a>b )
{
printf("a is middle number");
}
//Checking for b is middle number or not
if( a>b && b>c || c>b && b>a )
{
printf("b is middle number");
}
//Checking for c is middle number or not
if( a>c && c>b || b>c && c>a )
{
printf("c is middle number");
}
Способ 3
if(a>b)
{
if(b>c)
{
printf("b is middle one");
}
else if(c>a)
{
printf("a is middle one");
}
else
{
printf("c is middle one");
}
}
else
{
if(b<c)
{
printf("b is middle one");
}
else if(c<a)
{
printf("a is middle one");
}
else
{
printf("c is middle one");
}
}
Я получил подходящие анны найти среднее значение тройки
Вот ответ на Python, но такая же логика применима к Java-программе.
def middleOfThree(a,b,c):
middle = a
if (a < b and b < c) or (c < b and b < a):
middle = b
elif (a < c and c < b) or (b < c and c < a):
middle = c
print 'Middle of a=%d, b=%d, c=%d is %d' % (a,b,c,middle)
middleOfThree(1,2,3)
middleOfThree(1,3,2)
middleOfThree(2,1,3)
middleOfThree(2,3,1)
middleOfThree(3,2,1)
middleOfThree(3,1,2)
Поднять старый поток, но все же это самое короткое решение, и никто не упомянул об этом.
int median2(int a, int b, int c) {
return (a > b) ^ (a > c) ? a : (a > b) ^ (b > c) ? c : b;
}
(тесты охватывают все возможные комбинации, все они печатают 6)
public static void main(String[] args) {
System.out.println(median(3, 6, 9));
System.out.println(median(3, 9, 6));
System.out.println(median(6, 3, 9));
System.out.println(median(6, 9, 3));
System.out.println(median(9, 3, 6));
System.out.println(median(9, 6, 3));
System.out.println(median(6, 6, 3));
System.out.println(median(6, 6, 9));
System.out.println(median(6, 3, 6));
System.out.println(median(6, 9, 6));
System.out.println(median(3, 6, 6));
System.out.println(median(9, 6, 6));
System.out.println(median(6, 6, 6));
}
(a > b) ^ (a > c) false, если c > a > b или c < a < b - вернуть a;
в противном случае (a > b) ^ (b > c) false, если либо a > b > c либо a < b < c - вернуть b;
в противном случае вернуть c;
Предположим, что p = a > b; q = b > c; s = a > c;
Давайте построим карту Карно.
| 00 01 11 10 (p, q)
---+----------------------
0 | b c * a
1 | * a b c
(s)|
* означает, что комбинация невозможна (как a > b; b > c; a < c)
Обратите внимание, что правая часть является зеркальной левой частью, и карту можно упростить, введя t = p ^ q; u = s ^ p t = p ^ q; u = s ^ p
| 0 1 (t)
---+---------
0 | b c
1 | * a
(u)|
Таким образом, функция может быть записана как
private static int median(int a, int b, int c) {
boolean t = (a > b) ^ (b > c);
boolean u = (a > b) ^ (a > c);
if (u)
return a;
else if (t)
return c;
else
return b;
}
Встраивание переменных и замена ifs на?: Дает ответ
int median2(int a, int b, int c) {
return (a > b) ^ (a > c) ? a : (a > b) ^ (b > c) ? c : b;
}
Решение отлично работает, даже если некоторые входы равны, что может быть неочевидно, но вполне логично.
Используя idxA для idxC в ary,
int ab = ary[idxA] < ary[idxB] ? idxA : idxB;
int bc = ary[idxB] < ary[idxC] ? idxB : idxC;
int ac = ary[idxA] < ary[idxC] ? idxA : idxC;
int idxMid = ab == bc ? ac : ab == ac ? bc : ab;
indexMiddle указывает на среднее значение.
Объяснение: из 3 минимумов 2 - общий минимум, а другое значение должно быть посередине. Поскольку мы проверяем равенство, мы можем сравнивать индексы в последней строке, а не сравнивать значения массива.
Вы можете использовать массив, например:
private static long median(Integer i1, Integer i2, Integer i3) {
List<Integer> list = Arrays.asList(
i1 == null ? 0 : i1,
i2 == null ? 0 : i2,
i3 == null ? 0 : i3);
Collections.sort(list);
return list.get(1);
}
100% бесплатная версия для целых чисел:
int mid(const int a, const int b, const int c) {
const int d0 = b - a;
const int m = (d0 >> 31);
const int min_ab = a + (d0 & m);
const int max_ab = a + (d0 & ~m);
const int d1 = c - max_ab;
const int min_max_ab_c = max_ab + (d1 & (d1 >> 31));
const int d2 = min_ab - min_max_ab_c;
return min_ab - (d2 & (d2 >> 31));
}
Построен с использованием функций min/max без ответвлений:
int min(const int a, const int b) { const int d = b - a; return a + (d & (d >> 31)); }
int max(const int a, const int b) { const int d = a - b; return a - (d & (d >> 31)); }
Это может не выглядеть красиво, но машинный код может оказаться более эффективным на некоторых архитектурах. Особенно те без инструкций min/max. Но я не сделал никаких отметок, чтобы подтвердить это.
или один лайнер для поиска индекса в массиве, содержащем среднее значение:
int middleIndex = (a[0]<a[1]) ? ((a[0]<a[2) ? a[2] : a[0]) : ((a[1]<a[2) ? a[2] : a[1]);
Многие из них, похоже, используют довольно сложные операторы if. Я нашел очень простой обходной путь, используя математическую библиотеку.
Math.max(Math.min(array[start], array[mid]), Math.min(array[start], array[mid], array[end]))
Хорошо работает.